문제

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

❗ 풀이

문제 접근 1

전형적인 BFS + 델타 탐색 문제로 생각하고, visited를 2차원 배열로 생성하여 처음 도착한 칸에 한하여 해당 칸까지 도착한 명령 입력 횟수를 visited에 입력해주었다. 그리고, 목표한 좌표에 도달했을 때 입력받은 도착 방향에 맞게 입력 횟수를 추가해주고 최종적인 값을 출력하는 식으로 접근했다.

코드 1

일반적인 델타탐색과는 다른 점이 몇 가지 존재하기 때문에 꼼꼼하게 코드를 짜다보니 코드가 매우 길어졌다...(예를 들면 180도 회전을 하는 경우도 고려해야하고, 한번에 세칸까지 갈 수 있기도 한 점을 고려해야한다). 모든 경우의 수를 고려했기 때문에 당연히 이 코드를 돌리면 당연히 정답이 출력되지만, 백준 상에서는 당연히 시간초과가 발생하였다. 디버깅을 통해 어떻게든 시간을 줄여보려고 했지만, 몇시간에 걸친 디버깅에도 시간 초과가 발생해서 현재 내 알고리즘 지식으로는 해결할 수 없다는 것을 받아들이고 백준 질문 게시판에서 힌트를 얻어보기로 하였다.

from collections import deque

M, N = map(int, input().split())
factory = [list(map(int,input().split())) for _ in range(M)]
start_x, start_y, s_dir = map(int, input().split())
end_x, end_y, e_dir = map(int, input().split())

move = [(-1, 0), (0, 1), (1, 0), (0,-1)] # 상, 우, 하, 좌

def turn(dir, commend):
    if commend == 'left':
        return (dir+1) % 4
    else:
        if dir == 0:
            return 3
        else:
            return (dir-1)%4

def translate(dir):
    if dir == 1:
        return 1
    elif dir == 2:
        return 3
    elif dir == 3:
        return 2
    else:
        return 0
Q = deque([(start_x-1,start_y-1, translate(s_dir))])
visited = [[0] * N for i in range(M)]

ans = 1e7
while Q:
    x, y, dir = Q.popleft()
    if (x,y) ==(end_x-1,end_y-1):
        if dir == translate(e_dir):
            ans = min(ans, visited[x][y])
        else:
            l_dir = dir
            r_dir = dir
            l_cnt, r_cnt = 0, 0
            while l_dir!=e_dir:
                l_cnt += 1
                l_dir = turn(l_dir, 'left')
            while r_dir!=e_dir:
                r_cnt +=1
                r_dir = turn(r_dir, 'right')

            ans = min(ans, visited[x][y]+min(l_cnt, r_cnt))
    # 방향대로 가기
    for i in range(1, 4):
        nx, ny = x+move[dir][0]*i, y+move[dir][1]*i
        if nx < 0 or ny < 0 or nx == M or ny == N:
            break
        if factory[nx][ny]:
            break
        if not visited[nx][ny]:
            visited[nx][ny] = visited[x][y] + 1
            Q.append((nx, ny ,dir))
        else:
            if visited[nx][ny] > visited[x][y] + 1:
                visited[nx][ny] = visited[x][y] + 1
                Q.append((nx, ny, dir))
    # 왼쪽으로 돌기
    for i in range(1, 4):
        nx, ny = x+move[turn(dir, 'left')][0]*i, y+move[turn(dir, 'left')][1]*i
        if nx < 0 or ny < 0 or nx == M or ny == N:
            break
        if factory[nx][ny]:
            break
        if not visited[nx][ny]:
            visited[nx][ny] = visited[x][y] + 2
            Q.append((nx, ny ,turn(dir,'left')))
        else:
            if visited[nx][ny] > visited[x][y] + 2:
                visited[nx][ny] = visited[x][y] + 2
                Q.append((nx, ny, turn(dir, 'left')))
    # 오른쪽으로 돌기
    for i in range(1, 4):
        nx, ny = x+move[turn(dir, 'right')][0]*i, y+move[turn(dir, 'right')][1]*i
        if nx < 0 or ny < 0 or nx == M or ny == N:
            break
        if factory[nx][ny]:
            break
        if not visited[nx][ny]:
            visited[nx][ny] = visited[x][y] + 2
            Q.append((nx, ny ,turn(dir,'right')))
        else:
            if visited[nx][ny] > visited[x][y] + 2:
                visited[nx][ny] = visited[x][y] + 2
                Q.append((nx, ny, turn(dir, 'right')))
    # 180도 회전하기
    for i in range(1, 4):
        nx, ny = x+move[turn(turn(dir, 'right'), 'right')][0]*i, y+move[turn(turn(dir, 'right'), 'right')][1]*i
        if nx < 0 or ny < 0 or nx == M or ny == N:
            break
        if factory[nx][ny]:
            break
        if not visited[nx][ny]:
            visited[nx][ny] = visited[x][y] + 3
            Q.append((nx, ny ,turn(turn(dir,'right'), 'right')))
        if visited[nx][ny] > visited[x][y] + 3:
            visited[nx][ny] = visited[x][y] + 3
            Q.append((nx, ny ,turn(turn(dir,'right'), 'right')))


print(ans)

문제 접근 2

2차원 visited 배열에서 명령횟수를 저장하는 식으로 하는 방법을 3차원 배열에서 도착했을 때의 방향까지 고려한 visited 배열을 활용하였다.

코드 2

3차원 배열을 활용해 문제를 풀어본 적이 없었는데, 방향까지 고려해서 visited에 저장하는 방식은 정말 생소했다. 또 3차원 배열을 선언하면서 깊은 복사를 안하는 실수로 같은 행에 있는 visited 값들이 같이 입력되는 바람에 1시간을 날려먹는 등 꽤 구현하는데 애를 먹었다. 하지만 3차원 배열 + 방향 저장 이라는 힌트만 가지고 어떻게든 내 힘으로 구현을 해냈다.

또 한 좌표+방향을 popleft() 하고나서 로직을 수행할 때, (직진) or (회전한 좌표+방향)을 while문 한 번 안에 수행해줘야 코드가 꼬이지 않는다(재귀로 따로 하려다가 이 부분에서 몇시간을 날려먹었다).

from collections import deque

M, N = map(int, input().split())
factory = [list(map(int,input().split())) for _ in range(M)]
start_x, start_y, s_dir = map(int, input().split())
end_x, end_y, e_dir = map(int, input().split())
move = [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)] # 동 서 남 북
visited = [[[0 for i in range(5)] for j in range(N)] for k in range(M)]

Q = deque([(start_x-1, start_y-1, s_dir, 0)])
visited[start_x-1][start_y-1][s_dir] = 1

while Q:
    x, y, k, cnt = Q.popleft()
    if (x, y, k) == (end_x-1, end_y-1, e_dir):
        print(cnt)
        break
    for i in range(1, 4):
        nx = x + move[k][0]*i
        ny = y + move[k][1]*i
        if nx < 0 or ny < 0 or nx == M or ny == N:
            break
        if factory[nx][ny]:
            break
        if not visited[nx][ny][k]:
            visited[nx][ny][k] = 1
            Q.append((nx, ny, k, cnt+1))
    for i in range(1, 5):
        if i == k:
            continue
        if (i == 1 and k == 2) or (i == 2 and k == 1) or (i == 3 and k == 4) or (i == 4 and k == 3):
            if not visited[x][y][i]:
                visited[x][y][i] = 1
                Q.append((x, y, i, cnt+2))
        else:
            if not visited[x][y][i]:
                visited[x][y][i] = 1
                Q.append((x, y, i, cnt+1))