[Java][자바][백준][11403번] 경로 찾기

문제

가중치 없는 방향 그래프 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으로 출력해야 한다.

 

생각

인접행렬의 형태로 형태가 주어졌다. dfs, bfs의 경우에는 인접행렬, 인접리스트로 주어진 것과 지도 형식으로 주어지는 게 있는데 두 부분 모두 공부하기를 추천한다. 왜냐, 내가 지도 형식만 공부했다가 이번 a형에서 탈탈 털렸기 때문이다.. 흑흑..

 

위 문제는 각 이어져있는 정점이 주어지고 i에서 j로 가는 경로가 있는지 판단하는 것이다. bfs나 dfs를 i에서 시작해서 j가 되면 종료를 하는 방식으로 문제를 풀면된다. 주석에서 설명을 적기로 하겠다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int n;
    static int[][] map;
    static boolean[] visited;
    //출력을 인접행렬 형식으로 보여줘야 하므로 새로운 배열을 만들어준다.
    static int[][] result;
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        map = new int[n][n];
        visited = new boolean[n];
        result = new int[n][n];
        
        for(int i=0; i<n; i++) {
            String[] str = br.readLine().split(" ");
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(str[j]);
            }
        }
        
        //매번 정해야 하므로 bfs를 한번 하고 나면 visited를 초기화 해준다.
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(!visited[i]) {
                    bfs(i,j);
                    Arrays.fill(visited, false);
                }
            }
        }
 
        show(result);
    }
    //bfs를 통하여 i에서 j로 가는 경로를 구하여 그 경로가 0보다 크면 result에 추가시켜준다.
    //이렇게 해야 i에서 i로 돌아오는 경우 바로 bfs가 종료되는 것을 막아줄 수 있다.
    static void bfs(int start, int end) {
        int[] count = new int[n];
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        
        loop : while(!q.isEmpty()) {
            int v = q.poll();
            
            if(v == end) {
                if(count[v] > 0) {
                    result[start][end] = 1;
                    break loop;
                }
            }
            
            for(int i=0; i<n; i++) {
                if(map[v][i] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                    count[i] = count[v] + 1;
                }
            }
        }
    }
    
    static void show(int[][] arr) {
        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[0].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}