[BOJ-10159] 저울

 

https://www.acmicpc.net/problem/10159

10159번: 저울

---

[ 풀이 ]

플로이드 와샬문제라고 한다.

그런데 굳이 플로이드 와샬(3중루프) 안써도 BFS로도 풀 수 있다. 

관련된 문제는 백준 "역사"문제와 "케빈베이컨 6가지 법칙"과 유사하다. (특히 역사문제를 강추한다)

 

[ 백준 1613 - 역사 ]

2020/02/27 - [알고리즘/BOJ] - [BOJ-1613] 역사

[BOJ-1613] 역사

[ 백준 - 케빈베이컨 6가지 법칙 ]

2020/02/26 - [알고리즘/BOJ] - [BOJ-1389] 케빈 베이컨의 6단계 법칙

[BOJ-1389] 케빈 베이컨의 6단계 법칙

 

 

그래도 풀이를 말하자면.

(1) H[무거운물건][가벼운물건] 2차원 리스트 배열을 만든다. 행번호>열번호 로 설정했다.

(2) M개의 미리 측정된 물건 쌍이 힌트이다. ([앞]> [뒤] : 앞의 무게가 뒤의 무게보다 더 무겁다)

그렇다면 H[앞][뒤]=1, H[뒤][앞]=-1 로 한다.

 

(3) 그리고 1번물건부터 BFS탐색한다.

(4) 물건을 탐색할때마다(BFS를 호출할때마다)

- visited방문리스트는 처음에 N개 노드(물건1번~N번)가 아직 방문되지 않은 상태로 초기화 한다.

 

- 탐색 물건번호(target: 1~N)을 큐에 먼저 넣는다.

 

- 큐에서 가장 먼저 들어온 원소를 pop하면서 방문 여부를 확인하고

 

- now가 target일때 H[target][i]=1 (무게관계: [target]>[i])이고

i번째 노드는 방문하지 않은 상태일 때

i를 큐에 넣는다.

여기서 i는 target이 아닌 다른물건번호(노드)라는 걸 주의하자.

 

문제 예시에서 [1]>[2], [2]>[3], [3]>[4] 일때 [1]>[4]관계를 갖는 것을 일반화 한다면

i는 target보다 가벼운 물건이라 가정한다면 (H[target][i]=1)

i보다 가벼운 물건인 j는 H[i][j]=1을 만족하므로

즉, [target]>[i]>[j]이므로 H[target][j]=1이어야한다.

 

 

(5) 각 노드별로 BFS탐색을 마치면

H[i=1~N][j=i가 아닌 다른수] 중 0의 개수를 출력하면 된다.

 

 

---

[코드 python]

import sys
from collections import deque
input=sys.stdin.readline
q=deque()

def bfs(target):
    global N,H
    visited=[False]*(N+1)

    q.append(target)
    while q:
        now=q.popleft()
        
        #now가 방문을 아직 안했는가?
        if not visited[now]:
            visited[now]=True
            #now는 target이 아니면서, H[target][now]가 0인가?
            if now!=target and H[target][now]==0:
                H[target][now]=1
                H[now][target]=-1
            
            #H[now][i]가 1인 노드를 넣는다.
            for i in range(1,N+1):
                #아직 i는 방문을 안한상태
                if (H[now][i]==1) and (not visited[i]): 
                    q.append(i)

N=int(input())
M=int(input())
H=[[0]*(N+1) for _ in range(N+1)]

#미리 측정된 물건 쌍 (앞물건>뒤물건)
for _ in range(M):
    heavy, light= map(int, input().strip().split())
    H[heavy][light]=1  #heavy>light
    H[light][heavy]=-1 #light<heavy

#1번부터 탐색
for target in range(1,N+1):
    bfs(target)


#탐색한 결과, 물건i(1~N)과 비교결과를 알 수 없는 물건의 개수를 출력
for i in range(1,N+1):
    #자기자신을 제외한 나머지
    cnt=0
    for j in range(1,N+1):
        if j!=i and H[i][j]==0:
            cnt+=1
    print(cnt)