Java 백준 문제풀이 (53) 13023 _ ABCDE

 

이 문제에서 가장 어려웠던 것은 문제 이해다..

난 처음 이 문제를 읽고 모든 정점이 한 번에 이어지는 경우의 수를 찾는 것으로 이해해했으나, 그렇게 생각하면 도저히 문제에서 주어지는 예제와 출력이 맞지 않았다.

 

알고보니 말 그대로 정점 순서 관계 없이 ABCDE, 5개의 정점만 연속으로 이어지면 된다.

나만 바보인가..? 아무튼 풀어보자.

 

해당 문제를 읽고 전제조건을 먼저 주석으로 작성해보았다.

 

        // A,B,C,D,E가 한 번에 이어지는 경우를 찾아야 한다 -> DFS
        // 깊이가 5면 정답처리하면 될 듯
        // 사람 수(정점)은 일반 그래프와 달리 0부터 순서대로 주어지니 주의하자

 

사실 이번에는 별달리 전제조건을 적어놓을 것들은 없어 보였다.

그냥 DFS로 탐색하는 거고 사람 A,B,C,D,E는 일반 그래프 탐색 문제의 Vertex, 친구 관계는 Edge로 치환하면 끝 아닌가..? 라고 생각하고 야매로 수도코드를 작성했다.

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) {
        // A,B,C,D,E가 한 번에 이어지는 경우를 찾아야 한다 -> DFS
        // 깊이가 5면 정답 처리하면 될 듯
        // 사람 수(정점)은 일반 그래프와 달리 0부터 순서대로 주어지니 주의하자
        
        // 총 정점 수 N과 간선 M 입력받기.
        
        // 반복문
        // 인접 리스트를 위해 ArrayList N번 만큼 생성
        
        // 반복문
        // // N번 반복하며 간선 정보 입력받기
        // // 친구 관계는 무방향이므로 양쪽에 동일하게 넣어주자.
        
        // 방문 여부 체크를 위한 배열 생성
        // depth 체크용 변수 생성
        // 반복문
        // // 각 노드를 dfs로 탐색
        // // dfs (정점, 인접리스트, 방문여부체크, 깊이체크)
    }
    
    // dfs (정점, 인접리스트, 방문여부체크, 깊이체크)
    // 만약 depth == 5라면 1 출력하고 시스템 종료
    // 만약 방문했었다면 리턴
    // visited[정점] = true
    
    // 반복문 (list.size)
    // if !isited[정점] 라면 dfs
}

그리고 역시나 틀렸다.

 

반례를 찾을 것도 없이 문제에서 기본적으로 제시하는 예제조차 충족하지 못하고 있었다.

그래프 탐색 문제를 오랜만에 풀어봐서 기본적인 것도 까먹어버렸군..

 

 

바로 이 부분인데

이 예제가 실패하는 이유는 다음과 같다.

 

0 -> 1 탐색

1 -> 2 탐색

2 -> 3 탐색

3 - > 0 0은 이미 true이므로 실패

 

하지만 실제로는 이런 경우로 모두 이어질 수 있다.

4 -> 1 탐색

1 -> 0 탐색

0 -> 3 탐색

3 -> 2 탐색

2 -> 1 탐색

depth가 5이므로 1 출력

 

이 문제는 정답이 나올 때까지 모든 경우의 수를 뒤지는 게 목적이기 때문에 visited[v] = true 하나 던져주고 끝나면 망한다.

위의 성공 케이스를 마주하기 위해서는 4번에서 1번으로 가야하는데, 우리는 위에서 1번을 이미 옛날 옛적에 탐색했으니 4번은 더 이상 갈 곳이 없는 것이다.

해당 케이스에서는 계속해서 visited[v] = true를 체크해주되 1회 탐색이 끝났으면 다음 탐색을 위해 재귀에서 빠져나오는 시점에 다시 visited[v] = false로 돌려놔야 한다.

 

이걸 백트래킹이라고 하는데.. 처음 접하면 어렵지만 간단하게 생각해보면 별거 아니다. 너무 깊게 고민하지 말자.

 

기존의 방법은 이런 식이였다

: a(0)->b(0)->c(0)->d(0)->e(0)

true->true->true->true->true

이미 한 번 탐색한 정점은 절대 다시 방문할 수 없어짐

 

백트래킹 기법을 활용하면 아래와 같은 방법이 가능하다

: a(0) -> b(0) -> c(0) 탐색 실패?

빠져나오며 c(0)을 false로 만들어 b(1), b(2), b(3).. 에서 c(0)을 재탐색 가능하게 만들어준다.

 

나도 이제 간단한 백트래킹은 쉽게 생각하고 있었는데 굳이 생각하면서 글로 적으려니 헷갈리고 어려워지기 시작한다.

백트래킹은 그런 것이니 너무 깊게 생각하지 않는 게 좋다.

아무튼 주절주절 길어졌으니 기존 코드에 백트래킹을 적용해보자.

물론 저 말고 여러분이요..

 

그리고 그렇게 해도 해당 예제만 통과될 뿐 결국 또 틀렸다고 나온다.

이유가 뭘까?

위와 비슷한 맥락이지만 다른 위치에서 처리해줘야 한다.

 

반례

: 5 4

0 1

0 2

2 3

2 4

 

정답 : 1

위 코드대로 작성하면 : 0

 

직접 찾아보시길 바랍니다

정답은 아래에

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        // A,B,C,D,E가 한 번에 이어지는 경우를 찾아야 한다 -> DFS
        // 깊이가 5면 정답 처리하면 될 듯
        // 사람 수(정점)은 일반 그래프와 달리 0부터 순서대로 주어지니 주의하자
 
        // 총 정점 수 N과 간선 M 입력받기.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        // 반복문
        // 인접 리스트를 위해 ArrayList N번 만큼 생성
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        for (int i=0; i<N; i++) {
            lists.add(new ArrayList());
        }
 
        // 반복문
        // // M번 반복하며 간선 정보 입력받기
        // // 친구 관계는 무방향이므로 양쪽에 동일하게 넣어주자.
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
 
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
 
            lists.get(num1).add(num2);
            lists.get(num2).add(num1);
        }
 
        // 방문 여부 체크를 위한 배열 생성
        boolean[] visited = new boolean[N];
        // depth 체크용 변수 생성
        int depth = 0; // 별 의미는 없다.
        // 반복문
 
        // // 각 노드를 dfs로 탐색
        // // dfs (정점, 인접리스트, 방문여부체크, 깊이체크)
        for (int i=0; i<N; i++) {
            dfs(i, lists, visited, depth);
            Arrays.fill(visited, false);
        }
 
        System.out.println(0);
    }
 
    // dfs (정점, 인접리스트, 방문여부체크, 깊이체크)
    public static void dfs(int vertex, ArrayList<ArrayList<Integer>> lists, boolean[] visited, int depth) {
        // 만약 depth == 5라면 1 출력하고 시스템 종료
        if (depth == 4) {
            System.out.println(1);
            System.exit(0);
        }
        // 만약 방문했었다면 리턴
        // visited[정점] = true
//        if (visited[vertex]) return;
        visited[vertex] = true;
        // 반복문 (list.size)
        for (int i=0; i<lists.get(vertex).size(); i++) {
            int next = lists.get(vertex).get(i);
            if (!visited[next]) {
//                visited[next] = true;
                dfs(next, lists, visited, depth + 1);
                visited[next] = false;
            }
        }
        // if !isited[정점] 라면 dfs
    }
}

 

늘 그렇듯이 주석은 처음 한 번 작성하고 고치지 않으므로

틀린 내용이 있을 수 있으니 무시하자