[Python] 백준2178번 :미로 탐색

💡문제

백준 2178번 문제 링크

🍀풀이

이 문제가 이제 최단경로를 구하는 문제인거 같다. 이 문제는 방문여부를 체크하지 않고 값이 1인 곳을 지날때마다 카운트 해줘서 수를 구하면 된다. BFS 풀이는 똑같다!

내가 푼 코드

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
dist = [[-1] * m for _ in range(n)]

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    dist[x][y] = 0  # 시작점 거리 초기화
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1 and dist[nx][ny] == -1:
                    queue.append((nx, ny))
                    dist[nx][ny] = dist[x][y] + 1
    return dist[n-1][m-1]+1

print(bfs(0, 0))

사실 바킹독 개념 영상을 보면서 기억하는대로 푼거였는데 거기에서는 dist 배열을 둬서 -1로 초기화를 하고 지나갈때마다 이 값을 +1을 한다음 마지막에 다시 +1을 해주는 형태로 해서 그대로 했는데 하면서 든 생각이 그냥 0으로 초기화를 해도 될거 같다는 생각을 했다.

또한 풀고 나서 다른 사람 코드를 봤는데 이렇게 dist배열을 따로 선언 하지 않고 graph 배열을 사용하는 식으로 많이 한걸 봤다. 시간은 똑같이 걸리지만 더 간단한거 같아서 또 풀어봤다.

다른 사람 코드

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx, ny))
    return graph[n-1][m-1]

print(bfs(0, 0))

푸는건 비슷하다!