[백준 13023] ABCDE (JAVA)

백준 13023번 문제  - ABCDE

13023번: ABCDE

---

문제 분석

 

• 5가지 숫자가 순서대로 연결되어있으면 1, 아니면 0을 출력하는 문제

 

---

해결 키 포인트

 

• DFS(깊이 우선 탐색) 개념 파악 
• 노드 확인했는지 체크해주는 변수 초기화 적절하게 해야함 
  • 해당 index 노드 인접노드 확인 끝나면, 해당 노드 false로 다시 초기화

---

깊이 우선 탐색(DFS)

 

그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다.

 

깊이 우선 탐색의 핵심 이론

 

• 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트로 표현
• DFS의 탐색 방식은 후입 선출 특성을 가짐 ( 재귀함수 사용 많음 / 스택도 사용 )

 

알고리즘

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

 

Do It! 알고리즘 코딩 테스트

 

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입 (이를 모든 정점을 다한다)

 

Do It! 알고리즘 코딩 테스트

 

만약 스택에 노드가 없으면, 방문하지 않은 정점을 알아내, 스택에 삽입하고 다시 2번 단계를 반복한다.

---

코드

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

public class Main {
    // 현재 조건을 만족하는 친구관계가 있는지에 대한 변수
    public static boolean checkFriendShip = false;
    // 해당 index가 검사됬는지 확인하는 변수
    public static boolean [] checkIndex;
    // 각 index의 근접 노드를 저장하는 변수
    public static ArrayList [] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // N, M 입력
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 변수 세팅
        list = new ArrayList[N];

        for(int i=0;i<N;i++) {
            list[i] = new ArrayList();
        }

        // M번 반복해서 수 입력
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());

            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());

            // 인접 노드 등록
            list[first].add(second);
            list[second].add(first);
        }
        br.close();

        // 모든 수를 확인하면서 DFS 확인
        for(int i=0;i<N;i++) {
            checkIndex = new boolean[N];

            DFS(i, 1);
            // 친구관계를 만족했을 경우, 종료
            if(checkFriendShip) break;
        }
        // 친구관계를 만족한 경우 1, 아닌 경우 0 출력
        if(checkFriendShip)
            bw.write("1");
        else
            bw.write("0");

        bw.flush();
        bw.close();
    }

    public static void DFS(int index, int count) {

        // 확인 된 변수 일 경우, return
        if(checkIndex[index]) {
            return;
        }

        // 깊이가 5일 경우 친구관계를 만족한 것이므로 true로 변환 후 return
        if(count == 5)  {
            checkFriendShip = true;
            return;
        }

        // 확인했으니 확인했다고 해당 변수 변환
        checkIndex[index] = true;

        // 지금 연관된 인접노드 확인하면서 count 확인
        for(int i=0;i<list[index].size();i++) {
            DFS((Integer) list[index].get(i), count+1);

            // count가 만족하면 종료
            if(checkFriendShip)
                break;
        }

        // 다음 DFS에 방해되지 않게 초기화
        checkIndex[index] = false;
    }
}