from collections import *
dy = [1,-1,0,0]; dx = [0,0,1,-1]
def BFS(A1,A2):
dq = deque([[*A1,*A1,0]])
while dq:
y,x,ylast,xlast,d = dq.popleft()
if visited[y][x]:
continue
visited[y][x] = ylast,xlast
if [y,x] == A2:
return d
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0:
dq.append((y1,x1,y,x,d+1))
return 1e6
def solve(A1,A2,B1,B2):
global visited
visited = [[0]*M for i in range(N)]
for y,x in [B1,B2]:
visited[y][x] = 1
d = BFS(A1,A2)
if d==1e6:
return 1e6
y,x = A2
newvisited = [[0]*M for i in range(N)]
while 1:
if newvisited[y][x]:
break
newvisited[y][x] = 1
y,x = visited[y][x]
visited = newvisited
return d+BFS(B1,B2)
N,M = map(lambda x:int(x)+1,input().split())
co = A1,A2,B1,B2 = [[*map(int,input().split())] for i in range(4)]
print("IMPOSSIBLE" if (result:=min(solve(A1,A2,B1,B2),solve(B1,B2,A1,A2)))>1e5 else result)BFS 응용문제
우선 풀이를 설명하면,
1. B1,B2의 좌표를 visited로 칠해놓고 A1-A2의 최단거리를 BFS로 구하고 경로를 역추적으로 저장한다.
2. visited를 초기화하고, 1에서 구한 경로를 visited로 칠한다.
3. B1-B2 최단거리를 구하고 A1-A2 최단거리와의 합을 구한다.
4. A-B를 바꿔서 1~3을 한번 더 실행하고 더 짧은 거리를 출력한다.
골드1 치고 생각보다 까다로운 문제였다. 아이디어를 떠올리기도 쉽지 않았고 이를 증명하기도 쉽지 않았던 문제였다.
여담) 이 문제의 숏코딩 순위 1위가 되었다.
