[Python] 백준 10159번: 저울

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

10159번: 저울

 

 > 접근

예제 입력 2의 대소관계를 그래프화하면 다음과 같다.(4-5는 생략하였다.)

위로 갈수록 무거워진다.

여기서 결과를 직접 그려가면서 계산을 해본 결과, 한 방향으로의 탐색을 위, 아래로 각각 시도하면 이를 통해 결과를 낼 수 있다는 점을 알게 되었다. 예를 들어 7에서 값을 구한다고 해보자. 이때, 4-5와 더불어 9까지 정보를 알 수 없기에 3이라는 결과가 나오게 된다.

이것은 앞서 말했듯이, 한 방향으로만 하는 탐색을 위, 아래로 2번 했을 때 9에 도달하지 않기 때문이다. 이런 결론은 그려가면서 계산을 하다보니 일반화가 되어서 얻을 수 있었다.

이에 따라 그래프를 2개 생성해주고 입력을 이에 맞게 처리해주어야 한다.

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

def dfs(node, direction):
  res = 1
  for nxt in graph[direction][node]:
    if(not is_visited[nxt]):   
      is_visited[nxt] = True
      res += dfs(nxt, direction)        

  return res
          
if __name__ == '__main__':
  N = int(input())
  M = int(input())

  graph = [{i:[] for i in range(1, N+1)} for _ in range(2)]
  for _ in range(M):
    h, l = map(int, input().split())
    # 방향을 달리하여 따로 저장한다.
    graph[0][h].append(l)    
    graph[1][l].append(h)  
    
  for i in range(1, N+1):
    # 각 방향별로 탐색을 따로 한다.
    is_visited = [False]*(N+1)
    res1 = dfs(i, 0)-1

    is_visited = [False]*(N+1)
    res2 = dfs(i, 1)-1

    print(N - (res1 + res2 + 1))