[파이썬] BOJ - 2617 : 구슬 찾기

seanlion·2020년 12월 28일
0

알고리즘

목록 보기
7/11
post-thumbnail

링크

2617번: 구슬 찾기

문제

모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.

우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.

예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.

  1. 구슬 2번이 구슬 1번보다 무겁다.
  2. 구슬 4번이 구슬 3번보다 무겁다.
  3. 구슬 5번이 구슬 1번보다 무겁다.
  4. 구슬 4번이 구슬 2번보다 무겁다.

위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것이 2, 4, 5번 구슬이고, 4번 보다 가벼운 것이 1, 2, 3번이다. 따라서 답은 2개이다.

M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄은 구슬의 개수를 나타내는 정수 N(1 ≤ N ≤ 99)과 저울에 올려 본 쌍의 개수 M(1 ≤ M ≤ N(N-1)/2)이 주어진다.
그 다음 M 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

출력

첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.

풀이

  • 일단 특정 구슬 보다 무거운 구술 혹은 가벼운 구슬의 개수를 찾는 로직을 짜야 한다.

    • ** 처음에는 무거운 구슬이 무엇인지 가벼운 구술이 무엇인지 번호를 찾으려 했으나 우리가 답으로 찾는 건 갯수이므로 개수만 찾아도 된다고 판단.**
  • 그 후 특정 구슬의 개수가 중앙값 보다 같거나 큰지 확인한다.

    • 어떤 구슬이 그 구슬보다 무거운 구슬을 중앙값(ex: 3)만큼 가지고 있다면 그 구슬은 절대 중앙값이 될 수 없다.
    • 이미 구슬은 중앙값보다 최소 1칸 이상은 떨어져 있기 때문이다. (구슬의 개수가 5개이고, 중앙값이 3일 때를 떠올려보면 금방 이해가 된다.)
  • 그럼 더 무거운 혹은 가벼운 구슬의 개수는 어떻게 찾을 수 있을까?

    • 구슬들을 그래프 관계로 떠올려보고 DFS를 이용한다.
    • 딕셔너리를 활용해 키: 구슬번호 / 값: 그 구슬보다 더 작은 구슬번호 의 방향이 있는 인접그래프를 만들었다.

    • 그림을 보면 특정 구슬(1)보다 무거운 구슬(2)은 한개가 아니라 여러 개인 것을 알 수 있다.(2보다 3이 더 크면 1< 3이기 때문.)
    • 저 관계를 활용해 DFS를 타고 들어가면 1보다 큰 건, (2,4,5)라는 걸 알 수 있다.(재귀로 타고 내려갈 때마다 +1을 해준다.)
    • 방향이 있는 그래프이기 때문에 한번 재귀로 타고 내려가서 더 이상 갈 수 있는 지점이 없으면 멈추게 되어있다.
      • 단, 한번 들렀던 지점은 방문 체크를 해줘야 한다. 그렇지 않으면 계속 들릴 수 있기 때문에 시간이 많이 걸리게 돼 시간초과가 난다.
    • 따라서 반복문을 5번 돌려서 모든 지점을 출발 지점으로 만드는 탐색 방법을 써야한다.
    • 특정 구슬보다 무거운 구슬 개수가 나올 때마다 중앙값과 비교한다. 중앙값보다 같거나 크면 개수(answer)를 +1 해준다.
    • 특정 구슬보다 가벼운 구슬은 그래프를 반대로 뒤집으면 풀 수 있다.

코드

import sys
from collections import defaultdict
N,M = map(int,sys.stdin.readline().split())
tmp_lst = [list(map(int,sys.stdin.readline().split())) for _ in range(M)]
lighter_node_graph = defaultdict(list)
heavier_node_graph = defaultdict(list)
for i, j in tmp_lst:
        lighter_node_graph[i].append(j)
        lighter_node_graph[j]
        heavier_node_graph[j].append(i)
        heavier_node_graph[i]

median = (N+1)//2
def bfs(vertex,graph):
    global count
    visited_node[vertex] = 1 # 방문 체크 해줘야 함.
    for item in sorted(graph[vertex]):
        if visited_node[item] == 0:
            # visited_node[item] = count
            count += 1
            bfs(item,graph)
    return count
heavy_cnt=0
light_cnt=0
for marble in range(1,N+1):
    visited_node = [0 for _ in range(N + 1)]
    count = 0 # dfs 탐색하는 개수를 무거운거 찾을 때, 가벼운거 찾을 때 각각 초기화
    if bfs(marble,heavier_node_graph) >= median:
        heavy_cnt+=1
    count  = 0
    if bfs(marble,lighter_node_graph) >= median:
        light_cnt+=1

print(heavy_cnt+light_cnt)
profile
소프트웨어 엔지니어링을 연마하고자 합니다.

0개의 댓글