[백준] 키 순서 : 2458 Python

이 문제를 보면서 어떻게 풀어야 할지 고민하다가 알고리즘 분류를 보고 더 많이 헷갈렸다. 원래 문제를 풀 때 알고리즘 분류를 잘 보지 않으려고 하는데 이문제는 접근 자체가 너무 고민되어 보고 말았다....

알고리즘 분류에 플로이드-와샬이 적혀있었는데 나는 기본적으로 플로이드-와샬 알고리즘도 다익스트라처럼 가중치가 있는 그래프의 최단경로가 있을 때 사용할 거라 생각했었는데 이 문제는 가중치가 없어서 어떻게 플로이드 와샬로 풀지 와닿지 않았다. 그래도 일단 플로이드-와샬 알고리즘의 기본 틀은 알고 있었기 때문에 그 틀에 맞추어 풀어보았다.

나의 아이디어는 아래와같다.
1. 2차원 배열에는 현재 행을 기준으로 열이 행보다 작으면 True (1)을 준다.
2. 플로이드-와샬알고리즘을 활용하여 비교대상 값(s)이 비교대상 값(g) 보다 비교 가능하고, 비교했을 때 작다면 arr [g][s]는 True를 준다.
3. 위 과정을 반복한 후 자신보다 작은 값들의 개수와 큰 값들의 개수의 합이 N-1 값들을 찾는다.

이를 코드로 나타내면 이렇게 된다.

from sys import stdin
input = stdin.readline
N, M = map(int,input().split())


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

for _ in range(M):
    small, big = map(int,input().split())
    arr[big][small] = 1 


for k in range(1,N+1):
    for s in range(1,N+1):
        if k==s:
            continue
        for g in range(1,N+1):
            if g==s:
                continue
            cnt = 0
            if arr[k][s] and arr[g][k]: # k가 g와 비교된적이 있고 k가 더 작고, k와 s가 비교된적 있고 s가 더작다면
                cnt = 1  # s는 g보다 작다

            arr[g][s] = max(arr[g][s], cnt)


answer = 0
for i in range(1,N+1):
    scnt = sum(arr[i])
    rcnt = sum([1 if arr[j][i] else 0 for j in range(1,N+1)])
    if scnt + rcnt == N-1:
        answer += 1

print(answer)

자기 자신과 비교할 필요가 없기 때문에 k==s==g일 때 continue 함으로써 시간을 줄이려고 했지만 파이썬으로 통과하지는 못하였다.

백준에서는 플로이드-와샬알고리즘을 파이썬으로 하면 종종 시간 복잡도를 통과하지 못하는 경우가 있었기 때문에 다른 방법을 고민해보았다.

두 번째 방법은 dfs를 활용하여 푸는 것인데 백준 정답 코드의 simpleisbest님의 코드를 참고하였다.

아이디어는 아래와 같다.
1. 문제에서 주어지는 값들을 방향이 있는 그래프처럼 기록한다
2. N^2의 방문 기록할 2차원 배열을 만든다.
3. DFS를 활용하여 i점과 이어져있는(내 코드에서는 i보다 큰 값)들을 순회하며 방문 체크를 한다. 추가로 현재의 나보다 큰값이라면 그 값의 기준에서는 현재의 값은 그 값보다 작은 값이기 때문에 그 값의 입장에서도 방문체크를 한다.
4, DFS로 방문할 수 있는 모든 곳을 방문한 후 행 기준으로 모든 곳이 방문됐다면 정답을 기록한다.

이를 코드로 나타낸다면 아래와 같다.

from sys import stdin
input = stdin.readline

def f(now, idx):
    for pre in arr[idx]:
        if not v[now][pre]:
            v[now][pre] = 1
            v[pre][now] = 1
            f(now,pre)


N, M = map(int,input().split())
arr = [[] for _ in range(N+1)]

for _ in range(M):
    p, c = map(int,input().split())
    arr[p].append(c)

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

for i in range(1,N+1):
    v[i][i] = 1
    f(i,i)



answer = sum([1 if sum(v[i]) == N else 0 for i in range(1,N+1)])
print(answer)

 

DFS로 풀고 나면 생각보다 쉬운 문제인데 아이디어를 떠올리는게 어렵게 느껴졌었다.

아직 연습이 많이 필요한 것 같다