[백준] 경로 찾기

🔗 문제 보기 - [백준] 경로 찾기

📖 문제

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

✍ 입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

📄 출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayDeque;  
import java.util.Queue;  
import java.util.StringTokenizer;  
  
public class Main {  
    private static int n;  
    private static int[][] arr;  
    private static int[][] result;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        n = Integer.parseInt(br.readLine());  
        arr = new int[n][n];  
        result = new int[n][n];  
  
        for(int i = 0; i < n; i++) {  
            StringTokenizer st = new StringTokenizer(br.readLine());  
  
            for(int j = 0; j < n; j++) {  
                arr[i][j] = Integer.parseInt(st.nextToken());  
            }  
        }  
  
        for(int i = 0; i < n; i++) {  
            bfs(i);  
        }
        
        StringBuilder sb = new StringBuilder();  
        for(int i = 0; i < n; i++) {  
            for(int j = 0; j < n; j++) {  
                sb.append(result[i][j]).append(" ");  
            }  
            sb.append("\n");  
        }
        
        System.out.println(sb);
    }  
  
    public static void bfs(int start) {  
        Queue<Integer> queue = new ArrayDeque<>();  
        boolean[] visited = new boolean[n];  
  
        // start에서 직접 연결된 값들 result 값에 추가  
        for(int i = 0; i < n; i++) {  
            if(arr[start][i] == 1) {  
                queue.offer(i);  
                visited[i] = true;  
                result[start][i] = 1;  
            }  
        }  
  
        // 이후에 연결된 값들을 추가  
        while(!queue.isEmpty()) {  
            int val = queue.poll();  
  
            for(int i = 0; i < n; i++) {  
                if(arr[val][i] == 1 && !visited[i]) {  
                    queue.offer(i);  
                    visited[i] = true;  
                    result[start][i] = 1;  
                }  
            }  
        }  
  
    }  
  
}

🧩 코드풀이

해당 문제는 BFS를 이용해서 해결했습니다.

1. 1부터 차례대로 bfs 메소드를 통해 연결 되어있는 값들을 확인 합니다.
2. 첫번째 for문은 직접 연결된 값들을 체크하여 Queue에 값을 추가하고, 마지막 출력하기 위한 result 배열 요소 값들을 입력해줍니다.
3. 두번째 while문은 직접적으로 연결되어 있지 않은 값들을 queue에 담긴 값으로 이후 2차, 3차로 해당 위치까지 연결할 수 있는지 확인하고,
   연결 할 수 있다면 다시 queue에 추가하여 result 값을 1로 변경 해줍니다.
4. 위의 작업이 완료 된 후 result 배열에 담긴 내용들을 출력해줍니다.