[JAVA] 백준 (골드5) 13023번 ABCDE

링크

https://www.acmicpc.net/problem/13023

---

문제 설명

정답률 28.781%
BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

---

입력 예제

• 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
• 둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

5 4
0 1
1 2
2 3
3 4

---

출력 예제

• 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

1

---

풀이

문제의 조건을 간단히 하면 연속하는 5개의 노드 존재 여부를 판단하는 것이다. 단순히 모든 노드에 대해 탐색하는 것이 아니라 깊이가 5가 될 때를 찾아야 하므로 백트래킹을 DFS로 구현한다.

위의 그래프를 탐색한다고 하면 다음과 같다.

• 0
  • 1
    • 3
      • 2
      • 4 (자식 노드의 탐색이 끝나면 부모 노드인 3은 미방문 처리)
    • 4
      • 3 (미방문 처리로 인해 다시 방문 가능)
        • 2
          ...

단 방문 여부를 판단하는 것이 중요한데 인접 노드를 자식 노드라 생각할 때 자식 노드를 탐색하고 난 뒤 부모 노드는 다시 미방문 처리를 해줘야 한다. 그래야 다른 노드가 해당 노드에 대해 다시 탐색을 할 때 자식 노드로써 다시 방문할 수 있다.

//인접 노드를 방문하지 않았을 때
if (!visited[adjNode]) {
    //현 노드를 방문 처리
    visited[node] = true;
    dfs(adjNode, depth + 1);
    //인접 노드 탐색이 끝나면 현 노드는 미방문 처리
    visited[node] = false;
}

코드

//백준
public class Main {

    static List<List<Integer>> adjList = new ArrayList<>();
    static boolean[] visited;
    static boolean flag;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        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());  //친구 관계의 수
        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            adjList.add(new ArrayList<>());
        }

        //인접 리스트 초기화
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            adjList.get(a).add(b);
            adjList.get(b).add(a);
        }

        //모든 노드에 대하여 dfs
        for (int i = 0; i < N; i++) {
            if (flag) break;  //이미 연속된 5개 노드가 확인되면 break
            dfs(i, 1);
        }

        System.out.println(flag ? 1 : 0);
    }

    static void dfs(int node, int depth) {
        //깊이가 5가 되면 재귀 중단
        if (depth == 5) {
            flag = true;
            return;
        }

        //인접 노드에 대하여 반복
        for (Integer adjNode : adjList.get(node)) {
            //인접 노드를 방문하지 않았을 때
            if (!visited[adjNode]) {
                //현 노드를 방문 처리
                visited[node] = true;
                dfs(adjNode, depth + 1);
                //인접 노드 탐색이 끝나면 현 노드는 미방문 처리
                visited[node] = false;
            }
        }
    }

}