(백준 알고리즘) 그래프 – 13023 ABCDE 문제

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

나는 ArrayList를 거의 사용하지 않았기 때문에 이것을 알아내는 데 시간이 걸렸습니다 … lol

그래프 구현 + dfs 문제이기 때문에 이 두 가지 개념에 대한 감을 잡기에 좋은 문제인 것 같습니다.

아직 익숙하지 않아서 다른 분들의 코드를 참고하며 공부했습니다.

문제가 관계와 관련된 문제라면 그래프 구현을 통해 해결할 수 있는지 먼저 생각하십시오.

솔루션 코드

package baekjoonWeek4;

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class ABCDE {    //백준 13023번 ABCDE 문제
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();    //친구 관계 저장 리스트
    static boolean() visited;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String() args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());   //N은 사람의 수
        int M = Integer.parseInt(st.nextToken());   //M은 관계의 수
//        ArrayList<Integer>() g = (ArrayList<Integer>()) new ArrayList(N);

        for(int i=0;i<N;i++)      //그래프 초기화
            graph.add(new ArrayList<>());

        int a; int b;
        //인접리스트 채우기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
//            g(a).add(b);
            graph.get(a).add(b);    //a 리스트에 b 추가, a-b는 관계가 있음 나타냄
            graph.get(b).add(a);    //관계는 양방향이므로 반대로도 해줌
        }
        visited = new boolean(N);

        for(int i=0;i<N;i++) {    //각 노드 기준 DFS 탐색 시작
//            visited = new boolean(N);
            dfs(i,1);
        }
        bw.write("0");  //끝끝내 없었으면 0 출력
        bw.flush();
        bw.close();
    }


    static void dfs(int n, int count) throws IOException {  //탐색할 노드와 횟수(5번이 되면 성공), count는 1에서 시작
        if (count == 5) {
            bw.write("1");
            bw.flush();
            bw.close();
            System.exit(0); //확인됐으면 더 볼 필요 없으므로 종료
        }
        visited(n) = true;  //방문체크
        for(int i=0;i<graph.get(n).size();i++) {
            if(!visited(graph.get(n).get(i))) {    //n번 노드의 i번째를 아직 방문 안한경우
                dfs(graph.get(n).get(i),count+1);   //해당 i번째 노드의 관계를 살펴본다, 카운트 증가
            }
        }
        visited(n) = false;
        return;
    }
}

참조 블로그: https://tussle.m/685