[ 백준 1726번 로봇 ] Python 코드 (BFS)

1. 문제

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

1726번: 로봇

---

2. BFS 풀이 (3차원 visited 배열)  

나는 처음에 다른 방식으로 풀었다.

BFS에서 visited배열의 활용 방식을 살짝 변경해서 최단거리를 찾는 알고리즘으로 사용했는데

혼자 풀고 뿌듯함에 차있을 때, 다른 분들의 3차원 visited 배열을 보고 무릎을 탁 쳤다.

메모리 사용량과 처리시간도 더 적었을 뿐더러, 무엇보다 기본적인 BFS 알고리즘 동작방식을 그대로 따랐다.

 

3차원 visited 배열의 핵심은, 방향에 대한 visited 배열을 3차원으로 추가하자는 것이다.

왜냐하면 우리는 위치뿐만 아니라 방향조건까지 맞춰야하기 때문이다.

동,서,남,북 총 4개의 방향이 있으므로 높이가 4인 3차원 visited 배열을 만들어야 한다.

 

그러면 코드를 짤 때 하나만 주의하면 된다.

큐에 주변노드를 삽입할 때, 비용이 +1만큼 증가하는 경우를 모두 찾아 한번에 넣어야 한다.

그래야지 진정한 넓이 위주의 탐색이 구현되어, 최단거리를 찾을 수 있다.

비용이 +1만큼 증가하는 경우는 다음과 같다.

• 1만큼 직진하는 경우
• 2만큼 직진하는 경우
• 3만큼 직진하는 경우
• 오른쪽으로 90도 도는 경우
• 왼쪽으로 90도 도는 경우

3. 코드

위에서 설명한 것처럼

3차원 배열을 만들어서, BFS 탐색할 때마다 비용이 1만큼 증가하는 경우를 큐에 넣어주면 된다.

한 가지 주의할 점은, 직진에 대한 탐색을 할 때, 조건을 만족하지 못하는 위치를 만나면 바로 for문을 break해야한다.

아니면 다음과 같이 직진이 불가능함에도 BFS탐색을 하는 에러사항이 발생한다.

import sys
from collections import deque
input = sys.stdin.readline

dir_ref = {0: (0, 1), 1: (0, -1), 2: (1, 0), 3: (-1, 0)}        # { 현재방향: (i증가 방향, j증가 방향)}
turn_ref = {0: (2, 3), 1: (2, 3), 2: (0, 1), 3: (0, 1)}         # { 현재방향: (회전 시 방향1, 회전 시 방향2)}

def bfs2():
    INF= 20002
    visited = [[[0] * 4 for _ in range(M)] for _ in range(N)]
    q = deque()

    visited[si-1][sj-1][sd-1] = 1
    q.append((si-1, sj-1, sd-1))

    while q:
        i, j, d = q.popleft()
        if i == ei-1 and j == ej-1 and d == ed-1:   # 종료조건
            return visited[ei-1][ej-1][ed-1] - 1

        # 무조건 1씩 증가하도록 설계
        # 1. 직진하기
        for dist in range(1, 4):        # 1~3까지 한번에 이동할 수 있음
            ni = i + dir_ref[d][0] * dist
            nj = j + dir_ref[d][1] * dist
            if 0 <= ni < N and 0 <= nj < M and not arr[ni][nj]: # 해당 위치로 직진이 가능한 경우
                if not visited[ni][nj][d]:                          # 해당 위치와 방향을 방문하지 않았을 경우에만 append
                    q.append((ni, nj, d))
                    visited[ni][nj][d] = visited[i][j][d] + 1
            else:                                               # 직진이 불가능한 경우 break하여 for문을 탈출해야 함, 안그러면 예외케이스 발생
                break
        # 2. 방향변환
        for nd in turn_ref[d]:          # turn_ref 딕셔너리를 미리 정의하여 값을 읽어옴
            if not visited[i][j][nd]:       # 해당 위치와 방향을 방문하지 않았을 경우에만 append
                q.append((i, j, nd))
                visited[i][j][nd] = visited[i][j][d] + 1

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
si, sj, sd = map(int, input().split())
ei, ej, ed = map(int, input().split())

print(bfs2())