[백준] 1260번 : DFS와 BFS - JAVA [자바]

문제

문제 링크 : https://www.acmicpc.net/problem/1260

---

수도코드 작성

dfs

bfs

 

---

작성한 코드

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

public class Main {

    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

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

        int N = Integer.parseInt(st.nextToken()); // 정점 개수
        int M = Integer.parseInt(st.nextToken()); // 간선 개수
        int V = Integer.parseInt(st.nextToken()); // 시작 정점

        graph = new ArrayList[N+1];
        for (int i=1; i<=N; i++){
            graph[i] = new ArrayList<>();
        }

        // 간선 입력 (양방향)
        for (int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);
            graph[b].add(a);
        }
        // 번호 작은거부터 방문하기 위해 정렬
        for (int i=1; i<=N; i++){
            Collections.sort(graph[i]); // ArrayList sort
        }
        // dfs
        visited = new boolean[N+1];
        dfs(V);
        sb.append('\n');

        // bfs
        visited = new  boolean[N+1];
        bfs(V);

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

    static void dfs(int node){
        visited[node] = true;
        sb.append(node).append(' ');

        for (int next : graph[node]){
            if (!visited[next]){
                dfs(next);
            }
        }
    }

    static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;

        while (!q.isEmpty()){
            int cur = q.poll();
            sb.append(cur).append(' ');

            for (int next : graph[cur]){
                if(!visited[next]){
                    visited[next] = true;
                    q.add(next);
                }
            }
        }

    }
}

---

보완할 점 / 헷갈린 점

처음 DFS / BFS를 제대로 풀어봐서 이해하는데 시간이 조금 걸렸다
DFS는 재귀 형식으로 풀고

BFS는 큐에 넣고 다음 주소 부르라는 식으로 이해했는데 조금 더 문제들을 풀면서 이게 맞는 지 확인 해봐야겠다.

 

일단 처음에 ArrayList<Integer> 배열에 간선들을 다 넣고 시작하고
그리고 처음 정점들을 visited = true로 넣고 시작하는게 중요한 것 같다.