[백준] 2178 - 미로 탐색

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

 

문제

NxM 미로가 있다.
미로에서 1은 이동할 수 있는 칸이고 0은 이동할 수 없는 칸이다.
(1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸 수를 구하는 프로그램을 작성해라.

 

입력

• 첫째줄에 두 정수 N,M(2<=N,M<=100)이 주어진다.
• 다음 N개의 줄에는 M개의 정수가 미로로 주어진다.
• 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

• 첫째 줄에 지나야 하는 최소 칸 수를 출력한다.
• 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

풀이 방법

1. 최소 칸 수를 구하라고 명시되어 있으므로 BFS 문제임을 알 수 있다. (최소를 구하면 BFS, 모든 경우를 탐색해야 하면 DFS)
2. 시작 위치를 queue에 추가하고 방문 처리를 해준다.
3. while문으로 queue가 빌 때까지 반복하면서
4. popleft()로 현재 위치와 거리를 꺼내고
5. 갈 수 있는 방향을 모두 시도한다.
6. 현재 위치와 갈 방향을 더하고
7. 시작 위치를 queue에 추가하고 방문 처리를 해준다.
8. while문으로 queue가 빌 때까지 반복하면서
9. popleft()로 현재 위치와 거리를 꺼내고
10. 갈 수 있는 방향을 모두 시도한다.
11. 현재 위치와 갈 방향을 더하고 미로의 범위를 벗어나지 않았는지 확인한다.
12. 이동 가능한 칸이고 방문하지 않은 칸이면
13. 방문 처리하고 큐에 다음 위치와 거리 추가

 

작성한 코드

import sys
from collections import deque

N, M = list(map(int, sys.stdin.readline().strip().split()))
move = [(0,1),(0,-1),(1,0),(-1,0)] #움직일 수 있는 방향
maze = [list(map(int,sys.stdin.readline().strip())) for _ in range(N)]
visited = [[False]*M for _ in range(N)] #방문 기록

queue = deque()
queue.append((0,0,1)) #시작 지점 삽입
visited[0][0] = True #시작 지점 방문 처리

while queue:
    x, y, distance = queue.popleft() #현재 위치와 거리 꺼내기

    if x==N-1 and y==M-1: #도착하면 지나온 칸 수 출력
        print(distance)

    for nx,ny in move: #갈 수 있는 방향 모두 시도
        mx, my = x+nx, y+ny #현재 위치+갈 방향

        if 0<=mx<N and 0<=my<M: 
            if maze[mx][my] == 1 and not visited[mx][my]:
                visited[mx][my] = True
                queue.append((mx,my,distance+1))

 

 

이제 BFS가 좀 이해되는 것 같다.

좀 더 연습해야지.