BOJ 2178번 : 미로 탐색 (Python/Silver 1)

2178번: 미로 탐색

---

설명

위 사진은 미로를 나타낸 것이다. 1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸이다. Start칸에서 End칸까지 가야하는데, 지나갈 수 있는 최소의 칸을 구하면 된다. 주황색 형광으로 칠한 곳이 지나갈 수 있는 최소 칸 개수를 센 것이다. 칸 개수를 셀 때 시작칸과 마지막칸도 포함된다. 그럼 이제 문제를 풀어보자!

 

풀이

BFS 이용

1. 파이썬에서 BFS를 구현하기 위해서는 큐가 필요하다. 따라서 큐를 만든다.

파이썬 덱 모듈 내에 스택과 큐가 내장돼 있어서 사용하기 편한 덱 모듈을 가져온다. 

from collections import deque
import sys
input = sys.stdin.readline #입출력 향상

2. 미로를 표현하기 위해 이중 리스트를 생성한다.

N, M = map(int, input().split()) #N = 행, M = 열
graph = []
for _ in range(N): #행
    #이중 리스트 생성
    graph.append(list(map(int, input().rstrip()))) #rstrip() = 마지막 개행 문자 제거

#리스트가 잘 만들어졌는지 확인용으로 출력
for i in range(N):
    print(graph[i])

출력 결과

graph라는 리스트를 하나 만들고 graph 안에 또 다른 리스트를 만들어준다. 입력받는 데이터를 리스트 안에 집어넣고 그 리스트를 graph 리스트에 다시 집어넣도록 만들었다.

리스트가 잘 만들어졌는지 확인해보면(출력 결과) 문제 예시와 똑같이 미로가 표현된 것을 볼 수 있다. 

 

3. 미로를 탐색할 때 지나갈 수 있는지 확인하기 위한 변수 dx, dy 생성

BFS 알고리즘을 구현하기 전에 필요한 변수가 있다. (BFS 함수 내에서 해도 되지만 편의상 먼저 정의)

만약 3x3 미로(좌측 그림)가 있다고 가정하자. (0, 0)에서 지나갈 수 있는 길인지 확인하기 위해서는 현재위치에서 주변을 다 확인해봐야 하는데, 문제에서 인접한 칸으로만 이동할 수 있다고 했으므로 대각선을 제외한 상하좌우만 확인해보면 된다.

확인하는 방법은 현재 위치에서 다른 위치로 이동하면서 해야 한다. 상하좌우 4개의 데이터만 필요하므로 x, y 변수에 각 네 개의 값만 넣는다. 맨 우측의 그림을 보면 좌표로 나타낸 것을 볼 수 있는데, 이는 현재 위치에서 한 칸을 이동했을 때의 좌표를 나타낸 것이다. 그럼 dx에 x좌표만 저장하면 되므로 [(좌)-1, (우)1, (상)0, (하)0], 그리고 dy에는 y좌표인 [(좌)0, (우)0, (상)1 (하)-1] 이렇게 저장한다. 필자는 좌우하상 순대로 저장했지만, 본인이 편한 순서대로 저장하면 된다. (단 x와 y 모두 순서에 맞게 저장해야 한다. 즉, x는 좌우하상인데 y는 좌우상하 이런식으로 저장하면 안 된다는 것이다.)

#상하좌우를 다 확인하기 위한 걸 추가 (아래는 좌우상하 순대로 저장)
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

4. BFS 구현

def BFS(x, y):
    q = deque() #덱 생성
    q.append((x, y)) #초기 위치

파이썬에서는 함수를 정의하려면 def를 쓰면 된다. BFS 함수 인수에 좌표값(0, 0)을 넣어야 하므로 x와 y를 쓴다. 다음으로는 큐를 사용하기 위해 덱을 생성한다. 덱의 이름은 q라고 정의했다. 그리고 초기 위치를 q에 넣는다.

    while q:
        x, y = q.popleft()  # 꺼내기

        # 좌우상하에 길이 있는지 좌표 이동하면서 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

이제  좌표를 이동시키면서 길을 찾는다. popleft()는 덱의 가장 왼쪽에 있는 걸 빼내고 삭제한다. 덱에 있는 현재 좌표를 꺼내서 x, y에 저장한다. 다음으로는 현재 좌표에서 상하좌우를 확인한다. 

            # 미로 밖으로 벗어나면 안 되기 때문에 벗어나면 무시한다.
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

그러나 미로 밖으로 벗어날 수도 있다. 위의 그림(3번)에서 현재 좌표가 (0, 0) 일 때 상하좌우를 확인하면 X표시 된 것을 볼 수 있는데 그건 미로 밖에 있기 때문에 값이 없다고 표시한 것이다. 따라서 미로를 벗어나면 무시하는 코드를 넣어줬다. 

            # 길(1)이 발견되면 해당 칸으로 좌표 이동
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1 #이동할 수 있는 칸의 개수 카운트
                q.append((nx, ny))  # 이동된 nx, ny를 queue에 집어 넣기

상하좌우를 확인하다가 길(1)이 발견되면 해당 칸으로 이동한다. 만약 현재 좌표가 (0, 0)일 때 graph[0][0]이고 이 값은 현재 1이다. 여기에 1을 더해서 칸의 개수를 센다. 그리고 이동된 좌표를 다시 큐에 넣는다. 이동된 좌표가 현재 위치가 된다.

상하좌우를 다 확인했으면 다시 큐에서 현재 위치를 꺼내서 End칸에 도착할 때까지 위의 과정을 반복한다.  

return graph[N - 1][M - 1]  # 최종 n, m 위치에서의 graph 값 즉, 최소 거리를 반환함

while문이 끝났으면 결과값을 반환한다. 이동한 칸의 개수를 확인하려면 graph의 End칸의 위치를 반환하면 된다. 아래에 전체 코드가 있으므로 확인해보자.

 

Solution (전체 코드)

import sys
input = sys.stdin.readline #입출력 향상
from collections import deque

N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input())))

#좌우상하
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
    
def BFS(x, y):
    q = deque() #큐 생성
    q.append((x,y)) # x = 0, y = 0 -> deque([(0, 0)])

    while q:
        x, y = q.popleft() # x = 0, y = 0 -> (0, 0)

        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                q.append((nx, ny))

    return graph[N-1][M-1]

print(BFS(0, 0)) #결과 출력

✧ 2023-02-19 20:44 -> 23.05.13 풀이 설명 재수정