2020 카카오 인턴십 동굴 탐험 풀이 With Python

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/67260

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

이 문제는 그래프 문제입니다. 실제 시험 당시에는 정확도 문제에서 1개를 틀렸는데, 이번에 문제를 다시 풀면서 해결하였습니다. 저는 무조건 0번 방에 들어갈 수 있다고 생각하였는데, 0번 방에 들어가기 위해 먼저 방문해야 할 조건이 있을 수도 있다는 것을 생각하였고, 이러한 조건을 추가하자 통과를 하게 되었습니다. 제가 해결한 풀이는 먼저 갈 수 있는 곳을 다 가고, 만약 해당 방에 들어가기 위해 필요한 선행 방이 필요하다면 선행 방을 방문하였을 때 방문하고 방문하지 않았을 때는 방문하지 않았습니다. 또한 내가 방문한 방이 다른 방의 선행 방이고, 과거에 방문하였었다면 그 방을 방문하도록 하였습니다. 그리고 방문한 방의 개수와 전체 방의 개수가 같다면 True를 같지 않다면 False를 반환하였습니다. 소스코드는 아래와 같습니다. 

 

def solution(n, path, order):
    from collections import deque
    queue = deque()
    answer = False
    visit = [0] * n
    cango = [0] * n
    visit[0] = 1
    cango[0] = 1
    must = {}
    must2 = {}
    for i in order:
        must[i[1]] = i[0]
        must2[i[0]] = i[1]
    matrix = [[] for _ in range(n)]
    for i in path:
        matrix[i[0]].append(i[1])
        matrix[i[1]].append(i[0])
    if must.get(0) is None:
        queue.extend(matrix[0])
    while queue:
        p = queue.popleft()
        cango[p] = 1
        # 선행지점 없을 경우
        if must.get(p) is None:
            visit[p] = 1
            for i in matrix[p]:
                if visit[i] == 0:
                    queue.append(i)
            if must2.get(p) is not None and cango[must2[p]]:
                queue.append(must2[p])
        else:
            # 선행지점을 방문하였을 경우
            if visit[must.get(p)] == 1:
                visit[p] = 1
                for i in matrix[p]:
                    if visit[i] == 0:
                        queue.append(i)
    if sum(visit) == n:
        answer = True

    return answer

 소스코드에 대한 질문이 있으시면 댓글 남겨주시면 답변드리겠습니다. 읽어주셔서 감사합니다. :-)