[코딩 테스트] 2020 카카오 인턴십 동굴탐험

작성일 | In |

카카오 2020 인턴십 문제 중 가장 어려웠다고 생각하는 동굴 탐험 문제입니다.

기본적으로 그래프 탐색 문제이고, node의 숫자가 최대 20만으로 꽤 많긴 하지만 같은 node에 여러 번 방문하는 경우가 많지 않아 DFS / BFS로도 풀이가 가능합니다.


코드

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
46
47
48
49
50
51
52
53
54
from queue import Queue

def solution(n, path, order):
    # 전처리 구간
    answer = True
    trees = [[] for _ in range(n)]
    targeting = [None] * (n)
    be_targeted = [None] * (n)
    visited = [False] * (n)

    for v, w in path:
        trees[v].append(w)
        trees[w].append(v)
    for v, w in order:
        targeting[v] = w
        be_targeted[w] = v

    parents = [None] * n

    parent_queue = Queue()
    parent_queue.put(0)

    while not parent_queue.empty():
        node = parent_queue.get()
        for no in trees[node]:
            if no and parents[no] is None:
                parents[no] = node
                parent_queue.put(no)

	# 전처리 구간 끝
    
    # 탐색 구간
    stk = [0]

    cnt = 0
    while stk:
        node = stk.pop()

        if be_targeted[node] and not visited[be_targeted[node]]: continue # 방문할 수 없는 경우
            
        visited[node] = True # 방문 처리, stk에 들어왔다면 모든 방문처리는 이 곳에서 이루어진다.
        
        if targeting[node]:
            p = parents[targeting[node]]
            if visited[p]: # 방문할 수 없는 경우 2(부모 node가 방문완료 되었을때만 stack에 추가)
                target = targeting[node]
                stk.append(target)

        for no in trees[node]: # 현재 node에서 갈 수 있는 node들 전부 stack에 추가
            if not visited[no]:
                stk.append(no)
	# 탐색 구간 끝
    
    return all(visited) # 모든 방에 방문했는지 확인



기본적인 생각의 흐름은 다음과 같다.

  1. 그래프를 트리 구조로 만들어 각 node의 부모 node를 알게 한다.
  2. 0번 Node부터 순회하며 갈 수 있는 방에는 간다.

여기서 갈 수 있는 방은 2가지이다.

  • 날 노리고 있는 Node가 없는 경우(먼저 방문해야하는 방이 없는 경우)
  • 날 노리고 있는 Node가 방문완료된 경우(먼저 방문해야하는 방이 방문완료된 경우)

갈 수 없는 방도 2가지 경우가 있을 수 있다.

  • 부모 Node가 방문되지 않은 경우(0번에서 출발해 임의의 Node까지 가기 위해서는 임의의 Node의 부모 Node를 거치지 않으면 불가능하기 때문)
  • 날 노리고 있는 Node가 방문되지 않은 경우


전처리 구간에서는 다음과 같은 작업을 한다.

  1. 필요한 변수들을 선언한다.

  2. path와 order를 순회하며 그래프 구조 / 선방문 구조를 완성한다

    • ex) 6 -> 4일 경우,

    • 1
      2
      targeting[6] = 4
be_targeted[4] = 6
    • 위와 같이 저장된다.

  3. parents 리스트에 index 번호 : Node, value : 부모 Node형태로 부모 Node 정보를 저장한다.


탐색 구간에서는 다음과 같이 탐색한다.

  1. DFS를 이용해 탐색한다.
  2. 날 노리고 있는 Node가 있고 그 Node가 아직 방문되지 않은 경우, 로직을 돌지 않는다.
  3. 그렇지 않을 경우 일단 방문처리하고, 나와 연결되어 있는 Node 중 방문 가능한 Node들을 골라 stack에 집어넣는다.
  4. 반복하며 탐색을 완료한다.


이렇게 탐색 가능한 모든 Node를 탐색했을 때, 만약 방문되지 않은 Node가 있다면 모든 방을 방문하지 못한 것이므로, visited 리스트에 대해서 all 함수를 사용해 한 곳이라도 방문하지 못한 Node가 있다면 False를, 모두 방문했다면 True를 Return한다.