[그래프이론] 여행계획

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20분 + a

1. 문제 설명

- 여행계획을 짜려고 하는데 나라들이 연결되어만 있으면 여행을 갈 수 있다. 나라들이 연결되어 있는 정보와 여행 일정에 대한 입력이 들어오면 해당 여행 일정이 가능한지 출력을 하는 문제

2. 접근 방식

- 그래프 알고리즘을 이용해서, 여행일정에 해당하는 노드들이 서로 연결되어 있는지 확인하면 된다.

- 여행일정에 해당하는 노드들이 서로 연결되어 있다는 것은 하나의 집합(부모)에 묶여있다는 뜻이라고 생각할 수 있다. 

3. 코드

n, m = map(int, input().split())
ls = []
for _ in range(n):
    ls.append(list(map(int, input().split())))
    
plan = list(map(int, input().split()))

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
    
def union_parent(parent, x, y):
    a = find_parent(parent, x)
    b = find_parent(parent, y)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
parent = [0]*(n+1)
for i in range(1, n+1):
    parent[i] = i

for i in range(n):
    for j in range(n):
        if ls[i][j] == 1:
            union_parent(parent, i+1, j+1)
            
result =True
# 여행 계획에 속하는 모든 노드의 루트가 동일한지 확인 (핵심코드)
for i in range(m-1): # m - 1번째인 이유는 다음 꺼랑 비교하기 때문이다. 
    if find_parent(parent, plan[i]) != find_parent(parent, plan[i]+1):
        result = False

print("YES" if result else "NO")

4. 코멘트

- 모든 코드를 다 구현해놓고 알고리즘을 제대로 풀어내지 못해서 시간이 오래걸렸다.
- 결국 여행경로가 하나의 집합에 묶여있다면 여행자는 움직일 수 있는 것으로 이해하면 됐다.

- 서로소 '집합' 알고리즘'이라는 것을 다시 한 번 기억해둘 필요가 있을 것 같다. 결국 그래프 문제이지만, 집합을 구하는 문제라고 생각할 수도 있을 것 같다.