[백준] 24444 알고리즘 수업 - 너비 우선 탐색 1 - BFS(너비우선탐색) JAVA

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

코드설명

BFS(너비우선탐색) 을 활용합니다.

 

이 문제의 경우 고민했던점은, 무방향 그래프를 어떻게 저장할까 라는 고민이었습니다.

가장 편한 방식은 matrix[][] 를 구현해서 각 정점의 연결을 표현합니다.

하지만, 이 방법을 활용한다면 정점의 수는 10^5 입니다.

행렬이기에, 10^10 이 되고 이는 int형일경우 Byte로 변환하면 (10^10) * 4 byte가 됩니다.즉, 40GB가 됩니다.

메모리 제한 512MB를 훌쩍 뛰어넘습니다.

그러므로 ArrayList로 구현하여 연결하여야 메모리초과가 발생하지 않습니다.

 

또, 이떄 유의점은 연접정점들을 오름차순으로 정렬하여야 합니다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, R;
	static int[] answer;
	static ArrayList<Integer>[] arr = new ArrayList[100001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		answer = new int[N];
		for(int i=0;i<100001; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			arr[u].add(v);
			arr[v].add(u);
		}
		
		for(int i=0;i<N;i++) {
			Collections.sort(arr[i]);
		}
		
		BFS(R - 1);
		for(int i=0;i<N;i++) {
			System.out.println(answer[i]);
		}
	}
	
	static void BFS(int now) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(now);
		boolean[] visited = new boolean[N];
		visited[now] = true;
		
		int rank = 1;
		while(!q.isEmpty()) {
			int temp = q.poll();
			answer[temp] = rank++;
			for(int next = 0; next < arr[temp].size(); next++) {
				int nextNode = arr[temp].get(next);
				if(visited[nextNode] == true) continue;
				visited[nextNode] = true;
				q.offer(nextNode);
			}
		}
	}
}