여행 계획 그래프

각 여행지는 1~N번 까지의 번호로 규정되어 있습니다. 두 여행지 사이에는 이동할 수 있는 도로가 있습니다. 그리고 도로는 양방향으로 이동이 가능합니다. 여행 계획을 세운 뒤에 이 여행 계획에 가능한지 여부를 판단하고자 합니다.

예시 5 4 (도시의 개수, 여행 계획하는 도시 수) 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 2 3 4 3 YES 여행 계획이 가능하다면 YES, 불가능 하다면 NO

처음에 문제를 대충 보고 실컷 잘못? 풀고 있었습니다. 위 계획에서 3에서 4로 갈 수 있는 방법이 없어서 NO라고 했는데 예시에서는 YES라고 하지요 2에서 3그리고 4로는 못가지만 다시 2로 돌아서 4로 갈 수 있고 3역시 마찬가지

결국 이 문제는 서로소 집합 알고리즘을 이용하여 그래프에서 노드간 연결성을 파악해서 해결할 수 있다. 여행 계획에 해당하는 모든 노드가 같은 집합에 속하기만 하면 가능한 여행 경로이기 때문. 두 노드 사이에 도로가 존재하는 경우에는 union연산을 통해서 서로 연결된 두 노드를 같은 집합에 속하도록 만든다.

#여행지의 개수와 여행 계획에 속한 여행지의 개수 입력받기
n,m = map(int, input().split())
parent = [0]*(n+1) #부모테이블 초기화

#부모 테이블상에서 부모를 자기 자신으로 초기화
for i in range(i, n+1):
    parent[i] = i

각 여행지의 개수와 여행 계획을 위해서 방문할 도시를 고르고 각 도시에 대해서 부모테이블을 초기화를 해줍시다.

#특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
    #루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

원소가 속한 집합을 찾아 줍시다. 해당 노드가 루트 노드가 아니라면 루트 노드를 찾을때까지 재귀적으로 호출을 해주게 되고 루트노드를 반환하는 함수 입니다.

#두 원소가 속한 집합을 찾기
def union_parent(parent, a, b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

두 원소가 속한 집합을 찾는고 연결하는 함수 입니다.

부모노드 테이블과 두 노드를 집어 넣게 되는데 a와 b에 대해서 각 루트노드를 찾게 되고 갱신하게 됩니다.

결과적으로 a와 b는 같은 루트노드를 가지게 됩니다.

#union 연산을 각각 수행
for i in range(n):
    data = list(map(int, input().split()))
    for j in range(n):
        if data[j] == 1: #연결된 경우 union 연산 수행
            union_parent(parent, i+1, j+1)

입력과 동시에 각 값에 대해서 union연산을 수행을 합시다.

#여행 계획 입력받기
plan = list(map(int, input().split()))

result = True
#여행 계획에 속하는 모든 노드의 루트가 동일한지 확인
for i in range(m-1):
    if find_parent(parent, plan[i]) != find_parent(parent, plan[i+1]):
        result = False

#여행 계획에 속하는 모든 노드가 서로 연결되어 있는지(루트가 동일한지) 확인
if result:
    print("YES")
else:
    print("NO")

마지막은 이제 함수를 사용하면 됩니다. 여행 계획을 입력받고 이를 findparent를 이용해서 부모가 같은지 검증을하고

아니라면 False를 반환 받아서 이를 출력하면 됩니다.