(Python/파이썬) - 백준(BOJ) 1976번 : 여행 가자

https://www.acmicpc.net/problem/1976

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라는 여행경로를 통해 목적을 달성할 수 있다.

 

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

 

 

 

---

• 풀이 :

그래프 탐색 문제입니다.

 

1. 주어진 여행경로 중 아무 지점이나 하나를 골라 해당 지점을 시작으로 bfs를 실시합니다.

 

2. bfs를 실행한 이후 여행경로들에 있는 모든 지점이 방문처리 되어있지 않다면 여행경로가 분리집합으로 나눠진다는 것이므로 NO를 출력하고 아니라면 YES를 출력합니다.

 

 

 

---

• 소스코드 : 

import sys
from collections import deque
input = sys.stdin.readline

def bfs(start):
    queue = deque()
    queue.append(start)
    visited[start] = True
    while queue:
        curr = queue.popleft()
        for next in graph[curr]:
            if not visited[next]:
                queue.append(next)
                visited[next] = True
N = int(input())
M = int(input())
g = [list(map(int,input().split())) for _ in range(N)]
graph = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if g[i][j] == 1:
            graph[i].append(j)
visited = [False for _ in range(N)]
plan = list(map(int,input().split()))
bfs(plan[0]-1)
answer = True
for i in plan:
    if not visited[i-1]:
        answer = False
        break
if answer:
    print("YES")
else:
    print("NO")