동굴 탐험

문제

총 노드 갯수와 노드 끼리의 연결정보, 우선 방문 노드 정보가 배열로 주어진다.

어떤 노드를 가려면 우선 방문해야 되는 노드가 있으며,

그 노드를 방문할수 없는 네트워크라면 False, 가능한 네트워크라면 True를 반환한다.

 

풀이방법

bfs로 풀었는데, 0부터 시작하면서 모든 노드를 순회하고,

우선 방문해야 되는 노드가 있는 노드라면 기다림 표시를 하고,

다른 노드가 기다리고 있던 노드라면 큐에 다시 방문해야 되는 노드를 추가해 준다.

그리고 모든 노드에서 방문하지 않은 노드를 큐에 추가한다.

 

programmers.co.kr/learn/courses/30/lessons/67260?language=python3

코딩테스트 연습 - 동굴 탐험

from collections import defaultdict, deque

def solution(n, path, order):
    pending, visited = [False] * n, [False] * n
    v = defaultdict(list)
    for start, end in path:
        v[start].append(end)
        v[end].append(start)
    get_before = {v: k for k, v in order}
    before_set = {k for k, v in order}
    get_next = {k: v for k, v in order}
    next_set = {v for k, v in order}
    queue = deque([0])
    while queue:
        target = queue.popleft()
        # 다른곳에 다녀왔는지 체크해야되는 경우
        if target in next_set:
            # 다른곳에 아직 가보지 못한 경우
            if visited[get_before[target]] is False:
                # 이 노드는 대기 표시
                pending[target] = True
                continue
        # 출발하는 곳인데
        elif target in before_set:
            # 이곳에서 출발하기를 기다리는 경우
            if pending[get_next[target]]:
                # 큐에 도착할 곳 다시 추가
                queue.append(get_next[target])
        # 아직 갔던 곳이 아니면 큐에 추가
        nexts = v[target]
        for next in nexts:
            if not visited[next]:
                queue.append(next)
        visited[target] = True
    return True if all(visited) else False


if __name__ == '__main__':
    print(solution(9, [[0, 1], [0, 3], [0, 7], [8, 1], [3, 6], [1, 2], [4, 7], [7, 5]], [[8, 5], [6, 7], [4, 1]]))
    print(solution(9, [[0, 1], [0, 3], [0, 7], [8, 1], [3, 6], [1, 2], [4, 7], [7, 5]], [[4, 1], [8, 7], [6, 5]]))