[백준] 24391 귀찮은 해강이 - 파이썬 [골드5]

이번에 처음으로 접하게된 그래프 이론중 UNION에 해당하는 문제다.
이해하는데 너무 쉬웠지만, 정리는 해볼 필요가 있다고 판단하여 정리한다. 

---

문제

해강이는 앙중대학교에 다닌다. 해강이는 이번 학기에 강의코드 1번부터 N번까지 N개의 강의를 듣고 있다.

모든 강의는 강의코드와 동일한 번호의 건물에서 진행된다. 예를 들어, 강의코드가 1인 강의는 1번 건물에서 진행되고, 강의코드가 N-1인 강의는 N-1번 건물에서 진행된다.

해강이는 밖에 나오는 것을 싫어해서, 강의 시간표 순서대로 모든 강의를 들으면서 한 건물에서 밖으로 나와서 다른 건물로 이동하는 횟수를 최소화하고 싶다. 앙중대학교에는 다행히도 서로 연결되어 있는 건물들이 있어, 이 건물끼리는 밖으로 나오지 않고 이동할 수 있다.

해강이의 강의 시간표가 주어질 때, 밖에 나오는 것을 싫어하는 해강이를 위해 최소 몇 번만 밖에 나오면 되는지 구해보자. 맨 처음 강의를 들으러 이동하는 횟수는 세지 않는다.

---

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 105)과 연결되어 있는 건물의 쌍의 개수 M(0 ≤ M ≤ 105)이 공백으로 구분되어 주어진다.

두 번째 줄부터는 M줄에 걸쳐 i와 j(1 ≤ i, j ≤ N)가 주어진다. 이는 i번 건물과 j번 건물이 연결되어 있다는 의미이다. 건물이 자기 자신과 연결되거나, 이미 연결된 건물의 쌍이 다시 주어지는 경우는 없다.

마지막 줄에는 N개의 강의코드 Ai(1 ≤ Ai ≤ N)로 이루어진 강의 시간표가 공백으로 구분되어 주어진다.

---

출력

해강이가 밖에 나와야 하는 최소 횟수를 출력한다.

 

---

예제

---

전체소스코드

import sys
input = sys.stdin.readline

def union_find(V):
    if V != buildings[V]:
        buildings[V] = union_find(buildings[V])
    return buildings[V]

def union(A, B):
    A = union_find(A)
    B = union_find(B)

    if A > B:
        buildings[A] = B
    else:
        buildings[B] = A


N, M = map(int, input().split())  # N -> 건물갯수 / M -> 연결되어있는 건물 케이스

buildings = [0] * (N + 1)  # 건물들

for i in range(1, N + 1):  # 1,2,3... 입력
    buildings[i] = i

# 연결되어있는 건물 입력
for i in range(M):
    A, B = map(int, input().split())
    union(A, B)

# 시간표
timeTable = list(map(int, input().split()))
answer = 0
for i in range(1, len(timeTable)):
    if union_find(timeTable[i - 1]) != union_find(timeTable[i]):
        answer += 1

print(answer)

---

풀이

천천히 살펴보자.

위의 예제출력으로 예시를 들어보자. 일단 코드가 실행되면 아래와같은 입력이 들어올 것이다.

#예제
5 3 # 건물수 / 연결되어있는 건물 케이스 수
1 3 # 1번건물과 3번건물 연결
2 5 # 2번건물과 5번건물 연결
3 4 # 3번건물과 4번건물 연결
1 2 3 5 4 # 수업시간표 

#출력
4

우리가 생각을해보자. 1,2,3,4,5 번 건물이 존재하고, 각 연결되어있는 건물들이 있다.
1번건물과 3번건물이 연결되어있고, 3번건물과 4번건물이 연결되어있다면 결국, 4번건물에서 1번건물로 건너갈 수 있다.
2번건물과 5번건물이 연결되어있으니, 5번건물에서 2번건물로 건너갈 수 있다.
이렇게 우리는 부모와 자식노드 개념으로 자식 노드를 집었을때 그의 부모노드의 값으로 비교하면 된다는 말이다.

천천히 코드를 보면서 정리하면,

N, M = map(int, input().split())  # N -> 건물갯수 / M -> 연결되어있는 건물 케이스

buildings = [0] * (N + 1)  # 건물들

for i in range(1, N + 1):  # 1,2,3... 입력
    buildings[i] = i

# 연결되어있는 건물 입력
for i in range(M):
    A, B = map(int, input().split())
    union(A, B)

우리는 일단 buildings에 1,2,3,4,5를 입력받았다.
그다음 건물케이스 만큼 반복하면서 A,B ( ex. 1 3 )을 입력받으면서 union 함수와 union_find를 호출한다.

def union_find(V):
    if V != buildings[V]:
        buildings[V] = union_find(buildings[V])
    return buildings[V]

def union(A, B):
    A = union_find(A)
    B = union_find(B)

    if A > B:
        buildings[A] = B
    else:
        buildings[B] = A

위의 함수가 결정적이라고 볼수있는데, union을 수행하면서 union_find로 부모노드를 찾는 과정을 수행한다.
A에서 1을 입력받고, B에서 3을 입력받으면
union_find에서 V값(1)이 buildings[1]과 같은지 체크한후, return 한다. 3도 마찬가지로 수행한다.
그 다음, A 와 B의 값을 비교한 후에 buildings에 값을 넣어준다.
A > B 일경우에는 buildings[A] = B , 그외에는 buildings[B] = A . 이 과정을 입력받으며 수행하고 나면 아래의 배열이 나온다.

#union수행하기전 buildings
buildings = [1,2,3,4,5]

# A = 1, B = 3을 입력받은 후, union 수행후 buildings
buildings = [1,2,1,4,5]

# A = 3, B = 4를 입력받은 후, union 수행후 buildings
# 여기서 V(3)은 buildings[3]과 값이 다르기 떄문에 union_find를 수행한다.
# union_find에서는 값이 다르면 buildings[3]의 값을 가지고 다시 union_find를 재귀하여 부모값을 찾는다.
buildings = [1,2,1,1,5]

# A = 2, B = 5를 입력받은 후, union 수행후 buildings
buildings = [1,2,1,1,2]

위와 같은 배열이 정리가 되었다면, 이제 시간표대로 밖으로 나온 횟수를 카운트 해준다.

# 시간표
timeTable = list(map(int, input().split()))
answer = 0
for i in range(1, len(timeTable)):
	# union_find를 통해 부모값을 찾는다.
    if union_find(timeTable[i - 1]) != union_find(timeTable[i]):
        answer += 1

print(answer)

 즉, 서로 부모값이 다르다면 다른 집합에 있다는것으로 간주하고 밖으로 나와야한다는 결론이 나오기때문에, 카운트를 1씩 더해준다.

---