2178번 - 미로 탐색

💡b

import sys
from collections import deque

input = sys.stdin.readline

N ,M = map(int,input().split(' '))
graph = []
visited = [[False] * M for _ in range(N)]

for _ in range(N):
    graph.append(list(map(int,input().rstrip())))
    
def bfs():

    dq = deque()
    
    dq.append((0,0,1))
    visited[0][0] = True
    
    # 상 하 좌 우
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    
    while dq:
        x, y, cnt= dq.popleft()
        
        # 목적지에 도달하면 종료
        if x == M-1 and y == N-1:
            return cnt
        
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
            
            if 0 <= nx < M and 0 <= ny < N and graph[ny][nx] == 1 and visited[ny][nx] == False:
                visited[ny][nx] = True
                dq.append((nx,ny,cnt+1))
            
print(bfs())

• 위 문제도 사실 일반적인 BFS의 유형 중 하나였다.
• 다만 최소의 칸수를 구해야하기 때문에, 어떤 방식으로 진행하면 좋을지 고민을 많이 하였다.
• 나는 따로 dq안에 (x좌표, y좌표, 현재위치에 도달하는데 걸린 비용) 이렇게 3가지를 넣어주면서 계산하였다.
• 핵심 포인트는 최종 위치가 (N,M)에 도달하면 바로 탈출해서 걸린 비용을 계산해야 한다.(bfs이기 때문에, N,M에 최솟값을 가진다.)

💡 코테 스터리에서 나온 기발한 풀이법

혜진

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배열을 따로 선언해서 움직일 떄마다 걸린 거리의 숫자를 하나씩 증가시켜주는 방식
=> 생각해보면 그냥 graph에 바로 +1을 하여서 N,M에 도달했을떄의 숫자를 출력해도 괜찮을거 같다.