DFS : 구슬 찾기(백준 2617번)

▶ 문제 : https://www.acmicpc.net/problem/2617

2617번: 구슬 찾기

##### 문제 #####
# 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. 
# N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 
# 이 구슬 중에서 무게가 전체의 중간인(무게 순서로 (N+1)/2번째) 구슬을 찾고자 한다.
# 우리에게 주어진 것은 양팔 저울이다. 
# 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 
# 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 
# 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.
# M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

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

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

 

▶ 접근 방법

DFS와 플루이드 워셜 알고리즘 두 가지를 이용해서 해결할 수 있었다.
- 추가 작성

 

▶ 풀이 코드

import sys

# N : 구슬의 개수, M : 비교해본 쌍의 개수
N, M = map(int, input().split())

# 구슬의 개수를 고려하여 구슬 정보를 담을 리스트를 만든다.
marble_info = [[0] * (N + 1) for _ in range(N + 1)]

# 구슬 크기 비교 결과를 담는다.
# 이때, row에 해당하는 구슬이 col에 있는 구슬보다 큰 경우를 1로 갱신한다.
for _ in range(M):
    row, col = map(int, input().split())
    marble_info[row][col] = 1

# 플로이드 워셜(Floyd_Warshall)
# row의 구슬과 col의 구슬 크기를 갱신하는데, 중간의 다른 구슬 정보들을 참고하여 갱신한다.
for route in range(1, N+1):
    for row in range(1, N+1):
        for col in range(1, N+1):
            if marble_info[row][route] and marble_info[route][col]:
                marble_info[row][col] = 1

result = 0
# 1번 구슬부터 쭉 살펴본다.
for i in range(1, N+1):
    left_count = 0
    right_count = 0
    for j in range(1, N+1):
        # 1번 구슬과 1번 구슬을 비교하는 것과 같이 같은 번호의 구슬 크기 비교는 넘어간다.
        if i == j:
            continue
        # (1, 2), (1, 3), (1, 4) 등의 값이 1이라면 1보다 2, 3, 4의 구슬이 무겁다는 의미이다.
        elif marble_info[i][j] == 1: 
            right_count += 1
        # (2, 1), (3, 1), (4, 1) 등의 값이 1이라면 1보다 2, 3, 4의 구슬이 가볍다는 의미이다.
        elif marble_info[j][i] == 1:
            left_count += 1
    # 가볍거나 무거운 개수가 중간값 보다 많으면 중간이 절대 될 수 없는 구슬이다.
    if right_count > N//2 or left_count > N//2: 
        result += 1

print(result)

 

▶ 관련 링크

2021.11.18 - [알고리즘] - DFS(Depth First Search, 깊이 우선 탐색)이란?

2021.11.20 - [알고리즘] - DFS :트리의 부모 찾기(백준 11725번)

2021.11.22 - [알고리즘] - DFS : 아침 산책(백준 21606번)

2021.11.20 - [알고리즘] - 이분 그래프(Bipartite Graph)란?

2021.11.22 - [알고리즘] - DFS : 이분 그래프(백준 : 1707번)

2021.11.22 - [알고리즘] - DFS : 연산자 끼워넣기(백준 14888번)

2021.11.22 - [알고리즘] - DFS : 빙산(백준 2573번)

2021.11.22 - [알고리즘] - 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)이란?