[백준 5022번] 연결(파이썬)

https://www.acmicpc.net/problem/5022

5022번: 연결

예전에 이 문제를 접하고

예시코드까지 보고도 뭔소리인지 몰라서 접었는데

다시 보니 풀이방법이 보였습니다.

 

이 문제는 bfs문제인데 좀 특이합니다.

bfs를 총 2번 해야하며,

이전 bfs로 지나간 곳은 지나갈 수 없습니다.

'그럼 bfs2번만 해주면 되는 쉬운 문제네요'

라고 생각하실 수 있겠지만

bfs특성상 모든 지역을 다 탐색할 수 있습니다.

아무리 heaq로 구해도 이미 거의 대부분 지역을 탐색한 뒤라서

다음 bfs에서 이상하게 됩니다.

 

그래서 경로 중에서

선과 선이 완벽하게 연결된 지점을 나중에 방문처리해주는 방식으로

코드를 짜봤습니다.

#백준 5022 연결
from heapq import heappop,heappush
from copy import deepcopy
dx=[0,0,1,-1]
dy=[1,-1,0,0]

def bfs(sx,sy,ex,ey):
    q=[]
    se=set()
    se.add((sx,sy))
    heappush(q,[0,sx,sy,se])
    while q:
        cnt,x,y,road=heappop(q)
        if x==ex and y==ey:
            for vx,vy in road:
                visited[vx][vy]=True
            return cnt
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>N or ny<0 or ny>M:
                continue
            if ((nx,ny)) in road:
                continue
            if visited[nx][ny]==True:
                continue
            new_road=deepcopy(road)
            new_road.add((nx,ny))
            heappush(q,[cnt+1,nx,ny,new_road])

    return 1e9


N,M=map(int,input().split())
a1x,a1y=map(int,input().split())
a2x,a2y=map(int,input().split())
b1x,b1y=map(int,input().split())
b2x,b2y=map(int,input().split())
visited=[[False]*(M+1) for _ in range(N+1)]

r1=bfs(a1x,a1y,a2x,a2y)+bfs(b1x,b1y,b2x,b2y)



visited=[[False]*(M+1) for _ in range(N+1)]

r2=bfs(b1x,b1y,b2x,b2y)+bfs(a1x,a1y,a2x,a2y)
ans=min(r1,r2)
if ans>=1e9:
    print("IMPOSSIBLE")
else:
    print(ans)

아쉽게도 이 코드는

시간초과가 발생했습니다.

아마 deepcopy때문인 것 같습니다.

deepcopy자체가 시간을 많이 잡아먹어서

시간이 많이 소요되는 것 같습니다.

 

이후 구글링을 통해서

리스트 좌표로 경로를 역산출하는 방식을 썼습니다.

#백준 5022 연결
from collections import deque

dx=[0,0,1,-1]
dy=[1,-1,0,0]
def get_dist(a1x,a1y,a2x,a2y,b1x,b1y,b2x,b2y):
    visited = [[False] * (M + 1) for _ in range(N + 1)]
    path = [[(0, 0) for _ in range(M + 1)] for _ in range(N + 1)]
    visited[b1x][b1y]=True
    visited[b2x][b2y]=True
    dis1=bfs(a1x,a1y,a2x,a2y,visited,path)
    visited = [[False] * (M + 1) for _ in range(N + 1)]
    #갔던 길만 다시 복구
    #그냥 이전에 visited에서 True가 된 걸로 가면
    #모든 지역을 방문하는 케이스가 나올 수 있으니
    #오직 시작점,목적지까지 간 것만 고려해준다.
    cx,cy=a2x,a2y
    while True:
        visited[cx][cy]=True
        if cx==a1x and cy==a1y:
            break
        cx,cy=path[cx][cy]

    dis2=bfs(b1x,b1y,b2x,b2y,visited,path)

    return dis1,dis2

def bfs(sx,sy,ex,ey,visited,path):
    q=deque()

    q.append((sx,sy,0))
    visited[sx][sy]=True
    while q:
        x,y,cnt=q.popleft()
        if x==ex and y==ey:
            return cnt
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>N or ny<0 or ny>M:
                continue
            if visited[nx][ny]==True:
                continue

            q.append((nx,ny,cnt+1))
            visited[nx][ny]=True
            path[nx][ny]=(x,y)

    return 1e9


N,M=map(int,input().split())
a1x,a1y=map(int,input().split())
a2x,a2y=map(int,input().split())
b1x,b1y=map(int,input().split())
b2x,b2y=map(int,input().split())

r1,r2=get_dist(a1x,a1y,a2x,a2y,b1x,b1y,b2x,b2y)
dis1=r1+r2

r3,r4=get_dist(b1x,b1y,b2x,b2y,a1x,a1y,a2x,a2y)
dis2=r3+r4

ans=min(dis1,dis2)

if ans>=1e9:
    print("IMPOSSIBLE")
else:
    print(ans)

bfs를 어떻게 써야하는지

여러 생각을 들게 만들어준

좋은 문제였습니다.