[백준/파이썬] 2178번 미로 탐색 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2178번 미로 탐색
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

1은 이동 가능한 칸, 0은 벽인 미로가 주어집니다. 시작점 (1,1)에서 도착점 (N,M)까지 이동할 때 지나야 하는 칸 수의 최솟값을 구하는 문제입니다.

코드

import collections

n, m = map(int, input().split())
maze = [[0]*(m+2)]
for _ in range(n):
    maze.append([0]+list(map(int, " ".join(map(str, input())).split()))+[0])
maze += [[0]*(m+2)]

Q = collections.deque([])
deQ = Q.popleft
enQ = Q.append

visitFlag = [[False]*(m+2) for  _ in range(n+2)]

class Pos:
    def  __init__(self, r, c, d, cnt):
        self.r = r
        self.c = c
        self.d = d
        self.cnt = cnt

visitFlag[1][1] = True
enQ(Pos(1, 1, 0, 1))

while Q:
    pos = deQ()
    if pos.r == n and pos.c == m:
        print(pos.cnt)
        break
    cnt = 0
    while cnt < 4:
        if pos.d == 0: 
            if(maze[pos.r-1][pos.c] == 1 and
               not visitFlag[pos.r-1][pos.c]):
                enQ(Pos(pos.r-1, pos.c, 0, pos.cnt+1))
                visitFlag[pos.r-1][pos.c] = True
        elif pos.d == 1:
            if(maze[pos.r][pos.c+1] == 1 and
               not visitFlag[pos.r][pos.c+1]):
                enQ(Pos(pos.r, pos.c+1, 0, pos.cnt+1))
                visitFlag[pos.r][pos.c+1] = True
        elif pos.d == 2:
            if(maze[pos.r+1][pos.c] == 1 and
               not visitFlag[pos.r+1][pos.c]):
                enQ(Pos(pos.r+1, pos.c, 0, pos.cnt+1))
                visitFlag[pos.r+1][pos.c] = True
        else:
            if(maze[pos.r][pos.c-1] == 1 and
               not visitFlag[pos.r][pos.c-1]):
                enQ(Pos(pos.r, pos.c-1, 0, pos.cnt+1))
                visitFlag[pos.r][pos.c-1] = True
        pos.d = (pos.d+1)%4
        cnt += 1

설명

최단 칸 수를 묻는 문제라 BFS가 기본 해법입니다.

• 큐에서 현재 위치를 꺼내 4방향으로 확장합니다.
• 아직 방문하지 않은 1 칸만 큐에 넣습니다.
• 도착점에 처음 도달했을 때의 cnt가 최소 이동 칸 수입니다.

---

• 백준 문제풀이 전체 목록 보기

---