프로그래머스 동굴 탐험 - BFS, 위상정렬

https://programmers.co.kr/learn/courses/30/lessons/67260

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

 

2020 카카오 인턴쉽 문제입니다.

위상 정렬을 모르고 풀었을 때는 도저히 감이 안왔었는데, 위상 정렬을 한 번 공부하고 나니 그렇게 어렵지 않은 문제인 것을 알게 됐습니다.

 

주어진 path를 위상 정렬을 풀기위한 형태로 유도한 뒤에 order에서 다시 한번 위상 정렬을 하기위한 준비 과정을 하면 됩니다.

 

주어진 그래프에서 방문 순서를 지켜야 하는 방 번호를 일방향 화살표로 연결해보고 생각해보시면 편합니다.

 

예를 들어 첫 번째 예시 그래프에서 6번 -> 7번의 순서를 지켜야한다면 6번에서 7번을 일방향 화살표로 연결해줍니다.

그 다음 시작 위치는 항상 0이기 때문에 0부터 점점 내려가면서 일방향 화살표라고 생각 (양방향이지만 고려할 필요가 없음)하고 문제를 푸시면 위상정렬 형태로 유도할 수 있습니다.

 

처음에 주어진 순서를 고려하지 않고 BFS를 돌면서 위상 정렬 때 사용할 리스트(room, indegree)를 만들어줍니다.

그 후 주어진 순서를 적용하여 해당 리스트에 값을 수정(room 추가, indegree +1)해줍니다.

 

모든 작업이 끝났다면 위상 정렬을 통해 동글을 모두 탐험할 수 있는 지 없는 지 판단해주면 됩니다.

사이클이 발생하면(for문이 n번 돌기전에 queue가 비어있다면) False, 그 외엔 True입니다.

 

from collections import deque

def bfs(room_tmp, n):
    room = [[] for _ in range(n)]
    indegree = [0 for _ in range(n)]

    visited = [False for _ in range(n)]
    q = deque()
    q.append(0)
    visited[0] = True
    
    while q:
        current = q.popleft()
        for i in room_tmp[current]:
            if visited[i]:
                continue
            room[current].append(i)
            indegree[i] += 1
            visited[i] = True
            q.append(i)
    return room, indegree
    
def solution(n, path, order):
    answer = True
    room_tmp = [[] for _ in range(n)]
    
    for a, b in path:
        room_tmp[a].append(b)
        room_tmp[b].append(a)
        
    room, indegree = bfs(room_tmp, n)
    for a, b in order:
        room[a].append(b)
        indegree[b] += 1

    q = deque()
    for i in range(n):
        if indegree[i] == 0:
            q.append(i)
    
    for i in range(n):
        if not q:
            answer = False
            break
        current = q.popleft()
        for j in room[current]:
            indegree[j] -= 1
            if indegree[j] == 0:
                q.append(j)
    
    return answer