풀이

1. 여행 계획에 속한 도시들을 어떤 경로로 가던지 가기만 하면 된다. 즉, 여러 번 방문하는 것이 가능하기 때문에, 여행 계획에 속한 도시들이 뭔가 하나로 연결이 되어있다면 방문할 수 있는 것이다. 문제의 예시를 보고 접근해보자
2. 문제의 예시는 아래와 같은 상황이다.

1번 도시와 3번도시가 연결되지 않은 것을 빼고 모두 연결되어 있는 것을 알 수 있다. 즉, 1,2,3 어디를 가던 여행할 수 있다. (3을 간다고 해도 1에서 2 건너서 가도 됨)

반대로 안되는 케이스 생각해보자

만약에 위의 사진과 같이 4번 도시랑 5번도시만 따로 떨어져 있다면 여행 계획에 1,2,3,4가 있는 경우 3에서 4로 건너가는 방법이 없기 때문에 여행할 수 없다.

즉 각 도시들이 연결되어 있는 루트 노드를 찾아서 내가 방문할 도시들이 모두 같은 루트 노드를 가지고 있으면 YES를 출력하게 하면 된다. 이를 위해서 UNION FIND를 사용하면 된다.

# 1976 여행가자
N=int(input())
M=int(input())
parent=[i for i in range(N+1)]

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

def union(parent,a,b):
    a=find(parent,a)
    b=find(parent,b)
    if a<b:
        parent[b]=a # b의 부모를 parent_a 값으로 바꾸겠다. 즉 a의 부모가 b의 부모이다. b가 a보다 클때.
    else: # 더 작은 수를 부모로 설정
        parent[a]=b


for start in range(1,N+1): # start city number
    destination=list(map(int,input().split()))
    for idx in range(N):
        if destination[idx]==1:
            union(parent,start,idx+1)

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

root_site=parent[travel_list[0]]

for site in travel_list:
    if parent[site]!=root_site:
        print("NO")
        exit()

print("YES")

주의할 점

def find_parent(parent,x):
    if parent[x]!=x: # parent[x]==x 는 루트 노드라는 것을 의미한다.
        return find_parent(parent,parent[x])
    return x

위와 같이 find함수 선언하면 parent 배열 값이 루트노드를 한번에 계산하지 못하고 부모테이블을 거쳐서 거슬러 올라가야한다. 그림으로 나타내면 아래와 같다.

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

로 find 함수를 선언해야한다. 이렇게 하면 최상단 노드를 parent에 저장 가능하다.그림으로 나타내면 아래와 같다.