[백준] 2178 파이썬(python) : 미로 탐색

2178번 : 미로 탐색

 

 

그래프이론 문제 중에서도 너비 우선 탐색을 하는 bfs문제다. 파이썬에서는 deque라이브러리를 import해와서 사용한다. 너비 우선 탐색에 대해서는 조만간 포스팅 해보겠다.

 

첫번째 풀이)

from collections import deque
n, m = map(int, input().split())
graph = [ list(map(int, input())) for _ in range(n) ] #1
d = [ (-1, 0), (1, 0), (0, -1), (0, 1) ] #2
q = deque() #3
q.append((0,0)) #4
def bfs():
    while q: #5
        x, y = q.popleft() #6
        for i in range(4): #7
            dx = x + d[i][0] #8
            dy = y + d[i][1]
            if 0 <= dx < n and 0 <= dy < m: #9
                if graph[dx][dy] == 1: #10
                    graph[dx][dy] = graph[x][y] + 1 #11
                    q.append((dx, dy)) #12

bfs() 
print(graph[n-1][m-1]) #13

 

#1 : 문제에서 원하는 그래프의 형태를 한줄짜리 코드로 만드는 방법이다. 이전에는 2차원 리스트도 만들고 또 입력값 받는것도 따로 했는데 이제는 두 가지를 한번에 받는 형태로 코드를 짜야겠다.

#2 : 각각의 원소마다 "북, 동, 남, 서"를 표현한다. #8과 함께 사용된다.

#3 : 변수 q를 선언하고 deque로 초기화

#4 : bfs를 실행하기전 처음위치인 (0, 0)을 리스트 q에 넣어준다.

#5 : 리스트 q에 원소가 하나도 남지 않을때까지 반복한다.

#6 : q의 가장 첫번째 원소를 꺼내서 x, y에 대입한다. 맨 처음에 들어가 있는 원소는 (0, 0)이니까 x = 0, y = 0이 된다.

#7 : 4번 반복한다. 4번 반복하는 이유는 리스트 d에서 "북, 동, 남, 서"를 하나씩 방문해 주기 위해서이다. for i in range(len(d)): 이렇게 적어도 결과는 같다.

#8 : 리스트 d의 원소들을 현재 위치에 더해서 새롭게 진행할 수 있는 위치로 만든다.

#9 : 새롭게 진행할 위치 dx, dy가 그래프의 범위 안에 있으면

#10 : 그리고 새로운 위치의 값이 1이면(움직일 수 있는 거리이면)

#11 : 이전 위치(x, y)에서 +1을 해서 시작위치(그래프에서 0,0)에서 새로운 위치까지의 거리를 만든다.

#12 : 그리고 리스트 q에 새로운 위치 dx, dy를 튜플로 추가해준다.

#13 : graph[n-1][m-1]은 도착위치를 의미하므로 출력한다.

 

 

처음 글을 적은 후 몇일이 지났는데 다른 풀이를 적어볼까 한다. 다음 글들에서 나오는 코드들과의 풀이법 통일을 위해 이렇게 두번째 코드를 적었다. 결과는 같다.

 

두번째 풀이)

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n) ] #1
dx = [ 0, 0, -1, 1 ] #2
dy = [ -1, 1, 0, 0 ]
q = deque() #3
q.append((0, 0)) #4

def bfs():
    while q: #5
        x, y = q.popleft() #6
        for i in range(4): #7
            nx = x + dx[i] #8
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1: #9, 10
                graph[nx][ny] = graph[x][y] + 1 #11
                q.append((nx, ny)) #12
bfs()
print(graph[n-1][m-1]) #13