99클럽 코테 스터디 11일차 보너스1 - (DFS/BFS)

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

🚨 오늘의 학습

⭐️BFS⭐️

깊이우선 탐색 = 재귀
더 깊은 노드 찾기(더 이상 깊은 노드가 없을 때 까지)

⭐️DFS⭐️

너비우선 탐색 = Queue
Queue.add(시작 노드) -> Queue.poll() -> Queue.add(연결된 노드)

🗝️ 연결리스트 초기화 필수!!

        graph = new ArrayList<>(edge+1);
        for (int i = 0; i <edge; i++) {
            graph.add(new ArrayList<>());
        }

---

package com.example.algorithm.graph;

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

public class BFSvsDFS {

    static int[] dfsVisited;
    static int[] bfsVisited;
    static int edge = 0;
    static int node = 0;
    static int startNode = 0;
    static int endNode = 0;
    static ArrayList<ArrayList<Integer>> graph;
    static Queue<Integer> bfsQueue = new LinkedList<>();
    static int step = 0;

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

        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());
        startNode = Integer.parseInt(st.nextToken());

        dfsVisited = new int[node+1];
        bfsVisited = new int[node+1];

        /** 
         * 연결 리스트 초기화 필수!!
         */
        graph = new ArrayList<>(edge+1);
        for (int i = 0; i <edge; i++) {
            graph.add(new ArrayList<>());
        }

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

            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            graph.get(node1).add(node2);
            graph.get(node2).add(node1);

        }


        dfs(startNode);

        for(int i=0; i<dfsVisited.length;i++ ){
            if (dfsVisited[i] != 0) {
                System.out.print(dfsVisited[i] +" ");
            }
        }

        step=0;
        bfsQueue.add(startNode);

        while(!bfsQueue.isEmpty()){
            bfs(bfsQueue.poll());

        }

        for(int i=0; i<bfsVisited.length;i++ ){
            if (bfsVisited[i] != 0) {
                System.out.print(bfsVisited[i] +" ");
            }
        }



    }

    public static void dfs(int startNode){
        step++;

        dfsVisited[startNode] = step;

        for(int i=0; i<graph.get(startNode).size();i++){
            if(dfsVisited[graph.get(startNode).get(i)]==0){
                dfs(graph.get(startNode).get(i));
            }
        }

    }

    public static void bfs(int startNode){
        if(bfsVisited[startNode]==0){
            step++;
            bfsVisited[startNode] = step;
        }

        for(int i=0; i<graph.get(startNode).size();i++){
            if(bfsVisited[graph.get(startNode).get(i)]==0){
                bfsQueue.add(graph.get(startNode).get(i));
            }
        }

    }

}

오늘의 회고

• DFS와 BFS구현을 차이를 확실히 이해할 수 있었다.
• 하지만 공통적으로 중요한 점은 graph와 visited였다
• 노드의 재방문을 막기위한 노트 탐색 여부 확인은 필수!