[파이썬] 백준 14940 : 쉬운 최단거리 (실버1)

백준 14940 : 쉬운 최단거리 (실버1)

 

14940번: 쉬운 최단거리

---

문제

---

풀이

 

0. 방향성 생각

최단 거리를 요구하는 문제이기 때문에 BFS로 접근해야함을 알 수 있다.

또한 배열의 크기가 1000x1000이기 때문에 재귀를 통한 DFS 구현 시 시간이 오래 소요됨을 유추할 수 있다.

 

1. 입력 받기

import sys
from collections import deque
h,w = map(int,sys.stdin.readline().split())
arr = []

for i in range(h):
    temp = list(map(int,sys.stdin.readline().split()))
    arr.append(temp)
    if 2 in temp :
        x = temp.index(2)
        y = i

입력이 들어오는 도중 목표지점인 2의 위치를 찾아서 x,y에 할당해주자.

 

2. 배열 생성 및 방향 정의

visit = [[False]*w for i in range(h)]
answer = [[0]*w for i in range(h)]
step = [[1,0,-1,0],[0,1,0,-1]]

방문 유무를 체크할 visit, 답을 작성할 answer 어레이를 arr의 크기와 똑같이 만들어준다.

또한 상하좌우 4방향으로 탐색을 진행하기 때문에 step 내부에 x방향, y방향을 따로 정의해준다.

 

3. BFS 함수 정의

def bfs(x,y):
    # 1)
    q = deque()
    q.append([x,y])
    visit[y][x] = True
    answer[y][x] = 0
    
    # 2)
    while q:
        now = q.popleft()
        
        for i in range(4):
            next_x = now[0]+step[0][i]
            next_y = now[1]+step[1][i]
            
            # 3)
            if (0<=next_y<h) and (0<=next_x<w) and visit[next_y][next_x] == False :
                if arr[next_y][next_x] == 0 :
                    answer[next_y][next_x] = 0
                    
                elif arr[next_y][next_x] == 1 :
                    visit[next_y][next_x] = True
                    answer[next_y][next_x] = answer[now[1]][now[0]] + 1
                    q.append([next_x,next_y])
    # 4)                
    for i in range(h):
        for j in range(w):
            if visit[i][j] == False and arr[i][j] == 1:
                answer[i][j] = -1

1) 위에서 탐색한 x,y로부터 거리를 측정하므로 시작 시 큐에 x,y 좌표를 넣어주고 방문처리를 한 후 시작점이므로 answer에 0을 할당한다.

 

2) while문 내부에서 popleft를 통해 나온 현재 위치를 받고 탐색할 위치를 받아준다.

BFS 함수 내부에서는 DFS와 다르게 재귀적으로 호출하지 않기 때문에 BFS 함수 내부에서 4방향에 대한 탐색을 진행할 때 for문을 사용한다.

 

3) 주어진 인덱스가 arr 내부에 있고 아직 탐색하지 않았을 경우 탐색을 진행한다.

탐색하지 못하는 경우(=arr의 다음 좌표가 0인 경우) answer에서도 0을 표시해준다

탐색이 가능한 경우 방문처리를 해주고 현재 좌표의 거리 +1을 해준다. 또한 탐색이 가능하므로 큐에 넣어서 다음 탐색 후보군에 넣는다.

 

4) 원래 갈수 있는 곳 중에서 0 때문에 막혀서 탐색하지 못한 경우가 발생하게 된다.

visit이 False이고 arr이 1인 경우인데 이를 문제의 조건에 따라서 answer의 좌표에서 -1을 할당해준다.

 

4. 출력하기

bfs(x,y)
for i in answer :
    print(*i)

BFS를 진행하고 리스트를 언패킹해주는 *를 통해서 출력한다.

 

---

전체 코드

import sys
from collections import deque
h,w = map(int,sys.stdin.readline().split())
arr = []
for i in range(h):
    temp = list(map(int,sys.stdin.readline().split()))
    arr.append(temp)
    if 2 in temp :
        x = temp.index(2)
        y = i

visit = [[False]*w for i in range(h)]
answer = [[0]*w for i in range(h)]
step = [[1,0,-1,0],[0,1,0,-1]]

def bfs(x,y):
    q = deque()
    q.append([x,y])
    visit[y][x] = True
    answer[y][x] = 0
    
    while q:
        now = q.popleft()
        
        for i in range(4):
            next_x = now[0]+step[0][i]
            next_y = now[1]+step[1][i]
            
            if (0<=next_y<h) and (0<=next_x<w) and visit[next_y][next_x] == False :
                if arr[next_y][next_x] == 0 :
                    answer[next_y][next_x] = 0
                    
                elif arr[next_y][next_x] == 1 :
                    visit[next_y][next_x] = True
                    answer[next_y][next_x] = answer[now[1]][now[0]] + 1
                    q.append([next_x,next_y])
                    
    for i in range(h):
        for j in range(w):
            if visit[i][j] == False and arr[i][j] == 1:
                answer[i][j] = -1

bfs(x,y)
for i in answer :
    print(*i)