24391번 귀찮은 해강이

문제 설명

서로 이어져 있는 건물들이 있고 강의 시간표가 주어질 경우, 건물 이동 시 밖에 나와야하는 최소의 횟수를 구하는 문제이다.

 

내가 푼 방식

이 문제는,,,, 유니온 파인드 방법으로 하면 될 것 같다는 생각은 들었지만, 내 방식대로 풀고 싶어 시간을 조금 들였지만, 결국에는 유니온 파인드로 문제를 풀게 되었다...

그래프

연결된 건물들이 있고 연결되지 않은 건물로 이동할 경우의 횟수를 세는 것이다.

이것은 이어진 노드들끼리 그룹화되어 있는 상황에서 노드를 주어진 번호순으로 순회할 때 그룹을 이동하는 회수를 구한다고 생각하면 된다.

코드

우선 내 코드를 확인해보자

import sys
input = sys.stdin.readline

def find(class_room):
    if class_room == parent[class_room]:
        return class_room
    parent[class_room] = find(parent[class_room])
    return parent[class_room]

def union(a,b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent != b_parent:
        parent[a_parent] = b_parent

n,m = list(map(int,input().split()))
parent = [i for i in range(n+1)]
result=0

for i in range(m):
    a,b = list(map(int,input().split()))
    union(a,b)
        
lecture_list = list(map(int,input().split()))
for i in range(n-1):
    prev_class,after_class = lecture_list[i],lecture_list[i+1]
    
    if find(prev_class) != find(after_class):
        result+=1
print(result)

알고리즘 예시 사진

알고리즘 규칙

첫 세팅

노드가 8개가 있다고 가정해보면 위와 같은 예시 사진이 첫 모습일 것이다.

위의 표는 parent 배열의 각 인덱스의 값들을 표시해둔 것이다. 1행이 index, 2행이 parent이름을 나타낸다. (parent는 자신의 최종 부모를 뜻한다. 각 노들의 parent를 자기 자신으로 지정)

Test Case

내가 문제를 풀면서 만들어본 테스트 케이스이다.

8 7
1 2
3 4
5 6
7 8
2 3
6 7
1 5
1 2 3 4 5 6 7 8

설명

test case의 7 8이 있는 줄까지 마무리를 했다면, group 상황은 아래와 같이 바뀐다.

예시 사진 2

그 다음 test case의 2 3이 있는 줄을 실행했을 때를 살펴보면, 아래와 같이 바뀌게 된다.

예시 사진 3

여기서, 밑의 group과 위의 표의 차이를 보는 것이 중요하다.

union 함수를 실행할 경우 두 노드의 최종 부모가 다르다면, 그러니까 parent 배열안의 value값이 다르다면, 두 최종 부모 중 한 노드를 다른 노드의 부모로 만들면 된다.

예시 사진 3을 보면, 2와 3의 union함수를 실행하면 2의 부모는 2, 3의 부모는 4이다. 코드 상에서 그냥 오른쪽 노드를 왼쪽 노드의 부모가 되도록 했으므로 4가 2의 노드의 부모가 된다. 그러므로 2의 부모값이 4로 바뀌게 되었다.

 

find 함수

노드들이 같은 그룹 내에 있는 것을 확인하는 방법은 그 노드의 최종 부모의 노드 값을 확인해보면 된다.

그렇다면 해당 노드의 부모 노드를 확인하는 find 함수의 시간 복잡도를 줄이는 것이 중요할 것이다.

(저는 저만의 코드로 새롭게 풀어내고자 했지만 결국에는 시간 초과로 풀어내지 못했습니다.....)

find함수의 포인트는 재귀함수를 통해 부모를 찾으러 갈 때! 찾은 부모의 값을 다시 저장한다는 것입니다.

 

test case에서 6 7이 있는 줄과 1 5번이 있는 줄의 실행 결과를 비교하면서 설명해보도록 하겠습니다.

6 7 실행 결과

예시 사진 4

1 5 실행 결과

예시 사진 5

6 7 다음 1 5를 실행하고 난 다음의 parent 배열의 변화를 살펴보도록 하겠습니다.

1의 최종 부모는 4가 나오고 5의 최종 부모는 8이 나옵니다.

1의 최종 부모를 찾는 과정에서 1의 parent값을 배열에 저장하게 되서 parent[1]=4가 됩니다.

5의 최종 부모를 찾는 과정에서 5의 parent값을 배열에 저장하게 되서 parent[5]=8이 됩니다.

두 최종 부모는 4와 8로 다른 값이고 오른쪽 부모가 왼쪽 부모의 부모가 되게 되므로 parent[4]=8이 됩니다.

 

find함수를 매번 돌릴 때마다 해당 노드의 최종 부모의 값을 리셋해주므로, 매 find함수의 실행 시간을 줄여주게 되는 것 같습니다. (재귀 함수의 반복이 줄어드므로)

 

 

해결

이번 문제 풀이는 정말 진을 뺐던 것 같습니다. 저만의 방식으로 풀어내려고 해봤지만, 잘 되지 않아 괴로웠던 문제였습니다ㅠ