99클럽 코테 스터디 5일차 TIL : BFS(백준 24444번)

 

 

백준 24444. 알고리즘 수업 - 너비 우선 탐색 1

 

 

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

 

---

⭐나의 풀이

 

🔎문제 정리)

문제에 주어진 BFS 덕에 알고리즘 해결법은 고민할 필요가 없었다 !

 

💡 아이디어) 
1. BFS

어제 해결한 DFS 문제에서 메소드를 BFS로만 변경하는 과정을 거쳤다.

BFS 는 주로 큐를 사용한다.

Queue<Integer> queue = new LinkedList<Integer>();

 

✔ 최종 제출한 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	/*
	 * 백준 24444. BFS
	 * 날짜: 2024-11-01
	 * 작성자: CSY
	 */
	private static List<Integer>[] arr;	//간선정보 
	private static boolean[] visited;	//방문여부 
	private static int[] answer;		//노드방문순서 
	private static int cnt=1;			//노드방문순서 
	private static Queue<Integer> queue;	//bfs 큐 
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		
		int n = Integer.parseInt(st.nextToken()); //정점수<=100,000
		int m = Integer.parseInt(st.nextToken()); //간선의 수<=200,000
		int r = Integer.parseInt(st.nextToken()); //시작지점<=100,000
		
		arr = new ArrayList[n+1];
		visited = new boolean[n+1];
		answer = new int[n+1];
		queue = new LinkedList<>();
		
		for(int i=1;i<n+1;i++) {
			arr[i] = new ArrayList<>();
		}
		
		//간선정보 받아와서 list에 저장
		for(int i=0;i<m;i++) {
			s = br.readLine();
			st = new StringTokenizer(s);
			
			int u = Integer.parseInt(st.nextToken()); //시작지점
			int v = Integer.parseInt(st.nextToken());   //도착지점
			
			arr[u].add(v);
			arr[v].add(u);
		}
		
		StringBuilder sb = new StringBuilder();
		
		bfs(r);
		
		for(int i=1;i<answer.length;i++) {
			sb.append(answer[i]+"\n");
		}
		
		System.out.println(sb);
	}
	
	static void bfs(int R) {  
	    visited[R]=true;
	    answer[R]=cnt;
	    cnt++;
	    queue.add(R);
	    
	    while(!queue.isEmpty()) {
	    	int edge = queue.poll();
	    	Object[] newArr = arr[edge].toArray();
	 	    Arrays.sort(newArr);
	    	for(Object newEdge : newArr) {
	    		int inewEdge = (int)newEdge;
	    		if(visited[inewEdge]!=true) {
	    			visited[inewEdge]=true;
	    			queue.add(inewEdge);
	    			answer[inewEdge]=cnt;
	    		    cnt++;
	    		}
	    	}
	    }
	}

}

 

결과

---

⭐코드 최적화

package bfs;

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

public class Day5 {

    private static List<Integer>[] arr;   // 간선 정보
    private static int[] answer;          // 노드 방문 순서
    private static int cnt = 1;           // 노드 방문 순서 카운트
    private static Queue<Integer> queue;  // bfs 큐 

    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()); // 정점의 수 (<=100,000)
        int m = Integer.parseInt(st.nextToken()); // 간선의 수 (<=200,000)
        int r = Integer.parseInt(st.nextToken()); // 시작 지점 (<=100,000)
        
        arr = new ArrayList[n + 1];
        answer = new int[n + 1];
        queue = new ArrayDeque<>();
        
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }
        
        // 간선 정보 저장 및 정렬
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            arr[u].add(v);
            arr[v].add(u);
        }

        // 각 인접 리스트를 미리 정렬하여 탐색 시 정렬하지 않도록 함
        for (int i = 1; i <= n; i++) {
            Collections.sort(arr[i]);
        }
        
        StringBuilder sb = new StringBuilder();
        
        bfs(r);
        
        for (int i = 1; i < answer.length; i++) {
            sb.append(answer[i]).append("\n");
        }
        
        System.out.print(sb);
    }
    
    static void bfs(int R) {  
        answer[R] = cnt++;
        queue.add(R);
        
        while (!queue.isEmpty()) {
            int edge = queue.poll();
            
            for (int newEdge : arr[edge]) {
                if (answer[newEdge] == 0) {  // answer 배열로 방문 여부 체크
                    queue.add(newEdge);
                    answer[newEdge] = cnt++;
                }
            }
        }
    }
}

✔ 정렬 최적화

문제) bfs함수에서 매번 정렬하는 것이 비효율적이다.

개선) 입력으로 간선 정보를 받을 때 각 리스트를 정렬하여, bfs 함수에서 매번 정렬하지 않게 한다.

 

✔ ArrayDeque 사용

문제) 메모리사용량 개선

개선)  ArrayDeque는 LinkedList보다 큐로서의 성능이 뛰어나며, 메모리 사용량을 줄일 수 있다.

 

✔ visited 배열 제거

문제) 메모리사용량 개선

개선) answer 배열만으로 방문 여부를 판단하여 메모리 사용을 줄일 수있다.

(answer[i] == 0이면 방문하지 않은 것으로 간주)

 

💡  기대 효과

이 최적화를 통해 시간 복잡도와 메모리 사용량을 줄일 수 있다.

Arrays.sort의 호출 빈도를 줄임으로써 속도가 개선되고, visited 배열을 제거하여 메모리 사용량도 감소했다.