less than 1 minute read

문제

접근 방법

다른 도시로 가는 것을 반복하더라도 여행 계획대로 갈 수 있는지만 판단하면 되기 때문에 여행 계획의 첫 도시에서 다른 도시들로 갈 수 있는지만 판단할 수 있다면 풀 수 있을거라고 생각하였다.

bfs를 진행하면서 방문한 도시들 avail_cities은 시작점에서 갈 수 있는 도시들을 의미하기 때문에 이 도시들을 저장하고 여행 계획의 도시들 중에서 하나라도 avail_cities에 없다면 가능하지 않은 여행 계획이라고 판단하였다.

정답 코드


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

"""
bfs를 하면 한 점에서 다른 점으로 갈 수 있다면 양수로, 가능하지 않다면 0으로 나올 것이다.

 bfs의 시작점은 여행 계획의 첫 도시로 한다.
"""

n = int(input())

m = int(input())

graph = [[] for _ in range(n+1)]

for i in range(1,n+1):
  connects = list(map(int, input().split()))
  for j in range(len(connects)):
    if connects[j]==1:
      graph[i].append(j+1)
      graph[j+1].append(i)
  

travel = list(map(int, input().split()))

def bfs(start):
  visited = set()
  q = deque()
  q.append(start)
  visited.add(start)
  while q:
    tmp = q.popleft()
    for b in graph[tmp]:
      if b not in visited:
        q.append(b)
        visited.add(b)
  return visited

        
avail_cities = bfs(travel[0])

avail = True

for i in range(1,len(travel)):
  if travel[i] not in avail_cities:
    avail = False

if avail:
  print("YES")
else:
  print("NO")

You May Also Enjoy