[백준] 14940 쉬운 최단거리 [python]

 

 

 

문제 풀이

1️⃣ 목표지점 2를 찾아서 위치를 저장해둡니다.

2️⃣ 1의 값들을 전부 -1로 바꿔줍니다.

3️⃣ 찾아놓은 목표지점 위치부터 시작해서 bfs 그래프 너비 탐색을 통해서 이동할 수 있는 부분들을 탐색합니다.

4️⃣ 전체 탐색하고 탐색하지 못한부분은 -1로 그대로놔둡니다.

5️⃣ arr에 저장되어있는 값을 출력형식에 맞게 출력합니다.

 

 

 

 

전체 코드

from sys import stdin as s
from collections import deque
s=open('input.txt','rt')

# bfs 함수부분
def bfs(si,sj):
    q=deque()
    q.append((si,sj))
    v[si][sj]=1
    
    # 4방향 탐색위한 방향설정
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    
    while q:
        ci,cj = q.popleft()
        
        for i in range(4):    
            nx = ci+dx[i]
            ny = cj+dy[i]
            
            # 범위 설정
            if 0<=nx<N and 0<=ny<M and not v[nx][ny] and arr[nx][ny]==-1:
                v[nx][ny]=1
                # 이전 arr의 값에 +1씩 증가
                arr[nx][ny] = arr[ci][cj]+1
                q.append((nx,ny))
    
if __name__=='__main__':
    N,M = map(int,s.readline().split())
    ans=[]
    arr = [list(map(int,s.readline().split())) for _ in range(N)]
    v = [[0]*M for _ in range(N)]
    
    # 탐색하기전에 2인 값은 따로 저장해두고 나머지는 -1로 저장 
    # -> 나중에 전체 탐색했을 때 갈 수 없는 곳이면 -1을 출력해야하기 때문
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 2:
                ans.append((i,j))
            if arr[i][j] == 1:
                arr[i][j] = -1
    arr[ans[0][0]][ans[0][1]]=0
    bfs(ans[0][0],ans[0][1])
    
    
    # arr에 저장해둔 값들을 join을 이용해서 원하는 출력값으로 출력
    for row in arr:
        print(" ".join(map(str,row)))