[BOJ] DFS와BFS - 1260(BFS/DFS)

백준 - DFS와 BFS

package dfs.Day250228;

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

public class DFS와BFS {

    public static List<Integer>[] edgeList;
    public static boolean[] visited;
    public static List<Integer> dfsResult = new ArrayList<>();
    public static List<Integer> bfsResult = new ArrayList<>();

    public static void solution(int[][] graph, int startNode, int n) {
        edgeList = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < edgeList.length; i++) {
            edgeList[i] = new ArrayList<>();
        }

        for (int[] i : graph) {
            edgeList[i[0]].add(i[1]);
            edgeList[i[1]].add(i[0]);
        }

        for (List<Integer> integers : edgeList) {
            integers.sort(Comparator.comparingInt(o1 -> o1));
        }

        dfs(startNode);
        visited = new boolean[n + 1]; // 초기화
        bfs(startNode);
    }

    public static void dfs(int startNode) {
        dfsResult.add(startNode);
        visited[startNode] = true;

        for (int i : edgeList[startNode]) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }

    public static void bfs(int startNode) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        visited[startNode] = true;
        queue.add(startNode);

        // 비어 있지 않으면
        while (!queue.isEmpty()) {
            int poll = queue.poll();
            bfsResult.add(poll);

            for (int i : edgeList[poll]) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }

        }
    }

    public static void main(String[] args) throws IOException {
        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()); // 시작 정점

        int[][] graph = new int[m + 1][2];
        for (int i = 1; i < m + 1; i++) {
            st = new StringTokenizer(br.readLine());
            graph[i][0] = Integer.parseInt(st.nextToken());
            graph[i][1] = Integer.parseInt(st.nextToken());
        }

        solution(graph, v, n);

        for (int i : dfsResult) {
            System.out.print(i + " ");
        }

        System.out.println();
        for (int i : bfsResult) {
            System.out.print(i + " ");
        }
    }
}

문제

오늘은 백준에서 1260번째 문제인 DFS와 BFS를 풀었습니다.
기본 DFS와 BFS를 알고 있으면 쉽게 풀수 있는 문제입니다!

정점의 개수, 간선의 개수, 시작 정점이 주어진 후
간선의 개수 만큼 값들이 주어집니다.

그리고 그 값들을 각각 dfs/bfs으로 값들이 흘러가는 순서를 출력하면됩니다!

조건

하나의 조건이 붙습니다.
1이라는 노드의 근접한 노드들이 2,3,4가 있다고 하면 값이 작은 것 부터 진행하는 조건 입니다.

for (List<Integer> integers : edgeList) {
	integers.sort(Comparator.comparingInt(o1 -> o1));
}

저는 그래프를 만든 후 다시 for문을 돌려서 값이 작은 것들이 앞으로 오게 했습니다.

마무리

그래도 아무것도 보지 않고 풀지는 못했습니다.
(Comparator.comparingInt(o1 -> o1)) 부분은 기억이 안나서 검색을 한 후 사용했습니다. 🥲