본문 바로가기

카테고리 없음

[백준 5022번] 연결 (Python3)

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위가 되었다.