[백준 2024/09/20] 2617번 구슬 찾기

1. 문제

https://www.acmicpc.net/problem/2617

 

2. 접근 방법

특정 구슬보다 작은지 큰지를 구분하여 저장해 주었다.

예시를 defaultdict로 저장해 주었는데, 아래와 같이 저장하게 된다.

heavier[1] = [2, 5]
heavier[2] = [4]
heavier[3] = [4]

lighter[2] = [1]
lighter[4] = [3, 2]
lighter[5] = [1]

 

heavier[1] 보다 작은 것은, 2, 5 그리고 2보다 작은 4이다.

따라서, 이를 dfs로 순환하여 표현되지 않은 값들도 표현이 되도록 하였다.

 

구슬의 개수//2 보다 더 큰 값을 해당 노드가 저장하고 있다면, 그 노드는 중간에 있을 수 없다.

해당 구슬보다 작은 구슬이 mid개 있는 것 or 해당 구슬보다 큰 구슬이 mid개 있는 것이기 때문이다.

 

3. 코드

from collections import defaultdict


class Pearl:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.heavier = defaultdict(set)
        self.lighter = defaultdict(set)
        self.visited = [False] * (n + 1)

    def weight_pearl(self):
        for _ in range(self.m):
            h, l = map(int, input().split())
            self.heavier[l].add(h)
            self.lighter[h].add(l)

    def dfs(self, i, compare):
        stack = [i]
        visited = set()

        while stack:
            n = stack.pop()
            if n in visited:
                continue
            visited.add(n)
            for neighbor in compare[n]:
                if neighbor not in visited:
                    stack.append(neighbor)
                    compare[i].add(neighbor)

    def compress(self):
        keys = list(self.heavier.keys())
        for k in keys:
            self.dfs(k, self.heavier)

        self.visited = [False] * (n+1)

        keys = list(self.lighter.keys())
        for k in keys:
            self.dfs(k, self.lighter)

    def not_in_middle(self):
        exceed = self.n // 2
        cnt = 0
        for h in self.heavier:
            if len(self.heavier[h]) > exceed:
                cnt += 1

        for h in self.lighter:
            if len(self.lighter[h]) > exceed:
                cnt += 1

        return cnt


if __name__ == "__main__":
    n, m = map(int, input().split())
    pearl = Pearl(n, m)
    pearl.weight_pearl()
    pearl.compress()
    print(pearl.not_in_middle())