백준 - 여행 가자 / Gold 4 / 1976번 / Python

문제 📋

백준 - 여행 가자

풀이 📝

import sys
from collections import defaultdict

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

cities = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
plan = list(map(int, sys.stdin.readline().split()))  # 여행 계획


def solution(n, m, cities):
    if m == 1 and n > 0:  # 도시 하나만 방문할 계획이고 해당 도시가 존재하면 YES
        return "YES"

    graph = defaultdict(list)

    for i in range(n):
        for j in range(n):
            if cities[i][j] == 1:
                graph[i + 1].append(j + 1)

    for i in range(m - 1):  # 각 여행 계획에 대하여 출발점과 목적지를 정의.
        start = plan[i]
        destination = plan[i + 1]

        stack = [start]
        visited = [False] * (n+1)
        visited[start] = True
        is_reachable = False

        while stack:  # DFS 탐색
            city = stack.pop()
            visited[city] = True

            if city == destination:  # 목적지에 도착하면 탐색 중지하고 다음 여행계획으로 넘어감.
                is_reachable = True
                break

            for item in graph[city]:
                if not visited[item]:
                    stack.append(item)

        if not is_reachable:  # 만약 DFS로 전체 탐색해도 목적지에 도달 할 수 없다면 NO
            return "NO"
    
    return "YES"  # 모든 여행 계획의 목적지에 대하여 전부 도달 할 수 있다면 YES


print(solution(n, m, cities))

도시들의 연결 정보들과 여행 계획이 주어지면
계획한 모든 도시들을 순서대로 방문 할 수 있는지 구하는 문제이다.

근데 어떻게 돌아가든 무조건 도착만 하면 갈 수 있는 것으로 판단하기 때문에
여행 계획에서 출발점과 목적지를 정의하고 도달 할 수 있는지만 계속해서 판단하면 된다.

따라서 먼저 도시들의 연결 정보들로 그래프를 구성하였고
여행 계획을 순회하면서 출발점과 목적지를 정의했다.

그런 다음 DFS 탐색을 하여 목적지에 도달 할 수 있는지 체크해주었다.

또한 도시들의 수는 최대 200이고 여행 계획은 최대 1000이여서
최악의 경우 200,000번 탐색하게 되기 때문에 효율성 측면에서도 문제가 없다고 판단했다.