[백준] [파이썬] [Graph] [BFS] [DFS] 2617번: 구슬 찾기

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

문제 보러 가기

문제

모양은 같으나, 무게가 모두 다른 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

5 4
2 1
4 3
5 1
4 2

예제 출력 1

2

---

그림을 그려봐야한다.

한 구슬이 뭐보다 크고 뭐보다 크고 이렇게 언급이 많으면 일단 중간값은 될 수 없을 것이다.

또 한 구슬이 뭐보다 작고 뭐보다 작고 이렇게 언급이 많으면 중간값이 될 수 없다.

따라서 '큰 구슬 그룹'관점에서 봤을때 노드를 타고 타고 내려갔을때 카운트되는 수가 중간값(N+1/2)보다 크면 중간값이 될 수 없을 것이고 '작은 구슬 그룹'관점에서 봤을때 노드를 타고 타고 내려갔을때 카운트되는 수가 중간값(N+1/2)보다 크면 중간값이 될 수 없을 것이다.

따라서 큰 구슬 관점의 리스트와 작은 구슬 관점의 리스트를 각각 만들고 각 구슬별로 몇개의 노드가 연결되는지 카운트하면서 중간값보다 큰지 작은지를 확인하면 될것이다. 이때 잊지 말아야 할 것은 노드를 방문하고 다시 올라가서 방문한 노드를 중복 방문하는 일이 없어야 한다.

---

BFS로 푼 코드

import sys 
from collections import deque 

sys.stdin=open('input.txt','r')

def BFS(x,graph):
    cnt=0
    visited[x]=True 
    Q=deque()
    Q.append(x)
    while Q:
        e=Q.popleft()
        for i in graph[e]:
            if not visited[i]:
                cnt+=1
                visited[i]=True 
                Q.append(i)
    return cnt

if __name__=="__main__":
    N,M=map(int, input().split())
    graph1=[[] for _ in range(N+1)]
    graph2=[[] for _ in range(N+1)]
    mid=(N+1)/2
    for _ in range(M):
        a,b=map(int, input().split())
        graph1[b].append(a)
        graph2[a].append(b)


    ans=0
    for i in range(1,N+1):
        cnt=0
        visited=[False]*(N+1)
        if BFS(i,graph1)>=mid:
            ans+=1
        cnt=0
        if BFS(i,graph2)>=mid:
            ans+=1

    print(ans)

---

DFS로 푼 코드

import sys 
from collections import deque 

sys.stdin=open('input.txt','r')

def DFS(x,graph):
    global cnt 
    for e in graph[x]:
        if not visited[e]:  # False면, 즉 첫 방문일때만
            visited[e]=True
            cnt+=1
            DFS(e,graph)

if __name__=="__main__":
    N,M=map(int, input().split())
    graph1=[[] for _ in range(N+1)]
    graph2=[[] for _ in range(N+1)]
    mid=(N+1)/2
    for _ in range(M):
        a,b=map(int, input().split())
        graph1[b].append(a)
        graph2[a].append(b)


    ans=0
    for i in range(1,N+1):
        cnt=0
        visited=[False]*(N+1)
        DFS(i,graph1)
        if cnt>=mid:
            ans+=1
        cnt=0
        DFS(i,graph2)
        if cnt>=mid:
            ans+=1

    print(ans)

---

 

플로이드 워샬로 풀기 

 

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)