[python] 백준 14940번: 쉬운 최단거리(BFS)

# 14940 쉬운 최단거리

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

14940번: 쉬운 최단거리

⭐ 코드

import sys
input = sys.stdin.readline

from collections import deque
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[-1] * M for _ in range(N)]
dx, dy = [0,0,-1,1], [-1,1,0,0]

def bfs(i,j):
    queue = deque()
    queue.append((i,j))

    visited[i][j] = 0

    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:
                if graph[nx][ny] == 0: 
                    visited[nx][ny] = 0
                elif graph[nx][ny] == 1:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx,ny))

for i in range(N):
    for j in range(M):
        if graph[i][j] == 2 and visited[i][j] == -1:
            bfs(i,j)

for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            print(0, end=' ')
        else:
            print(visited[i][j], end=' ')
    print()

📝 풀이

갈 수 있는 땅과 갈 수 없는 땅을 잘 구분해서 visited에 기록해주고 목표지점인 2를 만났을 때 bfs를 실행시켜주면 된다. graph와 visited를 잘 구분해서 기록해주는것이 핵심이다.

🔓 정답 코드 뜯어보기

from collections import deque
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)] # 그래프 생성
visited = [[-1] * M for _ in range(N)] # 방문기록
 
 # 방향탐색 범위설정
dx, dy = [0,0,-1,1], [-1,1,0,0]

# graph
# [
# [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
# ]

BFS를 사용하기 위해 deque를 불러와주고, 그래프를 생성하기 위해 N만큼 반복문을 실행시켜준다. 위와 같이 그래프가 생성되게 되고, 방문기록을 할 visited를 생성해준다.

def bfs(i,j):
    queue = deque()
    queue.append((i,j))

    visited[i][j] = 0

    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:
                if graph[nx][ny] == 0: # 갈 수 없는 땅 체크
                    visited[nx][ny] = 0
                elif graph[nx][ny] == 1: # 갈 수 있는 땅 체크
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx,ny))

deque을 담아줄 queue를 생성해주고, 시작지점을 queue에 넣어준다. 처음 시작하는 i,j를 visited에 기록시켜준다. queue가 빌 때까지 while문을 실행시켜주면서 방향 탐색을 진행시켜준다. nx, ny가 범위내에 있고 visited[nx][ny]가 -1이라면(방문하지 않은 곳이라면) 갈 수 없는 땅(0)과 갈 수 있는 땅(1)에 따라 if문을 걸어준다.

 

갈 수 없는 땅이면 visited[[nx][ny]를 0으로 저장시켜주고, 갈 수 있는 땅이라면 방향탐색 전에 위치값에 +1을 더해서 visited[nx][ny]에 기록해준다. 탐색을 했으므로 다음 탐색을 위해 queue에 현재 좌표를 삽입시켜준다.

for i in range(N):
    for j in range(M):
        if graph[i][j] == 2 and visited[i][j] == -1:
            bfs(i, j)

for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            print(0, end=' ')
        else:
            print(visited[i][j], end=' ')
    print()

bfs를 생성했으니 for문을 통해서 목표지점일때, 그리고 visited[i][j]가 -1일 때(방문하지 않았을 때) bfs를 실행시켜준다. 그 후 이중 반복문을 돌면서 조건문을 통해 graph[i][j]가 0일때(방문을 못하는 땅)와 방문했던 곳 일때(visited[i][j])를 출력시켜준다.