[백준 12908번] 텔레포트3 (파이썬)

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

12908번: 텔레포트 3

이 문제는 언뜻보면 bfs같았지만

좀 다르게 풀어야했습니다.

#백준 12908번 텔레포트3
from collections import deque
dx=[0,0,1,-1]
dy=[1,-1,0,0]

sx,sy=map(int,input().split())
ex,ey=map(int,input().split())
telpo=dict()
for _ in range(3):
    x1,y1,x2,y2=map(int,input().split())
    telpo[x1,y1]=[x2,y2]
    telpo[x2,y2]=[x1,y1]
visited=dict()
visited[sx,sy]=0

min_time=1e9

q=deque()
q.append((sx,sy))
while q:
    x,y=q.popleft()

    if visited[x,y]>=min_time:
        continue

    if x==ex and y==ey:
        if min_time>visited[ex,ey]:
            min_time=visited[ex,ey]

        continue
    #현재있는 곳에서 점프
    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>1000000000 or ny<0 or ny>1000000000:
            continue

        if visited.get((nx,ny)):
            if visited[nx,ny]>=visited[x,y]+1:
                continue

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

    #텔레포트
    if telpo.get((x,y)):
        mx,my=telpo[x,y]
        if visited.get((mx,my)):
            if visited[mx,my]>=visited[x,y]+10:
                continue

        visited[mx,my]=visited[x,y]+10
        q.append((mx,my))

print(min_time)

처음에는 bfs로 문제를 접근했습니다.

visited의 범위가 크기 때문에

dict을 사용하는 방법을 썼지만

시간초과를 일으켰습니다.

 

이 문제의 푸는 방법은 좀 독특했는데요.

텔레포트 좌표 각 6개+도착지점까지 생각하면

총 7개의 점이 있습니다.

그 점들을 이동하는 케이스를 순열로 담은 다음에

모든 케이스를 다 구해주는 것이 이 문제의 풀이였습니다.

#백준 12908번 텔레포트3
from itertools import permutations
import sys

sx,sy=map(int,input().split())
ex,ey=map(int,input().split())
point=[]
for _ in range(3):
    x1,y1,x2,y2=map(int,input().split())
    point.append([x1,y1,x2,y2])
    point.append([x2,y2,x1,y1])

point.append([ex,ey,ex,ey])
answer=sys.maxsize
p=[i for i in range(0,7)]
for case in permutations(p,7):
    n_case=list(case)
    nx=sx
    ny=sy
    dis=0
    for i in range(7):
        now=n_case[i]
        gx,gy=point[now][0],point[now][1]
        dis+=abs(nx-gx)+abs(ny-gy)
        tx,ty=point[now][2],point[now][3]
        if tx==ex and ty==ey:
            break
        dis+=10
        nx=tx
        ny=ty
    answer=min(answer,dis)

print(answer)

 

문제 풀이를 보고 놀라긴 했는데

생각해보니 범위가 사실상 무한에서 무한대까지라는 걸 생각하면

bfs로 푸는 방법보다는

이렇게 특정 좌표를 기준으로 생각해보는 것이

시간을 절약하는 더 좋은 방식이었습니다.

좌표의 범위가 클 떄

어떻게 처리할 수 있는지 공부할 수 있었던 좋은 문제입니다.