백준 10159(저울) - Python(파이썬),Java(자바) - 플로이드 워셜

10159번: 저울

예제 풀이

그림으로 표현하면 이런식으로 표현 된다.

그럼 연결된 노드들을 표로 표현하면 이렇게 된다

이제 차례대로 1번노드부터 6번노드까지 경로노드로 거쳐서 간다고 할 때 표를 작성하면

1️⃣ 1번 노드가 경로노드인 경우 -> 없음

2️⃣ 2번 노드가 경로노드인 경우 -> 1번 노드에서 3번 노드로 가는 경우 D13 = (D12 + D23) =2로 변경

 

3️⃣ 3번 노드가 경로노드인 경우

-> 1번 노드에서 4번 노드로 가는 경우 D14 = (D13 + D34) =3로 변경

-> 2번 노드에서 4번 노드로 가는 경우 D24 = (D23 + D34) = 2로 변경

 

4️⃣ 4번 노드가 경로노드인 경우 -> 없음

5️⃣ 5번 노드가 경로 노드인 경우 -> 6번 노드에서 4번 노드로 가는 경우 D64 = (D65+D54) = 2로 변경

6️⃣ 6번 노드가 경로 노드인 경우 -> 없음

 

결론 : graph[i][j] 와 graph[j][i]의 값이 모두 빈칸인 경우 세기

 

 

문제 풀이

① (n+1) * (n+1) 테이블에 값이 INF인 graph 선언
② graph [i][i]인 값을 모두 0으로 만들기
③ m개의 a>b인 값을 graph[a][b]에 1로 넣기
④ for루프로 경로노드가 1부터 n까지인 경우 -> (시작노드->경로노드->도착노드의 값)과 (시작노드-> 도착노드의 값)을 비교하여 작은 값을 테이블에 대입
⑤ graph[i][j], graph[j][i]의 값이 모두 INF인 경우 값을 비교할 수 없다고 판단하여 출력하기

💻Python(파이썬)

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
INF = int(1e9)
graph = [[INF]*(n+1) for _ in range(n+1)]

#graph[i][i]인 경우 =0으로 넣기
for i in range(n+1):
    graph[i][i]=0
#m개의 a>b인 값을 받아 graph[a][b]=1로 넣기
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    graph[a][b]=1

#경로노드
for i in range(1,n+1):
    #시작 노드
    for a in range(1,n+1):
        #도착노드
        for b in range(1,n+1):
            graph[a][b]=min(graph[a][b],graph[a][i]+graph[i][b])


#둘다 INF가 아닌 경우 찾아 cnt +1하고 출력하기
for i in range(1,n+1):
    cnt =0
    for j in range(1,n+1):
        if graph[i][j]==INF and graph[j][i]==INF:
            cnt+=1
    print(cnt)

💻Java(자바)

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[][] graph = new int[N+1][N+1];
        int INF = (int)1e9;
        for(int i=0;i<N+1;i++){
            Arrays.fill(graph[i],INF);
        }
        //M개의 a>b인 수를
        for(int i=0;i<M;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            graph[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]=1;
        }
        for(int i=1;i<N+1;i++){
            for(int a=1;a<N+1;a++){
                for(int b=1;b<N+1;b++){
                    graph[a][b] = Math.min(graph[a][b],graph[a][i]+graph[i][b]);
                }
            }
        }
        for(int a=1;a<N+1;a++){
            int cnt=0;
            for(int b=1;b<N+1;b++){
                if(graph[a][b]==INF && graph[b][a]==INF){
                    cnt+=1;
                }
            }
            System.out.println(cnt-1);
        }

    }
}