[Do It! 코딩테스트 자바편(김종관)] 문제 062(백준 11403번)

느낀점

• 플로이드-워셜 알고리즘에서 조금만 변형하면 되는건데, 바로 안 떠오른 문제
• 아이디어만 떠올리면 구현은 전혀 어렵지 않은 간단한 문제

문제

경로 찾기 (백준: 11403번)

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int matrix[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        matrix = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                int tmp = Integer.parseInt(st.nextToken());
                matrix[i][j] = tmp;
            }
        }

        for (int k = 1; k <= n; k++) {
            for (int s = 1; s <= n; s++) {
                for (int e = 1; e <= n; e++) {
                    if (matrix[s][k] == 1 && matrix[k][e] == 1)
                        matrix[s][e] = 1;
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int r = 1; r <= n; r++) {
            for (int c = 1; c <= n; c++) {
                bw.write(matrix[r][c] + " ");
            }
            bw.write("\n");
        }
        bw.close();
    }
}