99클럽 코테 스터디 6일차 TIL - BFS, DFS

문제 💁🏻‍♂️

문제 링크 - 백준 1260 DFS와 BFS

해결 과정

이 문제는 정말 그래프 탐색의 기본인 DFS & BFS 기본 문제이다.

사고 과정 ❗️

나름 특별한 점이 있다면, 이 문제를 파이썬이 아닌 자바로 구현했다는 점이다. 자바로 구현할 때, 복잡하다고 느꼈던 점은 다음과 같다.

1. 정렬의 기준을 정해줘야 한다는 점
2. ArrayList<ArrayList<Node>> 너무 길다는 점
3. append(), pop() 이 아닌, offer(), poll()

그냥 전반적으로 파이썬 코드와 자바 코드의 구현이 비슷한 점이 하나도 없다는 점에서 조금 힘들었다. 이제 자바에 익숙해져야 하는데, 하나씩 바꿔나가는 과정을 겪으면서 자바 언어의 이해도를 높여야 겠다는 생각을 했다. 로직은 알고 있었기 때문에 해당 문제는 어렵지 않게 해결할 수 있었다!

코드

정답 코드

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

public class Main {

    static class Node implements Comparable<Node> {
        int idx;

        Node(int idx) {
            this.idx = idx;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.idx, other.idx);
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static int N, M, V;
    static ArrayList<ArrayList<Node>> vertex = new ArrayList<>();
    static boolean[] visited;

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= N; i++)
            vertex.add(new ArrayList<Node>());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            vertex.get(v1).add(new Node(v2));
            vertex.get(v2).add(new Node(v1));
        }

        // 각 정점에 담긴 인덱스들을 오름차순 정렬
        for (ArrayList<Node> lst : vertex)
            Collections.sort(lst);

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

        bw.write("\n");
        Arrays.fill(visited, false);
        bfs(V);

        bw.close();
    }

    private static void dfs(int curr) throws IOException {

        bw.write(curr + " ");
        visited[curr] = true; // 방문 처리

        for (int i = 0; i < vertex.get(curr).size(); i++) {
            Node nxt = vertex.get(curr).get(i);
            // 방문하지 않은 경우 -> 탐색
            if (!visited[nxt.idx]) {
                dfs(nxt.idx);
            }
        }
    }

    private static void bfs(int s) throws IOException {

        ArrayDeque<Integer> dq = new ArrayDeque<>();
        dq.offer(s);
        visited[s] = true; // 방문 처리

        bw.write(s + " ");
        while (!dq.isEmpty()) {

            int curr = dq.poll();

            for (int i = 0; i < vertex.get(curr).size(); i++) {
                Node nxt = vertex.get(curr).get(i);
                if (!visited[nxt.idx]) {
                    bw.write(nxt.idx + " ");
                    visited[nxt.idx] = true; // 방문 처리
                    dq.offer(nxt.idx);
                }
            }

        }
    }
}

Reference

• 내 머릿 속