10159. [Python]저울

1. 문제

 

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

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• 최단거리
• 플로이드 와샬

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline

N = int(input())

M = int(input())
# 초기 그래프 선언
graph = [[0] * (N+1) for _ in range(N+1)]
# 들어온 인풋에 대해서 누가 더 큰지 체크
for _ in range(M):
    S,E = map(int,input().split())
    graph[S][E] = 1
# i,i 인덱스 0으로 초기화
for i in range(N+1):
    graph[i][i] = 0
# 플로이드 와샬
for i in range(1,N+1):
    for j in range(1, N+1):
        for k in range(1, N+1):
            # j 에서 i 가 가는길이 있고 i 에서 k 로 가는 길이 있는 경우 j에서 k 로 가는 길이 존재 1 체크
            if graph[j][i] and graph[i][k]:
                graph[j][k] = 1
# 갈 수 없는길 체크
for i in range(1,N+1):
    cnt = 0
    for j in range(1,N+1):
        # i 랑 j 랑 같은 경우 무시
        if i == j:
            continue
        # i 에서 j 로 갈 수 없고 j 에서 i 로 올 수 없는 경우 cnt 증가
        if graph[i][j] == 0 and graph[j][i] == 0:
            cnt += 1
    print(cnt)

print(graph)

 

4. 문제를 풀고난 후 생각

 

• 플로이드 와샬이라는 개념에 대해서 다시 생각해볼 수 있던 문제였다.
• S 무게가 E 무게보다 큰지 작은지에 대해서 input 으로 처리를 한 후 플로이드 와샬을 통해서 S 에서 각각 노드별로 도달할 수 있는 노드를 모드 체크해서 1로 초기화 해준다.
• 개수를 체크하는 과정에서 S 에서 각 노드에 갈 수 있으면 반대로 다른 노드에서 S 에도 올 수 없는 경우 즉 서로의 무게를 모르는 경우 cnt 를 증가시키는 방식으로 문제의 요구 사항에 접근함

 

5. 문제를 푸는데 도움이 되는 지식

 

• 플로이드 와샬