[python code review] 12주차 (줄 세우기, 배달, 로봇 청소기)

 

---

[1] 로봇 청소기

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

[BFS + 시물레이션]

이 문제는 deq에서 결국 하나의 좌표만 관리되기 때문에 굳이 BFS로 풀지 않고 좌표로만 접근해도 됐다. 

보통 현재 좌표에서 네 가지 방향 모두 사용했는지 체크하는 변수를 두거나 for문으로 4가지 방향을 돌려서 검사하는 방식으로 구현하는데, 나는 전자의 방식을 사용했는데 (네 가지 방향 모두 사용했는지 체크하는 변수 : turn_time)

for문 돌리는 방식이 가독성이 좋아서 다시 코드를 개선했다.

from collections import deque

# 북 동 남 서
moves = [(-1,0),(0,1),(1,0),(0,-1)]
n, m, = map(int, input().split())
x, y, d = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

deq = deque([(x, y, d)])
answer = 1
board[x][y] = 2
turn_time = 0
while deq:
    x, y, d = deq.popleft()
    nd = (d + 3) % 4  # 왼쪽으로 방향 회전
    dx, dy = moves[nd][0], moves[nd][1]

    nx, ny = dx + x, dy + y
    if 0 <= nx < n and 0 <= ny < m:
        # 청소하지 않은 빈공간이라면
        if not board[nx][ny]:
            answer += 1
            board[nx][ny] = 2
            # 왼쪽으로 회전후 전진
            deq.append((nx, ny, nd))
            turn_time = 0
        else:
            # 왼쪽으로 회전만하고 제자리
            deq.append((x, y, nd))
            turn_time += 1

    if turn_time == 4:
        nx, ny = x - dx, y - dy
        if 0 <= nx < n and 0 <= ny < m:
            # 후진했는데 뒤가 벽이라면
            if board[nx][ny] == 1:
                print(answer)
                exit()
            else:
                deq.popleft()
                deq.append((nx, ny, nd))
                # print(deq)
                turn_time = 0

 

[코드 개선 - 시뮬레이션]

# 북 동 남 서
moves = [(-1,0),(0,1),(1,0),(0,-1)]
n, m, = map(int, input().split())
x, y, d = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

answer = 1
board[x][y] = 2

while True:
    flag = False
    # 왼쪽으로 방향 회전
    for _ in range(4):
        d = (d + 3) % 4
        dx, dy = moves[d][0], moves[d][1]
        nx = dx + x
        ny = dy + y
        # 청소하지 않은 빈공간이라면
        if not board[nx][ny]:
            answer += 1
            board[nx][ny] = 2
            # 왼쪽으로 회전후 전진
            x, y = nx, ny
            flag = True
            break
    # 4방향 모두 돌았으나 청소할 구역이 없는 경우
    if not flag:
        dx, dy = moves[d][0], moves[d][1]
        nx, ny = x - dx, y - dy

        # 후진했는데 뒤가 벽이라면
        if board[nx][ny] == 1:
            print(answer)
            exit()
        else:
            x, y = nx, ny

 

 

---

[2] 배달

https://www.acmicpc.net/problem/1175

1175번: 배달

[BFS + 4차원 배열]

x y, 좌표, 'C' 좌표, 4가지 방향까지 처리하기 위해 총 4차원 배열을 생성해야 풀 수 있는 문제였다. 

from collections import deque

n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]
    # 동 남 서 북
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

visit = [[[[0] * m for _ in range(n)] for _ in range(3)] for _ in range(4)]
s_x, s_y = 0, 0
check = False
for i in range(n):
    for j in range(m):
        if board[i][j] == 'S':
            s_x, s_y = i, j
        if not check and board[i][j] == 'C':
            check = True
            board[i][j] = 'D'


def bfs(x, y):
    deq = deque([[x, y, 0, 4, 0]])
    while deq:
        x, y, status, d, time = deq.popleft() # status : 'C' 방문시 1, 'D' 방문시 2
        time += 1
        for k in range(4):
            if k == d: continue
            nx, ny = x + dx[k], y + dy[k]
            if not(0 <= nx < n and 0 <= ny < m): continue

            if not visit[k][status][nx][ny]:
                if board[nx][ny] == '#':
                    continue

                elif board[nx][ny] == 'C':
                    if status == 2:
                        return time
                    deq.append([nx, ny, 1, k, time])
                    visit[k][1][nx][ny] = 1

                elif board[nx][ny] == 'D':
                    if status == 1:
                        return time
                    deq.append([nx, ny, 2, k, time])
                    visit[k][2][nx][ny] = 1
                else:
                    visit[k][status][nx][ny] = 1
                    deq.append([nx, ny, status, k, time])


answer = bfs(s_x, s_y)
print(answer if answer else -1)

 

[BFS + 4차원 배열 + 비트마스킹]

from collections import deque

n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]
    # 동 남 서 북
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

visit = [[[[0] * m for _ in range(n)] for _ in range(4)] for _ in range(4)]
target = []
s_x, s_y = 0, 0
for i in range(n):
    for j in range(m):
        if board[i][j] == 'S':
            s_x, s_y = i, j
            board[i][j] = '.'
        elif board[i][j] == 'C':
            target.append([i, j])


def bfs(x, y):
    deq = deque([[x, y, 0, 4, 0]])
    while deq:
        print(deq)
        x, y, count, d, time = deq.popleft()
        if count == 3:
            return time

        for k in range(4):
            if k == d: continue
            nx, ny = x + dx[k], y + dy[k]
            if not(0 <= nx < n and 0 <= ny < m): continue

            if not visit[k][count][nx][ny]:
                if board[nx][ny] == '#': continue
                elif board[nx][ny] == '.':
                    visit[k][count][nx][ny] = 1
                    deq.append([nx, ny, count, k, time + 1])
                elif board[nx][ny] == 'C':
                    # 'C' 좌표 처리시 비트마스킹 사용
                    bit = target.index([nx, ny])
                    visit[k][count | (bit + 1)][nx][ny] = 1
                    deq.append([nx, ny, count | (bit + 1), k, time + 1])


answer = bfs(s_x, s_y)
print(answer if answer else -1)

 

 

 

---

[3] 줄세우기

https://www.acmicpc.net/problem/7570

7570번: 줄 세우기

 

아이디어에 도달하기까지는 넘나 빡셌는데 풀이는 아주 심플했다.

어떤 블로거분이 알려주는 힌트로 접근해서 풀 수 있었지만 아이디어를 스스로 떠올리지 못했다. 

 

[선행 지식]

해당 문제를 풀이하기에 앞서 풀어보면 좋을 문제 https://www.acmicpc.net/problem/11053

 

[백준 7570번 아이디어 접근법]

1. 가장 긴 증가하는 부분수열을 찾으면 된다.
2. 그런데 증가하는 범위가 1이어야 된다.
3. 쉽게 생각하면 순서대로 있는 숫자 빼고는 앞이나 뒤로 다 보내버려서 모두 순서대로 만들어 주면 된다.
4. 예를 들어 5 2 4 1 3 가 있으면, 2 3 빼고 1은 맨 앞으로 4, 5는 뒤로 다 보내버리면 1 2 3 4 5 가 된다.

 

[그리디 + dp]

n = int(input())
lst = list(map(int, input().split())) # 5 2 4 1 3

dp = [0]*(n+1)
LIS = 0
# dp[x] : 숫자 x를 포함하면서 1씩 증가하는 가장 긴 증가하는 부분수열의 길이
# dp[5] = 1, dp[2] = 1, dp[4] = 1, dp[1] = 1, dp[3] = 2  
for data in lst:
    dp[data] = dp[data-1] + 1
    LIS = max(LIS, dp[data])
print(n - LIS) # 가장 긴 증가하는 부분 수열을 제외하고 다 꺼내줌