[백준 1260] DFS와 BFS (JAVA)

백준 1260번 문제  - DFS와 BFS 

1260번: DFS와 BFS

---

문제 분석

 

 

• 정점 수와 간선, 그리고 시작할 노드를 입력받는다. 이를 토대로 해당 노드에서 시작했을 때 DFS와 BFS를 출력한다.

 

---

해결 키 포인트

 

• DFS(깊이 우선 탐색) 개념 파악 
• BFS(너비 우선 탐색) 개념 파악

---

깊이 우선 탐색(DFS)

 

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

 

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

 

깊이 우선 탐색의 핵심 이론

 

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

 

알고리즘

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

 

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

 

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

 

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

 

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

---

너비 우선 탐색(BFS)

 

그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

 

너비 우선 탐색의 핵심 이론

 

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

 

알고리즘

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

 

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

 

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

 

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

 

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

---

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList[] list;
    static boolean[] isChecked;

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N,M,V 입력
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken()) - 1;

        // 확인여부 list | 인접노드를 알려줄 list 생성
        isChecked = new boolean[N];

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

        // 간선 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken()) - 1;
            int e = Integer.parseInt(st.nextToken()) - 1;

            list[s].add(e);
            list[e].add(s);
        }

        // 인접노드 오름차순 정렬
        for (int i = 0; i < N; i++) {
            Collections.sort(list[i]);
        }

        // DFS 확인
        DFS(V);
        bw.write("\n");

        // 체크했는지 여부 리스트 초기화
        isChecked = new boolean[N];

        // BFS 확인
        BFS(V);
        bw.write("\n");

        // 출력
        bw.flush();
        bw.close();
    }

    public static void DFS(int index) throws IOException {
        if (isChecked[index]) return;

        // 출력
        bw.write(index + 1 + " ");

        // 체크했음을 기록
        isChecked[index] = true;

        // 인접 노드 확인
        for (int i = 0; i < list[index].size(); i++) {
            DFS((Integer) list[index].get(i));
        }
    }

    public static void BFS(int index) throws IOException {
        Queue<Integer> queue = new LinkedList();
        queue.add(index);
        isChecked[index] = true;

        while (!queue.isEmpty()) {
            // 출력
            index = queue.poll();
            bw.write(index + 1 + " ");

            // 인접 노드 확인
            for (int i = 0; i < list[index].size(); i++) {
                int newIndex = (Integer) list[index].get(i);

                // 확인한 노드가 아니면 queue에 삽입 후 확인했음을 기록
                if (!isChecked[newIndex]) {
                    queue.add(newIndex);
                    isChecked[newIndex] = true;
                }
            }
        }
    }
}