[프로그래머스 - 카카오] 동굴 탐험

문제

문제링크

• 0번부터 n-1번 까지 번호가 붙여져 있는 n개의 방으로 이루어진 동굴이 있다.
• 동굴에 들어가기 위한 유일한 입구는 0번 방
• 각 방들은 양방향 통행이 가능하며 _서로 다른 방을 연결하는 통로는 하나만 존재한다.
• 임의의 서로 다른 두 방 사이의 최단경로는 한 가지 경우밖에 없으며, 두 방 사이에 이동이 불가능한 경우는 없다.
• 방문했던 방은 재방문이 가능하다.
• 적어도 한 번 모든 방을 방문해야한다.
• 특정 방은 방문하기 전에 반드시 방문해야하는 방이 있다.(order 매개변수로 주어진다.)

n 는 방의 수
path 는 해당 방들을 이은 정보
order 는 사전에 방문해야하는 방들의 정보

문제풀이

문제에 대한 조건이 많았지만, 결국 DFS 문제였다.
조건으로는,
1. 방문한 적이 있는가?
2. 사전에 방문해야하는 곳이 존재한다면 그걸 방문했는가?
3. 이전 경로에서 2번 조건에 의해 방문하지 못한 방을 해결했는가?

를 체크해서 진행하면 된다.

import sys
sys.setrecursionlimit(10**9)

def dfs(v):
    if check[v]: # 방문한 적이 있는가?
        return
    if not check[prev_visit[v]]: # 사전에 방문해야하는 곳을 방문했는가?
        next_visit[prev_visit[v]] = v
        return
    check[v] = 1
    if next_visit[v]:
        dfs(next_visit[v])
    for i in graph[v]:
        dfs(i)

def solution(n, path, order):
    global N, graph, prev_visit, check, next_visit

    N = n
    start_room = 0
    num_of_room = 0

    # 그래프를 저장하는 배열
    graph = [[] for _ in range(N)]
    # 선방문해야 하는 방을 저장하는 배열, prev_visit[후방문방] = 선방문방
    prev_visit = [0 for _ in range(N)]
    # 그래프 노드 방문여부를 저장하는 배열
    check = [0 for _ in range(N)]
    #  후방문해야 하는 방을 저장하는 배열, next_visit[선방문방] = 후방문방
    next_visit = [0 for _ in range(N)]

    # 양 옆으로 길을 표시
    for room_A, room_B in path:
        graph[room_A].append(room_B)
        graph[room_B].append(room_A)

    # B에 방문하기 위해서는 A에 사전 방문해야한다.
    for room_A, room_B in order:
        prev_visit[room_B] = room_A

    # 0에 방문할 때 조건이 있다면 실패!
    if prev_visit[start_room]:
        return False

    check[start_room] = 1
    for i in graph[start_room]:
        dfs(i)

    for i in range(N):
        if check[i]:
            num_of_room += 1

    return True if num_of_room == N else False

개선할 점

문제가 길어서 많이 해매다가 결국은 타 블로그를 참고했다.
정해진 풀이가 있는 문제가 아니고 효율에 따라 다양한 자료구조를 활용한 모습을 볼 수 있었다.
카카오 코딩테스트의 마지막 문제답게 구현에 조건이 까다롭다고 생각했다.
하지만 생각보다 간소화해서 생각하는 습관이 필요할 것 같다.
지레 겁먹지 말자!

참고 블로그 링크