[Python] 백준, 2178(BFS)

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

2178번: 미로 탐색

어제 문제 풀 때만 해도 아 이런 느낌이구나 하는 감이 왔었는데, 문제가 조금만 달라지면 그 느낌도 초기화가 되나 보다. 경건한 마음으로 구글링의 도움을 받았다. 100% 이해 완료하긴 했는데, 뭔가 비효율적인 것 같으면서도 거의 모든 풀이가 단일화되어 있는 걸 보면 이게 가장 좋은 풀이인가 싶은 의문이 든다. 

 

풀이가 굉장히 알고리즘스러운데, dx, dy의 설정으로 상하좌우의 경우를 생각해주는 건 진짜 괜찮은 방법인 것 같다. 코드도 나름 직관적이어서 이해하기 괜찮지 않을까 싶다. 

 

collections모듈의 deque를 사용하는 것과 리스트 메소드를 사용하는 방법 두 가지가 있는데 이 경우에는 후자가 훨씬 효율적인 것 같아 두 가지 모두 소개하겠다.

 

 

 

# PYTHON CODE (1) - deque모듈

from collections import deque
import sys

n, m = map(int, sys.stdin.readline().split())

tree = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

queue = deque()
queue.append([0,0])

while queue:
    x, y = queue.popleft()

    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 tree[nx][ny] == 0:
            continue

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

print(tree[n - 1][m - 1])

 

 

# PYTHON CODE (2) - 리스트 메소드

import sys

n, m = map(int, sys.stdin.readline().split())

tree = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

queue = [[0, 0]]

while queue:
    x, y = queue[0][0], queue[0][1]
    del queue[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 tree[nx][ny] == 0:
            continue

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

print(tree[n - 1][m - 1])