99클럽 코테 스터디 5일차 TIL : BFS

 

문제

백준 알고리즘 수업 - 너비 우선 탐색 1  | 실버 2

#그래프 이론 #그래프 탐색 #정렬 #너비 우선 탐색

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

 

풀이 & 코드

* 전형적인 BFS 문제

* 문제에서 list 내부의 숫자들을 '오름차순'으로 관리한다 했으므로, Collections.sort를 진행해준다

* 1,2,3,4,5 가 예시일 경우, 답변은 1이 언제, 2가 언제 등 각 노드가 언제 연결되는지를 결정해줘야 하므로 visited 배열에 cnt로 체킹해준 값을 넣어준다.

 

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

public class q24444 {
    static int n,m,r = 0;
    static List<List<Integer>> graph = new ArrayList<>();
    static Queue<Integer> queue = new LinkedList<>();
    static int[] visited;
    static int cnt = 1;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        visited = new int[n+1];

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

        for(int i = 0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(r).add(v);
            graph.get(v).add(r);
        }

        for(int i = 1; i<=n; i++){
            Collections.sort(graph.get(i));
        }

        queue.offer(r);
        visited[r] = 1;
        bfs();

        for(int i = 1; i<=n; i++){
            System.out.println(visited[i]);
        }
    }

    public static void bfs(){
        while(!queue.isEmpty()){
            int cur = queue.poll();

            for(int i = 0; i<graph.get(cur).size(); i++){
                int next = graph.get(cur).get(i);
                if(visited[next] == 0){
                    cnt++;
                    visited[next] = cnt;
                    queue.offer(next);
                }
            }
        }
    }
}

 

회고 & 배운점

* BFS 공부 (https://www.notion.so/dev-if/f2a7fe2bdc3b4878aef9442fe5ff0d20?pvs=4#51fe65b400d04edcb21f58396e7bf82d)

 

* 처음에는 배열로 풀었을 때 타임아웃이 발생했음 

   * DFS를 할 때, 배열로 풀게되면 재귀 호출마다 '깊은 복사'가 발생함 => 시간과 메모리 비용이 커져서 타임아웃이 발생할 가능성이 높음

   * 반면, 리스트는 주로 '얕은 복사'가 발생함 => 즉, 참조만 넘기기 때문에 메모리 복사가 덜 일어나 기능 상 이점이 있음 !! 

 

* 마지막에 visited 출력해줄 때도, print 하는 것보단 string builder 사용해서 출력시 메모리가 훨씬 효율적이다.