[백준/Python]13314: 플로이드에 오타가?

문제

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

백준 문제집 - 0x1C강 - 플로이드 알고리즘

알고리즘: 그래프 이론, 해 구성하기, 최단 경로, 플로이드-워셜

---

풀이

처음 접하는 유형이라 굉장히 당황스러웠던 문제... 다른 풀이 + GPT를 참고해서 풀었다.

결론부터 말하자면 9700개 이상의 차이가 발생하는 "데이터"를 찾아야 하는 문제다.

일단 지구이씨의 코드는 파일로 첨부되어 있는데, 살펴보면 아래와 같다.

# 조건
if( i == j && D[i][j] != 0 || D[i][j] > 10000) WRONG;

# 첫번째 코드
for(int k = 1; k < N; k++){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            D[i][j] = min(D[i][k] + D[k][j], D[i][j]);
        }
    }
}

# 두번째 코드는 맞음

중간 거점 노드 k의 범위를 1 ~ N으로 설정해야 하는데, N-1까지만 확인한다.
즉 D[i][N] + D[N][j]의 경우를 아예 체크하지 않은것.

이 데이터를 기준으로 T/F가 나뉘려면 어떻게 해야할까?
👉 D[i][j]값이 실제로는 D[i][N] + D[N][i]여야 맞는 풀이라는것.

따라서 데이터가 틀리려면 D[i][N] + D[N][i]가 D[i][j]보다 작아야 한다.

반대로 맞는 데이터들은 두 가지 경우가 있겠다.

1. D[i][i]: 주대각선(0이어야 함)
2. D[i][N], D[N][i]: 거쳐가지 않고 직접 연결
   • 직접 연결된 간선이므로 플로이드 워셜이 어떻게 돌아가든 항상 같음.

위 조건에 부합하는 데이터의 갯수를 cnt라고 가정해보자.
틀린 데이터의 갯수가 9700개 이상이어야 한다고 했으니 N*N - cnt >= 9700 을 만족하면 될 것이다.

계산 돌려보면 N = 100일때 1번 조건의 갯수는 100, 2번 조건의 갯수는 99 * 2 = 198(D[i][99], D[99][j]와 같이 출발/도착노드가 99가 아닌경우)가 나온다.
100 * 100 = 10000, 100 + 189 = 298이니까 10000 - 298 = 9702개가 되므로 문제의 조건을 만족한다.

 

고로 틀린 데이터가 9700개 이상이 나오는 코드는,

1. 100 * 100 행렬
2. D[i][99] = D[99][j] = 1
3. i=i인 주대각선의 값은 0

이 되어야 한다.

이렇게 하면

• 첫번째 코드: D[i][j] = 100
• 두번째 코드: D[i][j] = D[i][99] + D[99][j] = 2

가 되므로 차이가 생기게 된다.

 

전체 코드

# 9700개 이상의 차이가 발생하는 "데이터"를 찾아야 하는 문제다.
"""
100x100 행렬로 만들 수 있는 쌍의 갯수 = 100 * 100 = 10,000개
제대로 계산한 값과 틀린 계산의 값이 같은 경우를 cnt라고 했을때,
- (i, i): 주대각선 행렬 100개
- (i, k), (k, j): 출발지 or 도착지가 k인경우 99 * 2 = 198개
10,000개 - 298개 = 9702개가 되므로 N = 100이고 (i, k), (k, j)가 (i, j)보다 작을 때 "데이터"를 만족함.
"""
# 메모리: 32412KB / 시간: 36ms
N = 100

arr = [[100] * N for _ in range(N)]

for i in range(100):
    arr[i][99] = arr[99][i] = 1
    arr[i][i] = 0

print(N)

for line in arr:
    print(*line)

 

플로이드 워셜을 이해했는가를 검증하는 느낌이다.