백준 2617 구슬 찾기(python)

문제

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

2617번: 구슬 찾기

---

그래프 탐색으로 접근할 수 있는 문제입니다. DFS, BFS 어떤 것을 사용해도 무방하지만 저는 플로이드-워샬이 먼저 떠올랐기 때문에 이 방식으로 풀어보았습니다. 출력해야 되는 값이 무게가 절대로 중간값이 될 수 없는 구슬의 개수를 세는 문제였습니다. 풀이 과정은 다음과 같습니다.

• 먼저 입력으로 들어오는 구슬 번호대로 무게 순서를 지켜 관계를 2차원 리스트에 1로 표시해 줍니다.
• 다음으로 플로이드-와샬 알고리즘을 통해 모든 구슬들의 연결 관계를 확인해서 표시해 줍니다.
• 최종적으로 연결관계가 표시된 이차원 리스트에서 2중 반복문을 돌면서 무게가 크거나 작은 구슬들의 개수를 세어줍니다. 크거나 작은 구슬들의 개수가 N/2 보다 크다면 중간값이 될 수 없으므로 개수를 세어줍니다

이와는 별개로 DFS, BFS로 푸는 방식을 생각해 본다면, 무게의 작거나 큰 관계에 따라 2개의 리스트를 만들어 관계를 표현해주고, 기준 값보다 큰 개수를 세어주는 탐색, 작은 개수를 세어주는 탐색을 따로 실행해서 개수를 세주면 될 것 같습니다.

---

소스코드 

import sys
input = sys.stdin.readline
# 모든 구슬들의 관계를 살펴보고 조건 확인하기

N, M = map(int, input().split())

arr = [[0]*(N+1) for _ in range(N+1)]


for i in range(M):
    s, e = map(int, input().split())
    arr[s][e] = 1

# 플로이드 와샬
for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if arr[i][k] and arr[k][j]:
                arr[i][j] = 1


ans = 0

for i in range(1, N+1):
    left_cnt = 0
    right_cnt = 0
    for j in range(1, N+1):
        if i == j:
            continue
        elif arr[i][j] == 1: # 현재 구슬보다 가벼운 갯수 세기
            right_cnt += 1
        elif arr[j][i] == 1:# 현재 구슬 보다 무거운 갯수 세기
            left_cnt += 1
    if right_cnt > N//2 or left_cnt > N//2: # 가볍거나 무거운 개수가 중간값 보다 많으면 될 수가 없다
        ans += 1


print(ans)