boj 2617 구슬찾기 (플루이드-와샬)

처음 문제를 봤을 때 되게 간단한 그래프 문제구나!하면서 무거운 것과 가벼운 것을 2차원 리스트를 만들어 값을 입력받아 넣고 heavy에 연결된 값들을 dfs로 가벼운 것에 빈 리스트가 나올때 까지 들어간다면 모든 값들을 확인할 수 있다고 생각했다. 반대로도 마찬가지.

풀고나서 찾아보니 플루이드 와샬 문제였다.. 플루이드 와샬을 찾아보고 풀어보았다.. 플루이드 와샬을 알았다면 더 일찍 풀었을텐데!

그래도 이 방법을 알게돼서 햅삐~~~

dfs버전

import sys
sys.setrecursionlimit(10**6)

def dfs(start, graph, visited):
    stack = [start]
    count = 0
    while stack:
        current = stack.pop()
        for nxt in graph[current]:
            if not visited[nxt]:
                visited[nxt] = True
                stack.append(nxt)
                count += 1
    return count

n, m = map(int, input().split())
mid = (n // 2) + 1
light = [[] for _ in range(n+1)]
heavy = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    light[b].append(a)
    heavy[a].append(b)

result = 0

for i in range(1, n+1):
    if dfs(i, light, [False] * (n+1)) >= mid or dfs(i, heavy, [False] * (n+1)) >= mid:
        result += 1

print(result)

플루이드 와샬 버전

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
INF = int(1e9)
heavy = [[INF] * n for _ in range(n)]
light = [[INF] * n for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    heavy[b - 1][a - 1] = 1  # b가 a보다 무겁다
    light[a - 1][b - 1] = 1  # a가 b보다 가볍다

for k in range(n):
    for i in range(n):
        for j in range(n):
            heavy[i][j] = min(heavy[i][j], heavy[i][k] + heavy[k][j])
            light[i][j] = min(light[i][j], light[i][k] + light[k][j])

cnt = 0
for i in range(n):
    heavy_cnt = len([1 for j in range(n) if heavy[i][j] != INF])
    light_cnt = len([1 for j in range(n) if light[i][j] != INF])
    if heavy_cnt > n // 2 or light_cnt > n // 2:
        cnt += 1

print(cnt)