BOJ 10159번: 저울

www.acmicpc.net/problem/10159

10159번: 저울

아이디어:

주어진 입력에서 앞의 물건이 뒤의 물건보다 무거운 즉 1 2면 1>2인 관계를 가지므로 그냥 1->2로 연결된 방향 그래프라고 생각을 하고 풀었다. 그리고 플로이드 와샬 알고리즘을 이용해 탐색하고 연결되지 않은 경우를 카운트해서 출력했더니... 틀렸다^^

다시 생각해보니 당연한 것이었다. 일단, 방향 그래프로 설정해서 푸니 1->2는 알 수 있지만 2->1은 알 수 없는 걸로 나오는데 반대의 경우도 알 수 있다. 하지만, 그렇다고 양방향으로 설정을 하면 모두 연결되어 버리므로 그렇게 할 순 없다. 그래서 고민한 결과.. 방향 그래프로 설정해서 플로이드 와샬 알고리즘으로 탐색한 후, 만약 [i][j]가 연결되어 있으면 [j][i]도 연결되어 있다고 처리하면 된다는 걸 알았다! 근데 다 탐색하자니 시간초과가 날 것 같았고(근데 지금 다시보니까 N이 작아서 그냥 N^2만큼 다시 탐색해도 될 것 같긴 하다.) 그래서 따로 배열ans을 만들어서 [i][j]의 값이 갱신될 때 ans[i][j]=ans[j][i]=1이 되도록 하였다.

그런데 또 이렇게만 하니까 어처구니 없는 결과가 나와서 왜 그런가 봤더니, 플로이드 와샬 안에서만 업데이트 했으니 처음부터 바로 연결되어 있는 경우는 카운트가 안된다는 걸 발견했다. 그래서 처음에 값을 입력받을때도 ans[a][b]=ans[b][a]=1 이 되도록 했고 마지막에 ans를 돌면서 0인 경우를 카운트해서 출력했더니 맞았다.

 

#10159번 저울
import sys

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
INF = 10**9
dp = [[INF]*(N+1) for _ in range(N+1)]
ans = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a,  b = map(int, sys.stdin.readline().split())
    dp[a][b]=1
    ans[a][b]=1
    ans[b][a]=1

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if (dp[i][j]>dp[i][k]+dp[k][j]):
                dp[i][j] = dp[i][k]+dp[k][j]
                ans[i][j]=1
                ans[j][i]=1

for i in range(1,N+1):
    cnt = 0
    for j in range(1,N+1):
        if (i==j): continue
        if (ans[i][j]==0):
            cnt+=1
    print(cnt)