[Python][백준/BOJ] 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 = [[0]*m for _ in range(n)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs(x, y):
    visited[x][y] = 1
    graph[x][y]=0
    q = deque()
    q.append((x,y))
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<m and graph[nx][ny] ==1 and visited[nx][ny] == 0:
                visited[nx][ny] =1
                q.append((nx,ny))
                graph[nx][ny]=graph[x][y]+1
x, y =0,0
for i in range(n):
    for j in range(m):
        if graph[i][j] ==2:
            x, y = i, j
bfs(x, y )
for i in range(n):
    for j in range(m):
        if graph[i][j] ==1 and visited[i][j] == 0:
            graph[i][j] = -1
    
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            print(0, end =' ')
        else:
            print(graph[i][j], end =' ')
    print()

 

코드 리뷰

BFS

처음에는 완전 쉬운 문제라고 생각하고, 일반적인 BFS 문제랑 다르지 않겠거니 생각했다. 하지만 웬걸,,풀다보니 내가 조금 이상하게 접근한 부분들이 있었는지 도중 오류가 발생했다.. not visited를 사용하지 않고 정확하게 고쳐보니 결국 맞았다. 하나하나 뜯어보자.

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

bfs 함수는 기본적인 함수와 같다. visited를 통해 검사하고, graph에 1이 적혀있는 곳만 방문한다는 것만 이용해서 방문해준다. graph의 값이 0인 곳은 방문하지 않아야 하기 때문에 반드시 조건 안에 graph가 1인지 검사하는 것을 넣어주어야 한다!

 

n, m = map(int, input().split())
graph =[list(map(int, input().split()))for _ in range(n)]
visited = [[0]*m for _ in range(n)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
x, y =0,0

이건 기본 세팅 값이다. visited를 0으로 리셋하고, graph는 입력받은 대로 list로 저장하였다.

 

여기서 조금 꼬였는데 어쩌다보니 for문이 3개나 생기게 되었다. 

for i in range(n):
    for j in range(m):
        if graph[i][j] ==2:
            x, y = i, j
bfs(x, y )

 

먼저 첫번째 for문은 2인 목표 지점을 찾는 것이다. 목표 지점은 단 하나밖에 없기 때문에 저 상태에서 break를 하든 안하든 결과는 같다. 그리고 찾은 좌표를 bfs 함수에 넣어서 돌려준다. 그러면 graph의 2인 좌표를 중심으로 숫자는 퍼져나가게 된다.

 

for i in range(n):
    for j in range(m):
        if graph[i][j] ==1 and visited[i][j] == 0:
            graph[i][j] = -1

두 번째 for문은 방문할 수 없는 곳을 -1로 표시하라는 문제의 조건을 따르는 코드다. bfs를 통해 graph를 한 바퀴 다 돌았음에도 불구하고 visited가 0인(방문하지 않은) 좌표를 구한다. 그래서 그 지점은 문제의 조건에서 요구하는 대로 -1로 설정한다.

 

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            print(0, end =' ')
        else:
            print(graph[i][j], end =' ')
    print()

그리고 마지막 for문은 graph의 값이 0이면 0 그대로 표시해주고, 나머지는 생긴 대로 출력해주는 정직한 코드이다.

조건을 따르는 부분에서 조금 오류가 발생했는데, 그것 빼고는 다른 bfs 문제와 비슷했던 문제였다.