[PYTHON] 백준 2617 - 구슬 찾기

성능 요약

메모리: 115272 KB, 시간: 124 ms

분류

깊이 우선 탐색, 플로이드–워셜, 그래프 이론, 그래프 탐색

문제 설명

모양은 같으나, 무게가 모두 다른 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 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

출력

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

---

아이디어, 문제풀이

• 중간이 될수 없는 구슬이기 때문에, 큰것, 작은것을 모두 포함한다.
• 동일한 배열을 다른 두개의 배열로 저장한다.

  1. 인접리스트에 a를 기준으로 b를 저장하는것은 a가 b보다 무겁다는 의미.

  2. 인접리스트에 b를 기준으로 a를 저장하는것은 b보다 a가 무겁다는 의미.

     두가지 배열을 같은 dfs 함수에 적용하면, 각각 최소가되서 제외되는것, 최대가 되서 제외되는것을 각각 찾아낼 수 있다.

• (N+1)/2 는 그 구슬이 제외되기 위한 조건이다. 5개일때, 3개보다 작거나 커야만 제외가 가능하다.

---

TROUBLE SHOOTING

• 플로이드 워셜 알고리즘을 적용한 문제로 나와있다. 플로이드 워셜로 풀이가 가능하다는건? dfs로 풀이가 가능하다는것! 이 문제를 풀이할때, 사실 트러블 슈팅은 없었다. 트러블이 안난체로, 거의 한큐에 문제풀이에 성공했다. 알고리즘 자체는 간단했던것 같다.

• 난 dfs에 check라는 리스트를 만들어서, dfs에서 탐색하는 모든 노드들을 저장해줬는데, 이렇게하면 start에 입력된 값보다 무겁거나 가벼운것들을 모두 모아놓을 수있다. 그뒤 check 리스트를 리턴해주면 끝!

  def dfs(graph, start, visit):
  
      stack = []
      stack.append((start))
      check = []
  
      while stack:
          value= stack.pop()
  
          if visit[value] == 0:
              visit[value] = 1
  
          for node in graph[value]:
              if visit[node] == 0:
                  visit[node] = 1
                  check.append(node)
                  stack.append(node)
  		return check

  나온 리턴값을 가공해 문제에 알맞은 출력값으로 변환해 주면된다. 나같은 경우엔 최대, 최소를 모든 정점에 대해서 찾아준뒤, 그 배열의 개수가 (n+1)/2 를 넘을때 카운트 해주는 방식으로 풀었다.
  

---

코드

#https://www.acmicpc.net/problem/2617
#구슬 찾기
#2617

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

max_graph = [[] for _ in range(n+1)]
min_graph = [[] for _ in range(n+1)]
for _ in range(m):
    a , b = map(int, input().split())
    max_graph[a].append(b)
    min_graph[b].append(a)

# print(max_graph)
# print(min_graph)

# visit = [0] * (n+1)
count = [0] * (n+1)

def dfs(graph, start, visit):

    stack = []
    stack.append((start))
    check = []

    while stack:
        value= stack.pop()

        if visit[value] == 0:
            visit[value] = 1

        for node in graph[value]:
            if visit[node] == 0:
                visit[node] = 1
                check.append(node)
                stack.append(node)

        # print(check)
        # print(stack)

    return check

min_count = 0
max_count = 0

for i in range(n):

    visit = [0] * (n+1)
    result = dfs(min_graph, i+1, visit)
    # print(len(result))

    if len(result) >= (n+1)/2:
        min_count +=1

# print(min_count)

for i in range(n):

    visit = [0] * (n+1)
    result = dfs(max_graph, i+1, visit)
    # print(len(result))

    if len(result) >= (n+1)/2:
        max_count +=1

# print(max_count)

answer = min_count + max_count

print(answer)