[BOJ_11403] 경로 찾기

설명

---

다익스트라를 사용해서 직접 각 시작점에서 시작해서 가지는 모든 곳을 체크했습니다. 또한, 처음 시작하는 곳은 내가 이미 시작 할 때 방문 한 여부를 찾는것이 아닌 다른 지점에서 처음 시작 지점을 들어오는 것을 체크하는 것이라서 그에 대한 방문 처리를 해주었습니다.

 

코드

---

package shortest_path;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_11403 {
    static int[][] map;
    static int[][] ans;
    static boolean[] visited;
    static int N;
    public static void main(String[] args) throws Exception{
        input();
        ans = new int[N][N];
        for (int i = 0; i < N; i++) {
            visited = new boolean[N];
            dijkstra(i);
            check(i);
        }
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static void check(int idx) {
        for (int i = 0; i < N; i++){
            if(visited[i]){
                ans[idx][i] = 1;
            }
        }
    }

    private static void dijkstra(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(start);
        int cnt = 0;
        boolean first = false;
        while (!q.isEmpty()){
            int now = q.poll();
            if(visited[now]){
                continue;
            }
            cnt++;
            visited[now] = true;
            for (int next = 0; next < map[now].length; next++){
                if(next == start && visited[start] && map[now][next] == 1){
                    first = true;
                }
                if(!visited[next] && map[now][next] == 1){
                    q.offer(next);
                }
            }
        }
        if(!first){
            visited[start] = false;
        }
    }

    private static void input() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        N = Integer.parseInt(tk.nextToken());

        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            tk = new StringTokenizer(in.readLine()," ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tk.nextToken());
            }
        }
    }
}

11403번: 경로 찾기