[백준][1260] DFS와 BFS - JAVA

백준 1260번 DFS와 BFS

---

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

1260번: DFS와 BFS

문제 해석

---

DFS와 BFS 기본기를 익힐 수 있는 문제.

입력으로 들어오는 정점 연결 정보를 이용하여 DFS, BFS 탐색을 수행하여

탐색한 순서를 출력하면 됩니다.

입력 : 정점의 개수(N), 간선의 개수(M), 정점 번호(V)

두 정점을 잇는 간선 연결 정보

출력 : 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력합니다.

 

 

문제 풀이

---

DFS와 BFS의 연결 정보를 저장하기 위해서 ArrayList와 배열중 배열을 사용하였습니다.

한 정점에서 다른 정점으로 이어진 간선이 많을 경우 작은 정점부터 출력해야하는데

배열을 이용해서 For문을 작은 인덱스부터 반복하면 수월하다고 판단하였기 때문입니다.

 

DFS는 재귀함수(스택), BFS는 큐로 구현하였으며, 변수명을 cur, next로 정의하여

알고리즘 설계에 도움을 주었습니다.

 

package test1;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class bj_dfsbfs_1260 {
    static int N, M, V;
    static boolean map[][];
    static boolean visited[];
    static boolean visited2[];
    static Queue<Integer> queue = new LinkedList<>();

    static StringBuilder sb = new StringBuilder();
    static StringBuilder sb2 = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        map = new boolean[N+1][N+1];
        visited = new boolean[N+1];
        visited2 = new boolean[N+1];


        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            map[from][to] = true;
            map[to][from] = true;
        }

        dfs(V);
        System.out.println(sb.toString());

        bfs(V);

        System.out.println(sb2.toString());
    }

    static void dfs(int cur) {
        visited[cur] = true;
        sb.append(cur + " ");
        for(int i=0; i<N+1; i++) {
            if(map[cur][i]) {
                int next = i;
                if(visited[next]) continue;
                dfs(next);
            }
        }

    }

    static void bfs(int start) {
        queue.offer(start);
        visited2[start] = true;
        sb2.append(start+ " ");
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            for(int i=0; i<N+1; i++) {
                if(map[cur][i]) {
                    if(visited2[i]) continue;
                    visited2[i] = true;
                    sb2.append(i + " ");
                    queue.offer(i);
                }
            }
        }
    }
}

DFS와 BFS는 코딩 테스트에서 빈출 문제임으로 기본기를 탄탄하게 한다는 생각으로

습관적으로 풀이하고 있습니다.