[BOJ/python]3860번 할로윈 묘지

백준 3860번 할로윈 묘지 파이썬 

 

문제 링크 - https://www.acmicpc.net/problem/3860

3860번: 할로윈 묘지

정답률이 15퍼센트인 것을 모르고 문제를 풀기 시작했다. 문제를 번역하는 과정에서 중요한 내용들을 번역하지 않아서 이슈가 좀 있었던 것 같았다. 음수 사이클이 도착점에 도달하는 지 여부에 상관없이 존재하기만 한다면 Never을 출력해야 한다. 이 부분에서 많이들 오답을 받은 것 같다.

1. 풀이

시작점과 도착점이 고정되어 있다. 2차원 좌표에서 최단 거리를 구하는 문제다. 시간 여행을 할 수 있는 구멍으로 들어가면 시간도 줄어들고 좌표의 위치도 바뀐다. 들어가는 구멍과 나오는 구멍을 간선으로 연결해주고 벨만 포드 알고리즘을 사용하면 쉽게 풀 수 있다.

• graph 배열에 좌표의 정보를 저장한다.
  • 이동할 수 없는 묘비라면 -1, 이동할 수 있는 빈칸이라면 0, 귀신 구멍의 입구라면 인덱스를 1부터 늘려가며 저장한다. 그리고 귀신 구멍의 출구 좌표를 hole 배열에 따로 저장해준다.
• 출발점이 고정되어 있으므로 dist[a][b] 배열에는 a에서 b까지의 최단 거리가 아닌 출발점에서부터 (a,b)까지의 최단 거리를 저장한다.
• 모든 좌표의 개수만큼 반복문을 실행한다 - 벨만 포드
• 만약 현재 좌표가 도착점 혹은 묘비라면 코드를 실행하지 않는다. continue
• 만약 현재 좌표가 귀신 구멍의 입구라면 귀신 구멍의 출구로 이동하고 최단 거리를 갱신한다.
• 만약 현재 좌표가 귀신 구멍의 입구가 아니라면 인접한 4방향의 dist배열에 최단 거리를 갱신한다.
• 반복문이 좌표의 개수만큼 실행되는 순간 dist가 갱신된다면 Never을 출력하기 위해 -inf를 반환해준다.
• 음수 사이클이 존재하지 않는다면 도착점까지의 최단 거리를 반환한다.

2. 코드

answer=[]
INF = float('inf')
while True:
    W, H = map(int,input().split())
    if W==0 and H==0:
        break
    
    G = int(input())
    
    graph = [ [0 for _ in range(H)]for _ in range(W) ]
    hole=[[INF,INF,INF]]
    for _ in range(G):
        x,y = map(int,input().split())
        graph[x][y] = -1
    
    E = int(input())
    for i in range(1,E+1):
        x,y, hx,hy, t = map(int,input().split())    
        graph[x][y] = i
        hole.append([hx,hy,t])

    dist = [ [INF for _ in range(H)] for _ in range(W) ]
    dist[0][0]=0
    def bf():
        for count in range(H*W):
            for x in range(W):
                for y in range(H):
                    
                    if x==W-1 and y==H-1 or graph[x][y]==-1:
                        continue
                    
                    
                    elif graph[x][y] >=1:
                        outX,outY,outTime = hole[ graph[x][y] ]
                        if dist[outX][outY] > dist[x][y] + outTime :
                            dist[outX][outY] = dist[x][y] + outTime 

                            if count == H*W-1 :
                                return float('-inf')

                          
                    elif graph[x][y]==0:
                        for nx,ny in ([x,y+1], [x,y-1], [x+1,y], [x-1,y]):
                            if 0<=nx<W and 0<=ny<H : 
                                if graph[nx][ny] >=0 :
                                    if dist[nx][ny] > dist[x][y]+1:
                                        dist[nx][ny] = dist[x][y]+1
                                        
                                        if count == H*W-1:
                                            return float('-inf')
                                            # if check(nx,ny):
                                            #     return False
                                   
        return dist[W-1][H-1]
    
    result = bf()
    if result == INF:
        print('Impossible')
    elif result == float('-inf') :
        print('Never')
    else:
        print(result)