on
프로그래머스 미로 찾기 파이썬/Python
프로그래머스 미로 찾기 파이썬/Python
문제 보러가기
문제 설명
신규 게임 ‘카카오 미로 탈출’이 출시되어, 라이언이 베타테스터로 참가했습니다.
위 예시 그림은 카카오 미로 탈출의 초기 상태를 나타냅니다. 1번부터 3번까지 번호가 붙어있는 3개의 방이 있고, 방과 방 사이를 연결하는 길에는 이동하는데 걸리는 시간이 표시되어 있습니다. 길은 화살표가 가리키는 방향으로만 이동할 수 있습니다. 미로에는 함정이 존재하며, 함정으로 이동하면, 이동한 함정과 연결된 모든 화살표의 방향이 바뀝니다.
출발지점인 1번 방에서 탈출이 가능한 3번 방까지 이동해야 합니다. 탈출하는데 걸리는 최소 시간을 구하려고 합니다.
그림의 원은 방을 나타내며 원 안의 숫자는 방 번호를 나타냅니다. 방이 n개일 때, 방 번호는 1부터 n까지 사용됩니다.
화살표에 표시된 숫자는 방과 방 사이를 이동할 때 걸리는 시간을 나타냅니다. 화살표가 가리키고 있는 방향으로만 이동이 가능합니다. 즉, 위 그림에서 2번 방에서 1번 방으로는 이동할 수 없습니다.
그림에 표시된 빨간색 방인 2번 방은 함정입니다. 함정 방으로 이동하는 순간, 이동한 함정 방과 연결되어있는 모든 길의 방향이 반대가 됩니다. 위 그림 1번 방에서 2번 방으로 이동하는 순간 1에서 2로 이동할 수 있던 길은 2에서 1로 이동할 수 있는 길로 바뀌고, 3에서 2로 이동할 수 있던 길은 2에서 3으로 이동할 수 있는 길로 바뀝니다. 똑같은 함정 방을 두 번째 방문하게 되면 원래 방향의 길로 돌아옵니다. 즉, 여러 번 방문하여 계속 길의 방향을 반대로 뒤집을 수 있습니다.
2번 방은 함정입니다. 미로를 탈출하는데 필요한 최단 시간은 다음과 같습니다. 1→2: 2번 방으로 이동합니다. 이동 시간은 2입니다. 함정 발동: 2번 방과 연결된 모든 길의 방향이 반대가 됩니다. 2→3: 3번 방으로 이동합니다. 이동 시간은 3입니다. 탈출에 성공했습니다. 총 이동시간은 5입니다.
방의 개수를 나타내는 정수 n, 출발 방의 번호 start, 도착 방의 번호 end, 통로와 이동시간을 나타내는 2차원 정수 배열 roads, 함정 방의 번호를 담은 정수 배열 traps이 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최단 시간을 return 하도록 solution 함수를 완성해주세요.
제한사항
2 ≤ n ≤ 1,000
n ≤ 1,000 1 ≤ start ≤ n
start ≤ n 1 ≤ end ≤ n
end ≤ n 1 ≤ roads의 행 길이 ≤ 3,000
roads의 행 길이 ≤ 3,000 roads의 행은 [P, Q, S]로 이루어져 있습니다. P에서 Q로 갈 수 있는 길이 있으며, 길을 따라 이동하는데 S만큼 시간이 걸립니다. 1 ≤ P ≤ n 1 ≤ Q ≤ n P ≠ Q 1 ≤ S ≤ 3,000 서로 다른 두 방 사이에 직접 연결된 길이 여러 개 존재할 수도 있습니다.
0 ≤ traps의 길이 ≤ 10 1 ≤ traps의 원소 ≤ n 시작 방과 도착 방은 함정이 아닙니다.
traps의 길이 ≤ 10 항상 미로를 탈출할 수 있는 경우만 주어집니다.
입출력 예
n start end roads trap result 3 1 3 [[1, 2, 2], [3, 2, 3]] [2] 5 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
1 → 2 → 3 → 2 → 4 순서로 이동하면 됩니다. 총 이동시간은 4입니다.
제한시간 안내
정확성 테스트 : 10초
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import heapq def solution(n, start, end, roads, traps): start - = 1 end - = 1 INF = float( "inf" ) nodes = [] trap_dict = {trap - 1 : idx for idx, trap in enumerate(traps)} isvisited = [[ False ] * n for _ in range ( 1 < < len (traps))] graph = [[] for _ in range (n)] for src, des, cost in roads: graph[src - 1 ].append([des - 1 , cost, 0 ]) graph[des - 1 ].append([src - 1 , cost, 1 ]) heapq.heappush(nodes, ( 0 , start, 0 )) while nodes: cur_cost, cur_node, state = heapq.heappop(nodes) if cur_node = = end: return cur_cost if isvisited[state][cur_node] = = True : continue else : isvisited[state][cur_node] = True for next_node, next_cost, road_type in graph[cur_node]: next_state = state cur_istrap = 1 if cur_node in trap_dict else 0 next_istrap = 1 if next_node in trap_dict else 0 if cur_istrap = = 0 and next_istrap = = 0 : if road_type = = 1 : continue elif (cur_istrap + next_istrap) = = 1 : node_i = cur_node if cur_istrap = = 1 else next_node isTrapOn = (state & ( 1 < < trap_dict[node_i])) > > trap_dict[node_i] if isTrapOn ! = road_type: continue elif cur_istrap = = 1 and next_istrap = = 1 : isTrapOn1 = (state & ( 1 < < trap_dict[cur_node])) > > trap_dict[cur_node] isTrapOn2 = (state & ( 1 < < trap_dict[next_node])) > > trap_dict[next_node] if (isTrapOn1 ^ isTrapOn2) ! = road_type: continue if next_istrap = = 1 : next_state = state ^ ( 1 < < trap_dict[next_node]) heapq.heappush(nodes, (cur_cost + next_cost, next_node, next_state)) cs
풀이
문제 설명을 보고 주어진 시간제한이 10초라는 것을 봤을때,
최소힙을 이용한 다익스트라 알고리즘을 이용하는 문제 겠구나 싶었는데 trap을 밟는 경우떄문에 쉽게 풀수 없었다.
처음에는 trap을 밟는 경우만큼 그래프를 전부 만들고 풀려고 했는데 그러기엔 trap의 길이가 최대 10이고
이럴경우 2^10 = 1024가지가 나오기때문에 아니지 않을까.. 싶었다.
결국 다른사람의 풀이를 참고해서 풀었는데,
최소힙을 이용한 다익스트라 + trap을 밟는 경우를 비트 마스킹으로 처리하여 풀면 된다는 것을 알았다.
참고한 블로그
비트 마스킹으로 처리하면 용이한 이유로는
1. 방문 확인은 할때 위에서 언급한 2^n 가지의 함정을 밟는 경우의 수를 쉽게 처리할 수 있다.
2. 현재 노드와 다음 노드에서 함정을 밟는 경우에 따른 처리를 쉽게 할 수 있다.
두가지 이유가 있었다.
구체적인 구현을 살펴보면
1. 함정 정보를 위한 trap_dict, 방문 확인을 위한 isvsited 선언
# 비스마스킹을 하기 위해 각 traps의 원소 번호가 몇번째 idx인지 저장
# e.g.) 예제 2에서 2는 trap의 0번째 원소, 3은 trap의 1번째 원소
trap_dict = {trap-1 : idx for idx, trap in enumerate(traps)}
# 2^len(traps) 만큼의 state의 수가 존재한다
# 예를들어 trap이 두개라면 둘다 안밟는 경우, 2번만 밟는경우, 3번만 밟는 경우, 둘다 밟는 경우
# 로 총 2^2 = 4 개가 존재한다.
# 따라서 이 모든 경우에 따라 간선의 방향이 달라지기 때문에
# e.g.) 예제 2에서 2번 노드만 밟는 경우와 2번과 3번 노드를 밟는 경우 두 graph의 모양은 다르기때문에 방문 여부가 다르다고 생각)
# 2^n가지의 상태에서 n개의 노드중 방문한 노드의 정보를 저장해야한다.
isvisited = [[False] * n for _ in range(1<
#
# 이 같은 방법을 통해 함정을 밟는 2^n개의 모든 경우의 방문 노드를 체크할 수 있다.
2. graph에 간선 정보 저장
graph = [[] for _ in range(n)]
for src, des, cost in roads:
graph[src-1].append(des-1, cost, 0) # 정방향
graph[des-1].append(src-1, cost, 1) # 역방향
3. 최소힙을 이용한 다익스트라 알고리즘 적용
heapq.heappush(node, (0, start , 0)) # 비용, 시작지점, 함정을 밟은 상태
while node:
cur_cost, cur_node, state = heapq.heappop(node)
if cur_node == end: return cur_cost
if isvisited[state][cur_node] == True: continue # 이 state에서 방문한 노드면 continue
else isvisited[state][cur_node] = True # 방문 체크
4. 현재 노드에서 방문할 수 있는 다음 노드 탐색
for next_node, next_cost, roadtype in graph[cur_node]:
# cur_istrap : 현재 노드의 함정 여부 저장, next_istrap : 다음 노드의 함정 여부 저장
# roadtype : 0이면 정방향, 1이면 역방향
next_state = state
cur_istrap = 1 if cur_node in trap_dict else 0
next_istrap = 1 if next_node in trap_dict else 0
5. 다음 노드를 방문 할 수 있는지 검사
이때 방문하는 케이스는 크게 3가지가 존재한다.
case 1. 둘다 일반 노드 ) 일반 노드 -> 일반 노드
- 이경우 정방향으로만 갈 수 있다
case 2. 한쪽만 일반 노드 ) 일반 노드 -> 함정 노드 or 함정 노드 -> 일반노드
- 이 경우 함정노드를 밟았으면 역방향으로, 함정노드를 밟지 않았으면 정방향으로만 가능하다
case 3. 둘다 함정 노드 ) 함정 노드 -> 함정 노드
- 이 경우에는 둘다 밟거나 밟지 않았으면 정방향으로, 한쪽만 밟았으면 역방향으로만 가능하다.
# 일반 -> 일반
if cur_istrap == 0 and next_istrap == 0:
# 정방향만 가능
if roadtype == 1: continue
# 일반 -> 함정 or 함정 -> 일반
elif cur_istrap + next_istrap == 1:
# 함정을 발동한 상황에서 역방향과
# 함정이 발동하지 않은 상태에서 정방향이 가능
node_i = cur_node if cur_istrap == 1 else next_node # 둘 중 함정인 노드 저장
# 함정이 발동했으면 and 연산을 했을때 함정을 밟은 노드의 번호가 나온다
# e.g.) state & 1<
# 이걸 다시 trap_dcit[node_i] 만큼(trap에서 node_i의 idx만큼) 오른쪽으로 쉬프트 하면 1이 된다.
# 역방향이여야 하므로 이 값이 roadtype과 같아야함
#
# 발동하지 않았을때도 마찬가지
isTrapOn = (state & 1<> trap_dict[node_1]
if isTrapOn != road_type: continue
# 함정 -> 함정
elif cur_istrap == 1 and next_istrap ==1:
# 두 함정 모두 밟았으면 정방향
# 두 함정 모두 밟지 않았으면 정방향
# 한 함정만 밟았으면 역방향
# 두 함정 모두 밟은 여부를 조사
isTrapOn1 = (state & 1<> trap_dict[cur_node]
isTrapOn2 = (state & 1<> trap_dict[next_node]
# xor 연산으로 road_type과 비교
# 두 함정 모두 밟았거나 밟지 않았으면 연산 결과가 0이고 정방향만 가능하므로 road_type과 같아야함
# 한 함정만 밟았으면 연산 결과가 1이고 역방향만 가능하므로 road_type과 같아야함
if (isTrapOn1 ^ isTrapOn2) != road_type: continue
# 다음 node가 함정이면 현재 state에서 함정 노드로 가서 달라진 state를 저장
# xor 연산을 쓰는 이유는 이미 밟은 함정을 또 밟으면 정방향으로 돌아가기 때문
if next_isTrap == 1:
next_state = state ^ 1<
6. 위의 과정을 next_node로 넘어가며 반복
# (더해진 비용, 다음 노드, 다음 상태) 를 다시 heap에 저장
h.heappush(nodes, (cur_cost + next_cost, next_node, next_state))
from http://nooblette.tistory.com/228 by ccl(A) rewrite - 2021-09-06 21:00:19