그래프, BFS - 1976번: 여행 가자

1) 내가 설계한 로직

• travel[0]부터 BFS로 탐색하며 plans의 순서대로 도시를 pop해가며 진행
• cnt를 세어 n번 이상 돌았는데 계획을 pop하지 못하면 탐색 종료
• 연결 여부보다 BFS 탐색 순서와 plans 순서 일치를 확인하는 방식

2) 위 로직이 틀린 이유

• 여행 계획은 순서가 아니라 같은 연결 요소(그룹)인지 여부만 보면 됨
• cnt 제한과 plans pop 방식이 실제 연결 여부와 무관하게 탐색을 끊어버림
• 연결돼 있어도 BFS 순서에 따라 NO가 출력될 수 있음

3) 정답 로직

• travel[0]에서 BFS/DFS로 한 연결 요소(그룹)에 속한 도시들을 모두 탐색
• 여행 계획의 모든 도시가 그 연결 요소에 포함되는지 확인
• 포함되면 YES, 아니면 NO 출력하면 됨

from collections import defaultdict, deque

n = int(input())
m = int(input())

graph = defaultdict(set)

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

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



def bfs(start, graph):
    q = deque()
    q.append(start)
    visited = set()
    visited.add(start)

    while q:
        now = q.popleft()

        for neighbor in graph[now]:
            if neighbor not in visited:
                q.append(neighbor)
                visited.add(neighbor)
    
    # 시작 도시에 연결된 모든 도시들(그룹)의 집합 리턴
    return visited

visited = bfs(travel[0], graph)


for elem in travel:
    # 여행 계획 요소들이 모두 visited 안에 포함되어있다면 YES, 아니면 NO
    if elem not in visited:
        print('NO')
        break
else:
    print('YES')