100년 뒤 개발자 한승규입니다.

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

BFS, DFS의 문제는 아니고 find와 union을 사용해서 해결하는 문제이다.

find 함수

def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]

해당 그래프에서 최상위 노드를 구해주는 함수이다.

만약 find로 구한 노드가 같으면, 같은 그래프에 속하는 노드인 것이다.

union 함수이다.

같은 그래프에 속하지 않는 노드들을 연결해주는 함수이다.

def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1

이 함수들을 이용해서 같은 그래프에 속하는 노드끼리 묶어주고, 마지막에 여행을 가려는 노드들이 같은 그래프에 있는 지 확인을 해주면 된다.

import sys

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

parent = [i for i in range(N)]
rank = [0 for _ in range(N)]

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

trip = []

if M > 0:
    trip = list(map(int, sys.stdin.readline().split()))


def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]


def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1


for i in range(N):
    for t in range(i):
        if city[i][t] == 1:
            if find(i) != find(t):
                union(i, t)

standard = find(trip[0] - 1)
flag = True

for i in range(1, M):
    if standard != find(trip[i] - 1):
        flag = False

print('YES' if flag else 'NO')