[BOJ] 11403 경로 찾기 - JAVA

1. 문제

11403번: 경로 찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

---

2. 풀이

중간 노드가 될 지점을 가장 바깥 반복문으로 놓고, 시작지점, 끝지점을 i,j로 설정한다.

각 노드별 모든 거리를 살펴보면서 길이 이어져있는지(=경로가 있는지) 체크한다.

import java.io.*;
import java.util.*;

public class BOJ_11403_경로찾기 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int[][] matrix = new int[N][N];

      //입력
      StringTokenizer st;
      for (int i = 0; i < N; i++) {
         st = new StringTokenizer(in.readLine());
         for (int j = 0; j < N; j++) {
            matrix[i][j] = Integer.parseInt(st.nextToken());
         }
      }

      //탐색-플로이드워셜
      for (int k = 0; k < N; k++) {
         for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
               if(matrix[i][j]==1) continue;
               matrix[i][j] = matrix[i][k] & matrix[k][j];
            }
         }
      }

      //출력
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
            sb.append(matrix[i][j]).append(' ');
         }
         sb.append('\n');
      }

      System.out.print(sb);
   }
}

---

3. 결과

1년 전에 풀었던 문제를 다시 풀었더니 틀렸다. 역시 사람은 주기적으로 복습을 해야한다. ^_^..