[백준알고리즘] 그래프 - 13023 ABCDE 문제

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

13023번: ABCDE

ArrayList를 사용해본 적이 거의 없어서 이거 알아보는데만 좀 걸렸다...ㅋㅋㅋ

그래프 구현 + 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.tistory.com/m/685