백준 2617 | 구슬 찾기 (DFS&BFS)

문제 출처 : https://www.acmicpc.net/problem/2617

문제 접근 방법

• 현재 구슬보다 큰 구슬의 개수가 (n+1)//2 개 이상이거나,
  작은 구슬의 개수가 (n+1)//2 개 이상이라면 그 구슬은 절대 중간값이 될 수 없다.

• 현재 구슬보다 큰 구슬에 대한 연결 그래프와 현재 구슬보다 작은 구슬에 대한 연결 그래프를 각각 만든다.

• 1번 구슬부터 n번째 구슬까지 각각 큰 연결 그래프 (1) 과 작은 연결 그래프 (2) 에 대해
  BFS를 이용하여 탐색하면서 현재 노드가 (n+1)//2 개 보다 많은 연결 관계 를 가지고 있다면
  정답 개수에 1을 더해준다. answer + 1

포인트 :

• 현재 노드보다 큰 구슬 연결 정보를 가지는 그래프 (1) 와 작은 구슬 연결 정보를 가지는 그래프(2) , 총 2개의 그래프를 생성 후 탐색해야 한다.
• 구슬의 중간 위치의 중간 (구슬의 개수 + 1) // 2 을 넘어가면 그 구슬은 절대 중간에 있을 수 없다.

BFS 코드

import sys
from collections import deque

# n : 구슬의 개수 ( 1 <= n <= 99 )
# m : 저울에 올려 본 쌍의 개수 ( 1 <= m <= n(n-1)/2 )
n, m = map(int, sys.stdin.readline().split())

# 구슬 연결 정보
more = [ [] for _ in range(n + 1)]
less = [ [] for _ in range(n + 1)]

# 정답 배열 및 중간 위치 기준 변수 선언
answer = 0
mid = (n + 1) // 2

# 구슬 연결 정보 입력받아서 2개의 그래프에 각각 저장
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    more[a].append(b)
    less[b].append(a)

# BFS 
def bfs(data, x):
    global count
    # 탐색 시작 노드 방문처리 후 큐에 삽입
    queue = deque([x])
    visited[x] = True

    while queue:
        v = queue.popleft()

        # 인접 노드 중에서 방문하지 않은 노드의 갯수를 세고 방문처리 후 큐에 삽입
        for i in data[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                count = count + 1

# 1번째 구슬부터 n번째 구슬까지 큰 연결 그래프(1)와 작은 연결 그래프를 탐색하여
# 연결된 노드의 개수를 구한다.
# 연결된 노드의 개수가 중간이 될 수 있는 기준 값인 (`(n+1)//2`) 보다 크다면
# 정답 변수(`answer`)에 +1 을 한다.
for i in range(1, n + 1):
    visited = [False] * (n + 1)
    
    count = 0
    bfs(more, i)
    if count >= mid:
        answer += 1

    count = 0
    bfs(less, i)
    if count >= mid:
        answer += 1

print(answer)

추가할 점

• DFS를 이용한 풀이와 플로이드-와샬을 이용한 코드도 작성해볼 것