[백준]2178.미로찾기

문제설명

아주 기초적인 BFS문제. 최단거리를 찾아라.

접근

카카오2020 신입공채 블록이동하기 문제를 풀다가 아주 복잡하게 최단경로 문제를 풀고 있는 것 같아 이 문제를 살펴보았다.

접근1

개별의 이동에 대해 방문정보를 가지고 있어서 모두 탐색하도록 정했다.

• (1,1)에서 (2,1)이동가능하면 (2,1)노드와 함께 방문정보 (1,1),(2,1)을 que에 넣어준다.
• (1,1)에서 (1,2)이동가능하면 (2,2)노드와 함께 방문정보 (1,1),(1,2)를 que에 넣어준다.
• (2,1)과 (1,2)모두 (2,2)이동이 가능하므로 각각의 방문에 (1,1),(2,1),(2,2), (1,1),(1,2),(2,2)를 que에 넣어준다.

굵은 표시에 있는 내용을 보면 '최단거리'를 구하는 문제이므로 이럴 필요가 없다.

1. 이전 이동에 넣은 que가 한 번 비워질 때마다 count가 1씩 증가하는데, 다익스트라 알고리즘을 생각하면 당연하다. v의 위치에 최단거리 d를 구했는데, d+x가 최단거리일 수 있겠는가?

2. 또한, v에 도달했을 때 적용하는 알고리즘은 동일하므로 중복을 방지하기 위해서라도 visited를 통일해야 한다.

따라서 위 2가지 이유를 들어 visited를 통일시켜도 무방하다.

접근2

이건 다른 사람들의 코드를 참고했다. 위의 visited 통합을 포함하여 각 좌표별 count값을 가지는 테이블을 선언한다. 그러면 이는 visited와 count를 동시에 기록할 수 있게 된다. 이게 더 빨랐음!

구현

import sys
input = sys.stdin.readline
class QUEUE:
    def __init__(self):
        self.queue = [0]*50000
        self.front = 0
        self.rear = 0
    def push(self,item):
        self.front += 1
        self.queue[self.front] = item

    def pop(self):
        self.rear += 1
        return self.queue[self.rear]

N,M = map(int,input().split())
table = [input().rstrip() for _ in range(N)]

for i in range(N):
    table[i] = '0'+table[i]+'0'

table.insert(0,'0'*(M+2))
table.append('0'*(M+2))

visited = [0 for _ in range(N+2)]
visited[1] = visited[1]|1<<1

que = QUEUE()
que.push([1,1,1]) # r좌표,c좌표,cnt
direction = {0:[0,1] , 1:[0,-1] , 2:[1,0] , 3:[-1,0]}
while True :
    r,c,cnt = que.pop()
    if r == N and c == M:
        print(cnt)
        break

    for d in range(4):
        dr = r+direction[d][0]
        dc = c+direction[d][1]
        if visited[dr]&(1<<dc) or table[dr][dc] == '0':
            continue
        visited[dr] = visited[dr]|(1<<dc)
        que.push([dr,dc,cnt+1])