[BOJ - BFS] 14940번 : 쉬운 최단거리 ( python )

백준 너비우선탐색 14940 쉬운 최단거리 파이썬

 

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

14940번: 쉬운 최단거리

 

 

문제

 

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

 

 

 

 

1. 이 문제를 공유한 이유 : 반례

 

틀린코드를 먼저 보여주면서 사고했던 과정을 소개한다. 

 

시작부분을 1로설정, 원래못가는 곳을 -100으로 체크해두고

갈수 있는 곳을 1씩 증가시키면서 코드를 작성했다.

 

 

아래의 bfs 함수 코드를 확인해보면

결과적으로 visited라는 변수엔

시작위치 == 1

갈수 있는 곳 == 1이상의 숫자

원래 갈수 없는 곳 == -100

bfs를 아예 들어가지 않음 == False가 되고

bfs 이후 후처리를 통해 출력을 해주는 코드이다.

 

 (틀린코드) 

from collections import deque
import sys
input = sys.stdin.readline

d = [[1,0],[-1,0],[0,1],[0,-1]]

def bfs(y,x):  
    queue = deque()
    queue.append([y,x])
    
    visited[y][x] = 1
    
    while queue:
        r, c =  queue.popleft()
        
        for i in range(4):
            rr = r+d[i][0]
            cc = c+d[i][1]
            
            if (0<=rr<n) and (0<=cc<m) and not visited[rr][cc]:
                if graph[rr][cc] == 0:
                    visited[rr][cc] = -100 #원래 못가는 곳.
                elif graph[rr][cc] == 1:
                    visited[rr][cc] = visited[r][c] +1
                    queue.append([rr,cc])

n, m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]

for i in range(n):
    for k in range(m):
        if graph[i][k] == 2 and not visited[i][k]:
            bfs(i,k)
            
for i in range(n):
    for k in range(m):
        if visited[i][k] == -100:
            visited[i][k] = 1 #지금 전체적으로 1씩 증가되어있기 때문에 마지막에 1을 뺴줘야하고,  0으로 설정해주려고 1로설정.
        elif visited[i][k] == False:
            visited[i][k] = 0
        
        visited[i][k] -=1


for i in range(n):
    print(" ".join(map(str,visited[i])))

 

 

이 코드는 테스트케이스엔 완벽하게 돌아갔지만 실패했다고 떴다.

 

반례를 찾아보니 이와 같은 문제가 있었다. 

 

원래 갈 수 없는 땅인 위치는 0 과 원래갈수 있지만 도달할 수 없는 위치 -1을 출력해야하는데

원래 갈 수 없는데 도달할 수 없는 위치를 -1로 출력해버리는 것.

 

 

 

처음부터 갈수 없음에도 불구하고 False가 되어서 나중에 -1을 출력하는 경우가 생겼다. 

visited로 전부 체크하지 말고, 차라리 출력 해줄 때엔 graph[i][k] ==0인지 체크하고 0이라면 출력해주는 코드가 필요할 것 같았다.  

 

 

2. 사고하기

틀린김에 후처리 해주는것도 마음에 안들고 해서 아예 코드를 더욱더 심플하게 바꿨다.

visited = 전체 -1로 설정해서 후처리를 안할 수 있도록 했다.

 

if (0<=rr<n) and (0<=cc<m) and visited[rr][cc] == -1:

방문할 땅을 고르는 코드는, 갈수 있는 땅이고, 방문아직 안한(-1) 인곳이었기 때문에

두가지 조건이 필요했다.

1) 갈수 없는 땅(0) 일경우 방문처리 0으로 해주기

2) 갈수 있는 땅(1) 인경우 이전 위치에서 +1 하면서 방문처리 및 큐에 좌표 삽입

 

마지막으로 처음부터 갈수 없음에도 불구하고 False가 되어서 나중에 -1을 출력하는 경우를 방지하기 위하여

 

<출력>

1) graph[i][k] ==0인지 체크 > 0이라면 0 출력 

2) 0이 아니라면 visited 출력

 

정답 코드

#14940_쉬운 최단거리_bfs_gold5

from collections import deque
import sys
input = sys.stdin.readline

d = [[1,0],[-1,0],[0,1],[0,-1]]

def bfs(y,x):  
    queue = deque()
    queue.append([y,x])
    
    visited[y][x] = 0
    
    while queue:
        r, c =  queue.popleft()
    
        for i in range(4):
            rr = r+d[i][0]
            cc = c+d[i][1]
            
            if (0<=rr<n) and (0<=cc<m) and visited[rr][cc] == -1: 
                if graph[rr][cc] == 0: #갈수없는 땅 체크
                    visited[rr][cc] = 0
                elif graph[rr][cc] == 1: # 갈수있는땅 체크
                    visited[rr][cc] = visited[r][c] +1
                    queue.append([rr,cc])

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

for i in range(n):
    for k in range(m):
        if graph[i][k] == 2 and visited[i][k]== -1:
            bfs(i,k)

for i in range(n):
    for k in range(m):
        if graph[i][k] == 0:
            print(0, end= " ")
        else:
            print(visited[i][k], end = " ")
            
    print()