[Silver I] 쉬운 최단거리 - 14940

[Silver I] 쉬운 최단거리 - 14940

문제 링크

성능 요약

메모리: 41792 KB, 시간: 680 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 10월 31일 11:54:41

문제 설명

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

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

입력

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

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

출력

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

 

풀이

import sys

from collections import deque

N , M = map(int, sys.stdin.readline().split())

mat = [[w for w in map(int, sys.stdin.readline().split())] for _ in range(N)]
dis = [[0 for _ in range(M)] for __ in range(N)]
visited = [[False] * M for __ in range(N)]

def bfs(mat, x,y):
    q = deque()
    q.append([x,y])
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    visited[x][y] = True
    
    while(q):
        x , y = q.popleft()
        
        for i in range(4):
            mx = x + dx[i] # 세로 
            ny = y + dy[i] # 가로

            if(mx < 0 or mx >= N or ny < 0 or ny >= M):
                continue
            
    
            elif(mat[mx][ny] == 0):
                visited[mx][ny] = True
                continue
            
                
            elif(mat[mx][ny] == 1 and visited[mx][ny] == False):
                dis[mx][ny] = dis[x][y] + 1
                visited[mx][ny] = True
                q.append([mx,ny])
                
            
        
for x in range(N):
    for y in range(M):
        if(mat[x][y]==2):
            bfs(mat, x,y)
            break
    

for x in range(N):
    for y in range(M):
        if(visited[x][y]==False):
            dis[x][y] = -1
        

        
for x in range(N):
    for y in range(M):
        print(dis[x][y], end = ' ')
    print()

처음에는 위와 같은 코드는 테스트 케이스는 성공했지만 답은 틀렸다라는 결과가 나왔다.

elif(mat[mx][ny] == 0):
      visited[mx][ny] = True
      continue

그 이유는 mat[mx][ny] == 0 조건에 대해서 visited[mx][ny] = True를 시키고 co queue에 더 이상 좌표값이 채워지지 않아서 전체 0에 해당하는 곳의 가로 세로를 방문하지 않기 때문이었다.

이는 테스트 케이스를 임의적으로 추가해보면서 알게 되었다.

• 테스트 케이스

5 5
1 1 1 0 1
1 0 0 0 1
1 0 2 0 1
1 0 0 0 1
1 1 1 1 1

• 옳은 결과

1 -1 -1 0 -1 
-1 0 0 0 -1 
-1 0 0 0 -1 
-1 0 0 0 -1 
-1 -1 -1 -1 -1 

• 나의 결과

-1 -1 -1 -1 -1 
-1 -1 0 -1 -1 
-1 0 0 0 -1 
-1 -1 0 -1 -1 
-1 -1 -1 -1 -1 

따라서 방문가능하지만 0 때문에 막혀 방문하지 않은 곳(즉 방문하지 않은 곳)을 -1로 바꾼뒤에, 결과 출력시 원래의 매트릭스가 0이라면 0을 출력하도록 했다. 이는 비효율적인 처리이기에 좌표를 처음부터 -1로 초기화 했다.

• 리팩터링

import sys

from collections import deque

N , M = map(int, sys.stdin.readline().split())
mat = []

mat = [[w for w in map(int, sys.stdin.readline().split())] for _ in range(N)]
dis = [[-1 for _ in range(M)] for __ in range(N)]
visited = [[False] * M for __ in range(N)]

def bfs(mat, x,y):
    q = deque()
    q.append([x,y])

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

    dis[x][y] = 0
    visited[x][y] = True

    while(q):
        x , y = q.popleft()

        
        
        for i in range(4):
            mx = x + dx[i] # 세로 
            ny = y + dy[i] # 가로

            if(mx < 0 or mx >= N or ny < 0 or ny >= M):
                continue
            
    
            elif(mat[mx][ny] == 0):
                visited[mx][ny] = True
                continue
            
                
            elif(mat[mx][ny] == 1 and visited[mx][ny] == False):
                visited[mx][ny] = True
                dis[mx][ny] = dis[x][y] + 1
                q.append([mx,ny])
                
            
        
for x in range(N):
    for y in range(M):
        if(mat[x][y]==2):
            bfs(mat, x,y)
            break
    

for x in range(N):
    for y in range(M):
        if mat[x][y] == 0:  # 갈 수 없는 땅은 거리 0
            print(0, end=' ')
        else:
            print(dis[x][y], end=' ')
    print()

• 각 거리를 -1로 초기화한 뒤 bfs에 해당 좌표가 큐에 들어오게 되면 0으로 초기화하여 -1에 대한 방문을 관리하였다.