자바(백준) 11403 경로 찾기

오답 노트 & 새로 알게 된 점

해당 문제를 풀면서 중요한 부분을 배웠다.

알고리즘은 절대로 정형화해서 풀지 말자. 

원래 일반적으로 dfs를 풀 때, dfs함수를 호출하고 방문 체크를 해주는데 해당 문제는 그러면 안됐다.

 

예제2)

1. 1 -> 4 -> 5 -> 1 처럼 cycle이 있는 것은 1 4 5에 모두 1이 있어야하지만,

2. 2 -> 7 -> 3 처럼 cycle이 없는 것은 7 3에만 1이 있어야한다.

 

그래서 위와 같이 일반적으로 dfs를 푸는 것처럼 바로 방문체크를 하게 된다면,

1번은 맞게 되지만, 2번에서 2도 1이 된다. 그래서 틀리게 된다.

해결 방법은 dfs를 재귀 호출할 때 방문 체크를 해주면 된다.

 

두 가지 방법을 사용하여 문제를 풀었는데, 위 얘기는 1번 코드와 관련있다.

2번 코드는 dfs인자를 2개 사용하여 풀면 쉽게 풀 수 있다.

 

---

 

코드1 - dfs의 parameter가 1개

 

public class Main {
    static int atoi(String str){
        return Integer.parseInt(str);
    }
    static int rel[][];
    static int arr[][];
    static boolean visit[];
    static boolean recur[];
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
        rel = new int[N+1][N+1];
        arr = new int[N+1][N+1];
 
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = atoi(st.nextToken());
            }
        }
 
        for (int i = 1; i <= N; i++) {
            //start시점마다 visit배열을 초기화
            visit = new boolean[N + 1];
            recur = new boolean[N + 1];
            dfs(i);
            for (int j = 1; j <= N; j++) {
                if(visit[j]){
                    rel[i][j] = 1;
                }
            }
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                System.out.print(rel[i][j] + " ");
            }
            System.out.println();
        }
    }
    static void dfs(int start){
        for (int i = 1; i <= N; i++) {
            if(visit[i]) continue;
            if(arr[start][i] == 0) continue;
            visit[i] = true; //////////////////////이 부분
            dfs(i);
        }
    }
}

 

 

---

 

코드2 - dfs의 parameter가 2개

 

public class BOJ11403 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int rel[][];
    static int arr[][];
    static boolean visit[];
    static int N;
 
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
        rel = new int[N + 1][N + 1];
        arr = new int[N + 1][N + 1];
 
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = atoi(st.nextToken());
            }
        }
 
        for (int i = 1; i <= N; i++) {
            //start시점마다 visit배열을 초기화
            visit = new boolean[N + 1];
            for (int j = 1; j <= N; j++) {
                if(arr[i][j] == 1 && !visit[j])
                    dfs(i, j);
            }
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                System.out.print(rel[i][j] + " ");
            }
            System.out.println();
        }
    }
 
    static void dfs(int x, int y) {
        visit[y] = true;
        rel[x][y] = 1;
 
        for (int i = 1; i <= N; i++) {
            if(visit[i]) continue;
            if(arr[y][i] == 0) continue;
 
            dfs(x, i);
        }
    }
}