백준 13314번: 플로이드에 오타가? (Java)

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

13314번: 플로이드에 오타가?

문제

평소에 코딩 실력이 부족하다고 느끼고 있는 지구이는 익명게시판에서 “백스페이스 키를 쓰지 않고 코딩하기를 추천합니다” 라는 글을 읽게 되었다. 글의 최하단에는 매우 작은 글씨로 “효과는 보장할 수 없습니다” 같은 내용의 글이 5줄에 걸쳐 알아보기 힘들게 쓰여 있었지만, 지구이는 그래도 한 번은 시도해 볼 만한 방법이라고 생각했고, 직접 해보기로 했다.

지구이가 처음으로 도전한 문제는 다음과 같다.

“정점이 N (1 ≤ N ≤ 100)개 있고, 그래프의 인접행렬이 N*N으로 주어진다. 이때 모든 쌍의 최단거리를 구하시오.”

지구이는 플로이드로 이 문제를 풀려고 했으나, 아쉽게도 첫 번째 줄에서 오타가 나고 말았다. 하지만 지구이는 짧은 시간동안 자기합리화와 함께, “이 정도 실수라면 데이터가 내 코드를 빗겨나가지 않을까?”라는 굳은 믿음으로 계속 코딩을 했다. 하지만 결국 그 실수 때문에 맞을 수 없었고, 지구이는 코드를 밀 수밖에 없었다.

문제를 푼 후, 지구이는 자신의 첫 번째 코드가 얼마나 잘못됐는지 확인해 보려고 한다. 이것은, 첫 번째 코드와 두 번째 코드에서 구한 최단거리가 서로 다른 (i, j) 쌍의 개수가 9700개 이상인 데이터를 찾는 것이다. 하지만, 역시나 지구이는 데이터를 찾을 수 없었다.

지구이의 첫 번째 코드가 얼마나 망한 코드인지 알려주자!

지구이의 코드는 여기에 있다.

입력

입력은 없다.

출력

첫 번째 줄에 정점 개수 N(1 ≤ N ≤ 100)을 출력한다.

두 번째 줄부터 N개의 줄에 그래프의 인접행렬 D를 출력한다.

D(i, i) = 0, 0 ≤ D(i, j) ≤ 10000이어야 한다.

출력 예시는 답이 아님에 주의하라.

 

---

 

풀이

오타 찾는게 제일 힘든 문제였다... 자세히 보면 첫 번째 플로이드에서 첫 번째 for문에서 등호를 빠뜨렸다. 이 경우, 최단 경로가 점 N을 지나면서 갱신되는 경우 최단 경로를 구할 수 없을 것이다.

N=100일 때, 모든 점(!=N)에서 N으로 오고갈 때의 거리를 1, 나머지 점끼리의 이동의 거리를 적당히 1000 정도로 잡으면, 총 9702개의 점에서 값이 달라진다.

 

배운 점

'구성적' 태그가 적혀있는 문제를 처음으로 풀어봤다. 문제 풀이의 틀이 없어서 확실히 막막한 감이 있다. 문제 자체는 쉬운 편

 

코드

풀이

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        sb.append(100+"\n");
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (i == j) sb.append(0+" ");
                else if (j == 99 || i == 99) sb.append(1+" ");
                else sb.append(1000+" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}
 

 

테스트 가능한 코드: Java용

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int[][] d;
    static int[][] e;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        d = new int[N][N];
        e = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                d[i][j] = Integer.parseInt(st.nextToken());
                e[i][j] = d[i][j];
            }
        }
        
        wrongFloyd(d);
        floyd(e);
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (d[i][j] != e[i][j]) cnt++;
            }
        }
        System.out.println(cnt);
    }
    
    public static void wrongFloyd(int[][] dist) {
        for (int k = 0; k < N-1; k++) {
            for (int i = 0; i <= N-1; i++) {
                for (int j = 0; j <= N-1; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    public static void floyd(int[][] dist) {
        for (int k = 0; k <= N-1; k++) {
            for (int i = 0; i <= N-1; i++) {
                for (int j = 0; j <= N-1; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}