23.06.23 파이썬 코딩 퀴즈#258 동굴 탐험 (프로그래머스 스쿨)

이번 문제는 통굴 탐험 문제이다

카카오 관련 문제답지 않게 0번부터 방 번호가 매겨져 있다.

일단 설명을 더 확인해보자.

방 개수는 n 개 이고, 각 통로들이 연결하는 두 방의 번호가 담긴 2차원 배열 path, 프로도가 정한 방문 순서가 담긴 2차원 배열 order 가 매개변수로 주어진다.

프로도가 세운 탐험 계획은 다음과 같다.

1. 모든 방을 적어도 한 번은 방문해야 한다

2. 특정 방을 방문하기 전에 반드시 먼저 방문해야 할 방이 정해져 있으며, 1개 이거나 없을 수도 있다.

다만, 특정 방이 A 라고 가정하고 반드시 방문해야 할 방이 B 일때, B를 방문한 이후에 다른 C 방을 방문해도 문제없다.

path 의 경우 두 바의 번호가 순서없이 존재한다.

하지만 order 의 경우 order[i] 의 0을 먼저 방문하고 1을 방문해야 한다.

 

이제 입출력 예를 통해 어떤 형태인지 확인해 보자.

입출력 예 1 번을 그림으로 나타내면 위와 같다.

그리고 주어진 order에 의해 반드시 지켜야할 방문 순서도 정해졌다.

먼저 0에서 출발해 3, 6 순서로 방문하면 order[0] 의 A 를 방문한다. 그리고 다시 3으로돌아와 0, 7을 방문하여 order[i] 를 끝낸다. 그리고 이제 4를 방문하여 order[1] 의 A를 방문하여 해제하고, 7, 0, 1 을 방문하게 되면 order[1] 역시 완료된다. 이제 8로 이동하여 order[2]의 A를 해제하면 나머지 모든 노드들을 방문 가능하다.

 

입출력 예 3번을 살펴보면

위와 같은 통로를 가진 동굴이 생긴다.

그리고 order 에 의해 먼저 방문해야 할 지점은 4, 8, 6번 이고 막혀있는 부분은 1, 7, 5 이다.

6번을 방문해서 5번이 해제되지만 여전히 1,7이 막혀있으므로 더이상의 탐험은 불가능하다.

 

먼저 문제의 접근 방법을 이해해야 한다.

입출력 예제 1번이다.

먼저 0번 동굴에서 시작하게 되며, 현재 방문 가능한 동굴은 3번 하나 뿐이다. (1, 7 막힘)

그렇다면 3번 동굴을 방문하게 되고, 3번 동굴은 6번 동굴 하나이기 때문에 6번 동굴을 방문하게 되고, 이 때, 막혀 있는 7번 동굴이 해제된다.

이제 돌아가야 할 곳은 3번이 된다.

 

처음 생각한 방법은 단방향 그래프를 만들고, 만약 해당 노드의 하위 노드들을 모두 방문한 경우에만 해당 노드를 방문처리 하는 방법으로 코드를 작성해 보았다.

Node 클래스를 생성하고, 단방향 그래프를 만들기 위해 make_graph() 함수를 정의해 주었다.

이를 토대로 각 노드들을 작성하였다.

그 다음 시작점을 0으로 설정하고, n값을 감소시키는 방법으로 while문을 작성하였다.

먼저 해당 번호의 노드정보를 불러와서, 선행 방문 동굴이라면 막힌 동굴을 해제해준다.

0번 노드를 제외한 모든 노드들은 parent 값을 가지게 되며, 이를 이용해 현재 fr값이 None, 즉 0번 동굴에서 더 이상 진행이 불가능해 상위 동굴로 이동한 경우에 False 를 return 하도록 해두었다.

 

이제 다음 동굴을 탐색하게 되는데, 총 3가지 경우가 존재한다.

 

1. 다음 동굴로 이동 진행이 가능한 경우:

이 때에는 fr 값을 바로 갱신해주고 break를 통해 반복문을 빠져나오게 된다. 즉 탐색이 가능한 지점까지 한번에 탐색을 진행한다.

 

2. 막힌 동굴이 있는 경우:

이 경우는 재방문이 필요하다. flag 를 1로 바꿔준 뒤, 나머지 하위 동굴을 탐색 가능한지 계속 탐색한다.

 

3. 모든 하위 동굴을 이미 방문한 경우:

이는 하위 동굴이 없는 최하위 동굴에도 적용이 된다. 즉 flag = 0 이기 때문에 현재 노드의 부모(상위)로 이동한다.

 

코드 자체에는 문제가 없어 보이지만, 거의 대부분의 문제에서 시간초과에 걸린다.

즉 비효율적이다.

다음은 deque()를 활용한 DFS 탐색법이다.

처음 코드와 다르게 따로 노드를 작성하지 않고, 리스트를 만들어 막힌 동굴과 방문해야 하는 동굴을 저장해 주었다.

이제 이중 while문을 통해서 동굴을 탐색하게 되는데, 첫번째 조건은 locked(잠긴 동굴 수)이 존재할 때 이며, 두번째 조건은 q(탐색 가능한 좌표)가 존재할 경우이다.

그리고 q에는 order에 저장된 선행되어야 하는 동굴의 번호가 들어간다.

즉 입구에서 목표까지가 아닌, 목표에서 입구까지의 경로를 탐색하게 된다.

이제 탐색을 통해 이미 방문하거나(돌아가기 방지), 중간에 막힌 동굴을 제외하고 q에 넣어주면서 탐색을 하며, 입구(0번)까지 도착한 경우라면 flag 를 1로 갱신하고 종료한다.

그리고 다시 조건문에 의해 locked 값은 1 감소시켜주고, 해당 경로를 전부 방문처리해 준다.

이렇게 다시 방문처리 하는 이유는, 다른 경로를 탐색하다가 해당 경로를 타게 되었을때 바로 두번째 반복문을 탈출하기 위해서이다.

정확성 테스트는 모두 통과하였지만, 효율성 테스트를 시간제한으로 인해 통과하지 못했다...

 

내가 해당 문제를 풀면서 가장 바보같이 고민한 부분이 바로 어디로 돌아가야 하는가 였다.

자꾸 왔던 경로를 돌아가려고 하니, 시간제한에 걸리는 거였다. 그냥 막힌 경로는 따로 저장해 주고, 나중에 다시 그 경로를 탐색해 주면 간단히 해결 가능한 문제였다.

 

먼저 다른 부분은 거의 비슷하고 after_visit 딕셔너리가 추가되었다.

입출력 예 1번을 위 코드로 탐색해 보자.

해당 문제의 모든 입구는 0 이다. 

0번은 언제나 뚫려 있고, 해당 동굴에서는 갈 수 있는 길은 1,3,7번 이다.

순서대로 1번을 먼저 방문하게 되면, 현재 동굴은 막혀있는 상태고, 아직 4번 동굴은 탐색하지 않았기에 after_visit 에는 4: 1 이 저장된다.

그 다음은 3번 동굴이다, 문제없이 6번동굴까지 연결된다

그 다음은 7번 동굴이다. 동굴은 막혀 있지만, 이미 6번 동굴을 방문했기에 탐색 가능하다.

그리고 q에는 [4,5]가 추가된다. 여기서 4번 동굴을 탐색할때 4는 이미 키값으로 after_visit에 저장되어 있기에 이때 1번을 다시 q에 전달하게 된다.

 

만약 방문 순서가 0 -> [1,7,3] 이라고 하면 after_visit 에는 4:1 과 6:7 이 들어가게 되고, 3번을 방문 후 6번을 방문할 때, 여기서 다시 7번을 q에 넣어주게 된다.

 

이렇게 돌아가는 개념이 아닌 중간에 막혔던 경로를 다시 돌게 되면, 굳이 방문처리에 머리를 쓸 필요도 없고, 입구까지가는 시간도 줄일 수 있다.