[백준] 14940번 : 쉬운 최단거리 (python 파이썬)
https://www.acmicpc.net/problem/14940
처음에는
import sys
def func(x,y):
if y+1 < m:
if l[x][y+1] == 1:
l[x][y+1] = l[x][y] +1
func(x,y+1)
elif l[x][y]+1 < l[x][y+1]:
l[x][y+1] = l[x][y]+1
func(x,y+1)
if x+1 < n:
if l[x+1][y] == 1:
l[x+1][y] = l[x][y] +1
func(x+1,y)
elif l[x][y]+1 < l[x+1][y]:
l[x+1][y] = l[x][y]+1
func(x+1,y)
if y-1 >= 0:
if l[x][y-1] == 1:
l[x][y-1] = l[x][y] +1
return func(x,y-1)
elif l[x][y]+1 < l[x][y-1]:
l[x][y-1] = l[x][y]+1
func(x,y-1)
if x-1 >= 0:
if l[x-1][y] == 1:
l[x-1][y] = l[x][y] +1
return func(x-1,y)
elif l[x][y]+1 < l[x-1][y]:
l[x-1][y] = l[x][y]+1
func(x-1,y)
def print_l(l):
for i in l :
for j in i:
print(j,end=" ")
print()
n, m = map(int, sys.stdin.readline().split(" "))
l = []
x,y = 0, 0
for i in range(n):
l2 = list(map(int, sys.stdin.readline().split(" ")))
if 2 in l2:
a= i
b = l2.index(2)
l.append(l2)
l[x][y] = 2
func(x, y)
for i in range(n):
for j in range(m):
if l[i][j] == 1:
l[i][j] = -1
elif l[i][j] == 0:
pass
else:
l[i][j] = l[i][j]-2
print_l(l)
위의 방법처럼 재귀 함수를 통해 한 방향으로 계속 가면서 막힌 경우 다른 곳으로 이동하는 방향으로 생각했다.
하지만 이 방법으로 수행하면
위의 답이 나오게 된다.
재귀함수를 사용하게 되면 각 방향으로 끝까지 가버린다.
각 방향의 끝까지 간 후에 막히거나 0을 만나면 그 다음 방향으로 끝까지 가버리게 되는 거다.
즉 시계방향으로 계속 돌면서 수를 더할 것이다.
우리는 한 점으로 부터 시작해서 각각의 점까지의 최단 거리를 적고 싶다.
즉
위처럼 한칸 옮기기 전에 4방향 모든 곳에 영향을 주어야 한다.
그러려면 어떻게 해야 할까..?
한 점을 기준으로 4방향의 좌표를 순서대로 넣고, 먼저 넣은 좌표를 기준으로 또 4방향의 좌표를 넣으면 된다.
즉
먼저 들어간 좌표에 대해서 4방향을 계산한 뒤 다음 좌표를 순서에 추가하면 된다.
예를 들어보자
시작값 = [0,0]
[0,0] 에서 4방향의 값을 더해주고 각 좌표를 넣어준다. = [[1,0], [0,1], [-1,0], [0,-1]]
다음에는 가장 면저 넣은 좌표를 뺀다.
[1,0] , [[0,1], [-1,0], [0,-1]]
그리고 뺀 값을 기준으로 4방향의 값을 더해주고 좌표를 넣어준다.
기준값 = [1,0]
[[0,1], [-1,0], [0,-1], [2,0], [1,1], [0,0], [1,-1]]
리스트를 보면 기준의 방법과는 다른 것을 볼 수 있다.
처음 내가 작성했던 코드는 한 방향으로만 계속 갈 것이다.
재귀함수로 작성했으니까 더 이상 갈 수 없을 때까지 간 후, 다음 방향으로 계속 갈 것이다.
하지만 FIFO 방식을 이용한다면..?
각각의 좌표에서 한방향이 아니라 4방향 모든 값에 영향을 준 뒤 방향으로 이동하므로 최단 거리를 구할 수 있는 것이다.!
import sys
from collections import deque
def print_l(l):
for i in l :
for j in i:
print(j,end=" ")
print()
n, m = map(int, sys.stdin.readline().split(" "))
l = []
a,b = 0, 0
for i in range(n):
l2 = list(map(int, sys.stdin.readline().split(" ")))
if 2 in l2:
a = i
b = l2.index(2)
l.append(l2)
d = deque([[a,b]])
direction = [[0,1], [1,0],[0,-1],[-1,0]]
while d:
d2 = d.popleft()
a,b = d2[0], d2[1]
for dir in direction:
if 0 <= a+dir[0] < n and 0<= b+dir[1] < m:
if l[a+dir[0]][b+dir[1]] == 1:
l[a+dir[0]][b+dir[1]] = l[a][b] + 1
d.append([a+dir[0], b+dir[1]])
for i in range(n):
for j in range(m):
if l[i][j] == 0:
pass
elif l[i][j] == 1:
l[i][j] = -1
else:
l[i][j] = l[i][j]-2
print_l(l)
따라서 위의 방식을 이용하여 bfs 를 구현한 코드이다.
문제를 구현하면서 도움이 될만한 팁이 있다.
항상 문제를 구현하면 값을 입력하고, 정답의 형식을 갖춰 제출하는 코드가 있을 것이다.
이 코드를 미리 함수로 만들어서 사용한다면 반복되는 과정을 빠르고 정확하게 정리할 수 있다!!