[백준/Python3] 1976 여행 가자

✈Problem

1976 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

Solution

여행 계획의 순서만 유지되면 중간에 다른 도시를 방문해도 되므로 첫번째 도시를 기준으로 방문할 수 있는 모든 도시를 찾는 방법을 생각했다. BFS로 그래프를 탐색하면서 첫번째 도시와 연결된 도시를 통해 갈 수 있는 모든 도시를 찾아 course 리스트에 저장해주었다.
그리고 계획에 포함된 도시가 방문 가능한 도시에 모두 포함되어 있다면 YES를 출력하고, 아니라면 NO를 출력하도록 했다.

Python Code

from sys import stdin
from collections import deque

N = int(stdin.readline())
M = int(stdin.readline())

connect = [list(map(int, stdin.readline().split())) for _ in range(N)]
plan = list(map(int, stdin.readline().split()))

course = []
q = deque([plan[0] - 1])
while q:
    curr = q.popleft()
    course.append(curr + 1)
    for i in range(N):
        if connect[curr][i] == 1 and i + 1 not in course:
            q.append(i)
result = "YES"
for p in plan:
    if p not in course:
       result = "NO"
       break

print(result)

문제를 풀면서 어이없는 실수를 하나 했다. 계획대로 여행이 불가능한 경우에 아무것도 출력하지 않도록 코드를 작성했다. 역시 문제에 주어진 조건을 꼼꼼하게 읽어야 한다..