Q. 11403 자바 : 경로 찾기

Q. 11403 자바 : 경로 찾기

 

문제 : boj.kr/11403

실버 1 난이도의 문제이다.

 

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서,

i에서 j로 가는 경로 존재 여부를 구하라는 내용이다.

 

그래프 탐색 강의를 듣고 예제 문제를 푸는 도중이었는데 

이 문제는 List를 그래프 탐색이라고 되어 있어서 List를 사용해서 풀었지만,

만약 이를 몰랐다면 입력이 격자형 그래프로 주어져서 격자형 그래프로 풀었을 것 같다.

문제를 이해하는데 시간이 좀 걸렸다..

 

입력이 아래와 같이 주어졌을 때

3
0 1 0
0 0 1
1 0 0

출력이 아래와 같다.

1 1 1
1 1 1
1 1 1

즉 정점이 0, 1, 2가 있다면 입력을 간선으로 바꾸면

0 -> 1, 1 -> 2, 2 -> 0 세개의 간선이 있다고 생각하면 된다.

그래서 출력을 보면 모든 정점 0 1 2가 방문 가능하고 출발한 정점으로 돌아올 수도 있다는 내용이다.

---

문제는 BFS를 이용해서 풀었다.

정점마다 존재하는 방향그래프를 입력받았다면, 

모든 정점마다 BFS 탐색이 필요하다고 생각했다.(출발한 정점에서 다시 출발한 곳으로 돌아오는 경우를 고려해야 하므로)

그래서 모든 정점에 정점마다 존재하는 간선에 대해 BFS 탐색을 해서 풀었다.

 

위 문제의 경우 시간복잡도는 정점 N의 수가 최대 100개이므로1. 모든 정점에 대해 확인 - O(N)2. 간선이 존재할 경우 BFS 탐색 - O(N + E) 정점 + 간선의 수정점마다 확인해줘야 하므로 두개를 곱하면 약 O(N^2 + N*E)이고,N은 최대 100, 간선 E는 최대 4950(99 + 98 + 97 + ... + 3 + 2 + 1)이므로

계산 횟수는 약 10000 + 495000 = 505000번 정도 나오므로

시간초과는 걱정하지 않아도 된다.

또한 자료형 역시 int 범위 내에서 모두 해결할 수 있다.

 

풀고나서 강의자료에 있는 풀이를 봐보니 시간을 좀 더 줄일 수 있었고,

실제로도 꽤 많은 시간 차이가 나서 내 풀이와 강의자료를 참고한 풀이 두 방식의 풀이를 작성했다.

---

내가 푼 풀이는 아래와 같다.

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


public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N;
    static List<Integer>[] list;

    static int[][] res;


    static void input() {

        N = scan.nextInt();
        list = new List[N];
        res = new int[N][N];

        for (int i = 0; i < N; i++) list[i] = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int e = scan.nextInt();
                if (e == 1) {
                    list[i].add(j);
                    res[i][j] = 1;
                }
            }
        }
    }

    static void bfs(int s, int e) {

        Queue<Integer> que = new LinkedList<>();
        boolean[] visit = new boolean[N];
        visit[e] = true;

        que.add(e);

        while (!que.isEmpty()) {
            int v = que.poll();
            for (int i: list[v]) {
                if (!visit[i]) {
                    que.add(i);
                    res[s][i] = 1;
                    visit[i] = true;
                }
            }
        }
    }

    static void pro() {
        for (int i = 0; i < N; i++) {
            for (int j: list[i]) {
                bfs(i, j);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(res[i][j]).append(' ');
            }
            sb.append('\n');
        }

        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
   		 // BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

 

강의자료를 참고해서 다시 풀어봤다.

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


public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N;
    static List<Integer>[] list;

    static boolean[][] res;


    static void input() {

        N = scan.nextInt();
        list = new List[N];
        res = new boolean[N][N];

        for (int i = 0; i < N; i++) list[i] = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int e = scan.nextInt();
                if (e == 1) {
                    list[i].add(j);
                    res[i][j] = true;
                }
            }
        }
    }

    static void bfs(int start) {

        Queue<Integer> que = new LinkedList<>();
        boolean[] visit = new boolean[N];

        que.add(start);

        while (!que.isEmpty()) {
            int s = que.poll();
            for (int e: list[s]) {
                if (!visit[e]) {
                    que.add(e);
                    res[start][e] = true;
                    visit[e] = true;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            sb.append(res[start][i] ? 1 : 0).append(' ');
        }
        sb.append('\n');
    }

    static void pro() {

        for (int i = 0; i < N; i++)  bfs(i);

        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}