문제
접근
BFS를 이용하는 문제이다.
조건은 생각보다 쉽다.
여행하고자하는 도시 중 하나를 정해서 BFS를 수행하고
여행하고자하는 도시들에 모두 방문했는지 체크해주면 된다.
문제에서 입력이 인접행렬로 주어져서, 그냥 인접행렬을 사용했다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from collections import deque
def bfs(adj, start, visit):
q = deque()
q.append(start)
visit[start] = 1
while q:
node = q.popleft()
for idx, item in enumerate(adj[node]):
if item and visit[idx] == 0:
visit[idx] = 1
q.append(idx)
n = int(input())
m = int(input())
adj = []
visit = [0] * n
for _ in range(n):
adj.append(list(map(int, input().split())))
city = list(map(int,input().split()))
start = city[0] - 1
bfs(adj, start, visit)
flag = True
for item in city:
if visit[item-1] == 0:
flag = False
if flag:
print('YES')
else:
print('NO')