23.07.05 파이썬 코딩 퀴즈#261 미로 탈출 (프로그래머스 스쿨)

이번 문제는 미로 탈출 문제이다.

보통의 미로 탈출 문제와는 다른, 색다른 TRAP 이라는게 존재한다.

1. 미로는 정해진 화살표 방향으로만 이동 가능하다

2. 함정으로 이동할 경우, 함정과 연결된 모든 화살표의 방향이 반대로 바뀐다.

문제 예시에 대한 이동설명이다.

즉 1번에서 출발하게 도착지인 3번까지 가야하며, 중간에 2번은 함정이다.

그리고 제한 사항은 위와 같다.

각 통로마다 S 만큼의 시간이 소요되므로, 최단으로 갈 수 있는 길을 선택해야 한다.

입출력 예 1번은 위 그림 설명과 같다.

입출력 예 2번을 그림으로 표현하면 위와 같다.

1번으로 돌아갈 경우, 다시 2번으로 향할 수 없기에 2번에서 갈 수 있는 다른 3번으로 가야 하고, 이 때 다시 2-> 3 이, 3->2로 바뀌기 때문에 2번으로 돌아갈 수 있고, 2 <- 4의 화살표 역시 2 ->4로 바뀌므로 올바르게 4번에 도착 가능하다.

 

이 문제에서 가장 까다로운 부분은 바로 trap 이다.

트랩은 최대 10개까지 주어지며, 한번 밟을때 마다 트랩과 연결된 모든 경로가 바뀌게 된다.

이를 표현하기 가장 적합한 방법은 무엇일까?

 

내가 생각한 방법은 이진수를 활용한 방법이다. 

즉 각 함정을 밟은 횟수를 기록하여, 만약 짝수인 경우, 해당 위치의 진행 방향을 그대로 진행하고, 홀수인 경우라면 반대 방향으로 진행하게 해주면 된다.

그리고 현재 위치에서 도착하는 노드 역시 확인해 주어야 한다.

위와 같이 1,2,3 번의 노드가 존재하며 1번, 2번이 함정 이라고 가정해 보자.

두 함정을 모두 밟지 않은 경우라면 해당 경로들은 변함이 없다.

만약 1번 함정을 한번 밟은 경우라면, 1번과 연결되 두개의 경로가 뒤집힌다.

그리고 두 함정을 동시에 밟은 경우라면, 1번으로 오는 함정과 2번에서 나가는 함정 두개는 뒤집히지만, 1번과 2번을 연결하는 함정은 그대로 유지가 된다.

 

즉 현재 위치와 도착하는 위치의 함정을 밟은 횟수를 기록해 두면, 이 둘을 이용하여 현재 경로가 이용 가능한 경로인지가 확인이 될 것이다.

 

먼저 n에 해당하는 수만큼 노드를 만들어 준다.

그리고 roads 의 값을 기준으로 x => y 에는 양수, y=>x 에는 음수로 방향을 그려준다. 즉, 양수로만 이동 가능하다.

그리고 traps 의 함정 번호 노드에 함정임을 표시해 준다.

이제 heap 에 [0, start, node] 를 넣어주고 while문을 반복하게 되는데, 순서대로 비용, 현재위치, 지금까지의 노드 정보들을 담게 된다.

매번 node를 복사해서 사용하는 이유는, 갈림길 때문이다.

만약 end 에 도착하는 두가지 경로가 존재한다고 가정하고, 두 경로에서 A 경로에서는 함정을 2번, B 경로에서는 함정을 3번 밟아야 한다면, 각 경로간 함정에 따른 경로를 따로 분리해주기 위해 분리하였다.

 

가장 중요한 부분은 바로 new_cost 의 값 산정이다.

현재 위치의 trap_on 과 다음 위치의 trap_on 값을 합쳐서 2로 나눈 나머지를 기준으로 작동한다.

즉 [0,0]과 [1,1]는 갈 수 있지만, 현재 위치와 다음 위치중 하나라도 함정이 있는 경우라면 new_cost 값의 부호를 바꾸어주고, 양수인 경로만 이동 하도록 설정해 두었다.

 

최소heap을 사용하면서 함정사이를 왕복하는 문제점을 해결하기 위해, 다음 위치가 출구인 경우라면 answer 값을 갱신해주고, cost+new_cost 가 answer 보다 작은 경우에만 heap에 넣어주었다.

 

대부분의 문제에서 시간초과에 걸린다.

아마 문제는 매번 node 정보를 새로 deepcopy 해서 사용하기 때문에 발생하는 것으로 보인다.

이를 개선하기 위해 다른 방법이 필요하다.

이를 해결하기 위해 슬라이싱을 이용한 복사를 선택하였다.

기존 트리를 만들어 접근하는 방식은 치우고, graph에는 양방향으로 음수, 양수를 만들어 [비용, 지점]  쌍으로 저장하게 두었다. 

trap_inf 는 트랩을 밟은 경우에만 1씩 증가하면 최종적으로 2로 나눈 나머지가 된다.

이를 이용하면 그 다음 도착점의 trap_inf 를 확인하여 '10' 또는 '01'인 경우라면 cost 값을 반대로 계산하면 된다.

이렇게 머리를 싸맸는데... 딱 한문제 테케5번에서 또 시간초과에 걸린다... 하... 

level4에 들어오고 나서는 문제당 집중해야 하는 시간이 오래 걸리다보니, 생각보다 풀이에 많은 시간이 소모되었다.

몇시간을 헤매다가 다익스트라 알고리즘으로 풀어야 한다는 설명을 발견하고, 도움을 받아 작성해 보았다.

우선 trap_inf 에는 현재 트랩의 번호: 몇번째 트랩 인지가 저장이 된다.

그리고 costs 는 다익스트라 알고리즘을 적용하기 위해 만들어 두었다.

나머지는 기존 방법과 동일하다.

 

먼저 변수 s 는 현재 위치가 함정인 경우라면 state[trap_inf[loc]] 값이 정수형으로 전달 된다.

이렇게 하는 이유는 state를 trap의 길이만큼 생성하였기 때문이다.

그리고 이제 branch[loc]로 다음 이동 장소를 선택해야 한다.

먼저 cnt 와 nstate(다음에 쓸 함정발동 정보) 를 정의해 주어야 한다.

cnt 역시 마찬가지로 다음 위치의 함정 정보이다. 만약 다음 도착지가 함정 이라면 state[trap_inf[d]의 상수가 그 값이 될 것이고, 그렇지 않다면 0 이 된다.

nstate 의 경우 역시 만약 다음 위치가 함정인 경우라면 d의 함정 index(trap_inf[d])를 기준으로 state에서 복사하여 전달하게 된다.

 

입출력 예 1번을 살펴보자.

현재 branch 는 [ [], [[2, 2]], [[1, -2], [3, -3]], [[2, 3]] ] 의 값들이 존재한다.

즉 각 index 를 기준으로 index 에서 다음 좌표로 가는 [번호, 비용] 이 저장되어 있다.

먼저 현재 위치는 1에서 2로 가는 것이다.

비용은 2 만큼 소모가 된다.

현재 위치는 함정이 아니므로 s는 0 인 상태이다.

하지만 다음위치 d(2)는 함정 이므로 새롭게 nstate 와 cnt 가 정의 되는데, 아직 함정이 발동하기 전 이므로 cnt = 0 이 되고,

nstate = '1' 이 된다.

그리고 이제 c 값을 계산해 주어야 한다.

c*(-1)**(0+0) 이다. 여기서 한가지 눈여겨 봐야할 점은 바로 연산자의 우선 순위 이다.

파이썬 에서는 제곱(**) 이 곱셈보다 우선이다. 따라서 -1 의 제곱이 먼저 계산한 다음 c와 곱한 값이 결과 값이 된다.

음수를 기준으로 0을 포함한 짝수승은 양수이고, 홀수승은 음수가 된다.

따라서 최종적으로 2 값을 가지게 되며 q에는 [2, '1', 2] 가 전달된다.

이제 2번에서 3번으로 가는 길만 남았고, 2번은 함정이기 때문에 전달받은 '1' 이란 state 에서 trap_inf[2] 값에 해당하는 index를 가져오면 s는 1이 된다.

3번은 함정노드가 아니기 때문에 cnt, nstate = 0, state 가 된다.

그리고 계산한 결과값은 (-3)*(-1)**(1+0) == 3 이므로, 진행 가능한 방향이다. 따라서 진행이 가능하다.

1번으로 연결된 길도 함정이 아니기 때문에 cnt, nstate = 0, state 이며

이 때 계산한 결과값은 (-2)*(-1)**(1+0) == 2 이므로 진행 가능한 방향이다.

 

이제 다익스트라 알고리즘이 등장할 차례이다.

먼저 생성된 nstate 가 costs[d] 에 들어 있는지 확인해야 한다.

만약 들어있지 않거나, 현재 존재하는 값보다 새로운 도착 비용이 적다면 갱신해 주고, 이 루트를 그대로 탐색하면 된다.

만약 같은 함정을 밟고 왔는데 값이 크다면 과감히 무시 가능하다. 이 부분이 위 코드에서 가장 중요한 부분이다.

 

costs[d] 에는 d 에 도착하는 state(함정을 발동한 정보) : 소요비용 이 쌍으로 저장되기에 쉽게 그 값을 불러오고 확인 할 수 있다.  

 

그리고 최종적으로 end 에 도착하는 경우가 있다면, answer 값을 갱신해 주면 된다.