[카카오 2021 인턴/파이썬] 미로 탈출

0. 문제

https://programmers.co.kr/learn/courses/30/lessons/81304?language=python3 

코딩테스트 연습 - 미로 탈출

1. 해결 알고리즘

다익스트라 알고리즘, 비트마스크, 약간의 list & dict 차이

2. 해결 방법

2-1. 간선

문제를 읽어보면 간선의 방향이 중간 중간 바뀐다. 간선이 바뀌는 경우는 다음과 같다.

A 노드 -> B 노드로 갈 때 예시로 들면 다음과 같다.

1. 둘 다 일반 노드 일 경우
2. A가 활성화 된 함정노드, B가 일반 노드
3. A가 일반 노드, B가 활성화 된 함정노드
4. A, B 둘다 활성화 된 함정노드

* 활성화 되지 않은 함정 노드는 일반 노드와 같다.

1번은 정방향으로 진행 하면 된다.

2번과 3번은 역방향으로 진행하면 된다.

4번은 역 + 역 이므로 정방향으로 진행하면 된다.

함정 노드가 활성화 되었는지 되지 않았는지 dict을 활용해서 표시하면 활성화는 표시할 수 있지만 에러가 발생한다.

에러는 아래 설명과 함께 자세하게 서술하겠다.

2-2. 다익스트라 알고리즘과 방문

보통 다익스트라 알고리즘에서 우선순위 큐에 ( 시작점-노드의 거리, 노드 번호 ) 형식으로 큐에 넣고 빼서 다익스트라 알고리즘이 작동한다.

또한 각 노드별로 방문했는지 조사하면서 방문했던 노드라면 건너 뛰고 진행한다.

하지만 예시 2 를 보면 방문했던 노드라도 다시 방문해야 하는 경우가 생긴다.

그렇다고 방문했던 노드를 계속 방문하자면 무한 루프에 갇힐 것이다.

여기서 해결방안은 각 함정 노드의 활성화 여부에 따라서 방문을 다르게 체크하는 것이다.

그리고 활성화 표시를 우선순위 큐에 같이 넘겨주는 것이다.

(2-1)에서 발생할 수 있는 에러가 여기에 나온다. dict를 우선순위 큐에 넣을 수 있지만, dict와 dict를 비교해야 하는 상황이 온다면 에러가 발생할 수 있다.

그렇기에 비트 마스크를 활용해서 함정의 활성화를 표시할 수 있다.

traps 배열에서 5번 함정 노드가 활성화 되었다면 비트마스크로 2^1 에 해당하는 곳에 비트를 키는 것이다.

그리고 우선 순위 큐에 ( 시작-노드의 거리, 노드 번호, 비트마스크로 표시한 함정 활성화 ) 를 우선순위 큐에 넣는것이다.

2-3. 방문 했던 노드

2-2 에서 함정 노드의 활성화에 따라서 방문했던 노드를 표시하면 된다고 했다.

 ( 노드의 개수 ) X ( 2 ** (trap 개수) ) 의 2차원 배열로 표시하면 된다.

만약 01000 의 활성화와 3번째 노드 방문은

visited[3][8 = 01000] -> visited[3][8] 에 체크를 하면 되는 것이다.

3. 코드

import heapq as hq
import sys

INF = sys.maxsize


def solution(n, start, end, roads, traps):
	answer = INF
	active = 0b0
	graph = [[] for _ in range(n + 1)]
	visited = [[False for _ in range(2 ** len(traps) + 1)] for __ in range(n + 1)]
	
	temp = {}
	for i in range(1, n + 1):
		temp[i] = (False, 0)
	for t in traps:
		temp[t] = (True, traps.index(t))
	traps = temp
	
	for D, A, W in roads:
		ele = (A, W, True)
		graph[D].append(ele)
		ele = (D, W, False)
		# True -> 정방향 || False -> 역방향
		graph[A].append(ele)
	
	que = [(0, start, active)]
	
	while que:
		weight, N, active = hq.heappop(que)
		
		if N == end:
			answer = min(answer, weight)
		
		if visited[N][active] is True:
			continue
		else:
			visited[N][active] = True
		
		N_is_trap = False
		if traps[N][0]:
			N_is_trap = True
			active = active ^ (1 << traps[N][1])
		
		for A, W, state in graph[N]:
			if N_is_trap and active & (1 << traps[N][1]) > 0:
				# N 에서 함정 발동된 상태
				if traps[A][0] and active & (1 << traps[A][1]) > 0:
					# 정방향
					# A가 함정이고, 발동 된 경우
					if state is True:
						ele = (W + weight, A, active)
						hq.heappush(que, ele)
				elif state is False:
					# 역방향
					# A가 함정이 아닌 경우
					# A가 함정이지만 함정이 발동되지 않은 경우
					ele = (W + weight, A, active)
					hq.heappush(que, ele)
			else:
				# 정방향
				# N은 함정이 아닌 상태
				if traps[A][0] and active & (1 << traps[A][1]) > 0:
					if state is False:
						ele = (W + weight, A, active)
						hq.heappush(que, ele)
				elif state is True:
					ele = (W + weight, A, active)
					hq.heappush(que, ele)
	
	return answer

4. 개인적인 평

실제 인턴 코딩테스트도 참가했고 처음 봤을 때는 손도 못 댔다. 

특히 비트마스크와 방문체크를 혼합한 것은 생각하지도 못했다.

그리고 복습 겸 문제를 푸는데만 4일동안 이 문제 생각만 한 것 같다.

부분 점순는 여러번 맞았지만 통과가 되지 않았다.

특히, 마지막에 return 하기 전에 print(answer)를 해서 코딩하면서 체크용도로 쓰고 있는 것을 그대로 

제출 했을 때는 통과했지만 print(answer)를 삭제하자 시간초과가 떴다. ( 왜 그러지...? 줄어들어야 정상아닌가? )

시간이 정말 정말 촉박했다.

그래서 결국 (노드 번호) in traps 에서 trap 을 dict 형태로 전환해서 푸니 정해진 시간에 넉넉하지 않더라도

안전하게 들어 올 수 있었다.

4일 동안 너무 맘 고생이 심했다.. 외적으로 문제적으로도.. 하..