프로그래머스 미로 탈출 python

gobeul·2023년 9월 22일

Java python 알고리즘 문제 프로그래머스

알고리즘 풀이

목록 보기

36/70

개인적으로 너무 어려웠지만 비트마스킹을 적용해 볼 수 있는 기회여서 좋았다.

📜 문제 바로 가기 : 미로 탈출

제출코드

파이썬

import heapq

map = []
isTrap = []

def solution(n, start, end, roads, traps):
    global map, isTrap
    map = [[-1] * (n+1) for _ in range(n+1)]
    
    for p, q, s in roads:
        if map[p][q] == -1:
            map[p][q] = s
        else:
            map[p][q] = min(map[p][q], s)
    
    isTrap = [-1] * (n+1)
    tn = 0
    for i in traps:
        isTrap[i] = tn
        tn += 1
        
    
    return dijkstra(start, end, n)

def dijkstra(start, end, n):
    inf = 99999999
    hq = []
    distance = [[inf, inf] for _ in range(n+1)] # 0 : off // 1 : on
    distance[start] = [0, 0]
    visitCnt = [0] * (n+1)
    visitCnt[start] = 1
    
    heapq.heappush(hq, (start, 0, 0)) # 노드 / 거리 / 트랩 상태(비트)
    while hq:
        now, d, t = heapq.heappop(hq)

        for i in range(1, n+1):
            if isRight(now, i, t) == True and map[now][i] != -1: # 정방향
                k = d + map[now][i]
                if isTrap[i] == -1: # 트랩이 아닌경우 별 신경 x
                    if distance[i][0] > k or visitCnt[i] <= 1:
                        if distance[i][0] > k:
                            distance[i][0] = k
                        visitCnt[i] += 1
                        heapq.heappush(hq, (i, k, t))

                else: # 트랩인 경우 on, off 처리
                    new_t = switch(i, t)
                    if operateTrap(i, t) == False: # 트랩 off -> on
                        if distance[i][1] > k:
                            distance[i][1] = k
                            heapq.heappush(hq, (i, k, new_t))
    
                    else:
                        if distance[i][0] > k:
                            distance[i][0] = k
                            heapq.heappush(hq, (i, k, new_t))
                            
            elif isRight(now, i, t) == False and map[i][now] != -1: # 역방향
                k = d + map[i][now]
                if isTrap[i] == -1: 
                    if distance[i][0] > k or visitCnt[i] <= 1:
                        if distance[i][0] > k:
                            distance[i][0] = k
                        visitCnt[i] += 1
                        heapq.heappush(hq, (i, k, t))

                else: 
                    new_t = switch(i, t)
                    if operateTrap(i, t) == False: 
                        if distance[i][1] > k:
                            distance[i][1] = k
                            heapq.heappush(hq, (i, k, new_t))

                    else:
                        if distance[i][0] > k:
                            distance[i][0] = k
                            heapq.heappush(hq, (i, k, new_t))

         
    return min(distance[end])
                

def isRight(i, j, t): # i -> j 방향이 정? 역?
    if operateTrap(i, t) ^ operateTrap(j, t) == True:
        return False # 역
    return True # 정
    
    
def operateTrap(i, t): # i노드 트랩이 동작 중인가?
    if isTrap[i] == -1:
        return False
    
    tn = isTrap[i]
    if t & 2**tn == 0: # 트랩이 off
        return False
    return True

def switch(i, t): # 트랩 스위칭
    tn = isTrap[i]
    if operateTrap(i, t) == False:
        return t + 2**tn
    
    return t - 2**tn

접근방법

최단경로는 "다익스트라"를 이용해서 계산하고 트랩의 on/off 상태는 비트마스크로 저장한다.
트랩이 on 되는 경우 연결된 간선의 방향이 바뀌기 때문에 방향이 바뀌는 경우와 바뀌지 않는 경우를 조건 분기로 나눠야했다.

방향이 바뀌는 경우
1. 출발점이 off 상태 - 도착점이 on 상태인 경우
2. 출발점이 on 상태 - 도착점이 off 상태인 경우

방향이 바뀌지 않는 경우
1. 출발점이 on 상태 - 도착점이 on 상태인 경우
2. 출발점이 off 상태 - 도착점이 off 상태인 경우

이런 경우가 나오고 나는 XOR연산을 이용해서 처리했다. (출발점과 도착점의 상태가가 같으면 정방향이다.)

다익스트라는 기본적으로 방문한 노드라면 그 노드까지의 거리가 더 작은 값으로 갱신되지 않는 이상 힙큐에 값을 추가하지 않는데 이 경우 트랩의 on/off 상태 때문에 각각의 경우를 나눠 거리값을 저장했다. distance = [[inf, inf] for _ in range(n+1)] # 0 : off // 1 : on

여기까지 코드를 짜고 제출해봤는데 테스케이스 3번, 5번에서 오답이 나왔다.
여러가지 테케를 생각해본 결과 오답에 걸리는 테케를 찾을 수 있었는데 트랩이 아닌 노드에서도 더 높은 거리 값으로 2번 방문해야되는 경우가 있었다.