[백준 24445번 / java] 알고리즘 수업 - 너비 우선 탐색 2

문제

24445번: 알고리즘 수업 - 너비 우선 탐색 2 (acmicpc.net)

풀이 1

1. 인접 행렬 생성 (무방향)

2. bfs탐색 -> 큐에서 노드를 꺼내 인접 노드를 방문 (내림차순으로)

3. 방문체크된(큐에 넣은) 순서 정보를 따로 저장하여 출력하기

 

주어진 테스트 케이스, 만든 테스트 케이스 모두 통과됐지만

메모리 초과가 발생했다.

인접 행렬은 직관적이고 구현이 간단하지만, 이차원 배열이므로

노드 개수가 많을 경우 메모리 사용량이 상당히 많아진다.

 

• 인접행렬 메모리 초과 이유

메모리 제한 : 512MB

노드 수 : 5 <= N <= 100,000

간선 수 : 1 <= M <= 200,000

 

각 배열 원소는 int형이므로 4byte를 차지한다.

최악의 경우(N=100,000) 필요한 메모리는

100,000 * 100,000 * 4 = 40,000,000,000 byte = 약 37.25GB  >>>>  512MB

(10^3 MB = 1GB)

* byte -> KB -> MB -> GB 순으로 10^3배씩 늘어남

 

코드 1

//메모리 초과
import java.util.*;
import java.io.*;
public class Main {
    static int N;
    static Queue<Integer> q = new LinkedList<>();
    static boolean[] visited;
    static int[][] arr;
    static int[] ans;
    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());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        arr = new int[N+1][N+1];
        visited = new boolean[N+1];
        ans = new int[N+1];

        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][v] = arr[v][u] = 1;
        }
        bfs(R);
        ans[R] = 1;
        for(int i=1; i<=N; i++)
            System.out.println(ans[i]);

    }
    static void bfs(int R){
        int count = 2;

        q.offer(R);
        visited[R] = true;

        while(!q.isEmpty()){
            int now = q.poll();

            for(int i=N; i>=1; i--){
                if(arr[now][i] == 1 && !visited[i]){ //R과 인접한 노드 중 방문하지 않은 노드를 내림차순으로 탐색
                    q.offer(i);
                    visited[i] = true;
                    ans[i] = count++;
                }
            }

        }

    }
}

풀이 2

메모리 사용량을 줄이기 위해 인접행렬 대신 인접 리스트를 사용한다.

• 인접 리스트 사용 시 메모리 사용량

인접 리스트의 경우 간선을 저장함으로써 메모리가 사용된다.

무방향 그래프의 경우 각 간선은 두 번 저장된다. 

Integer 객체 포인터의 참조는 8byte를 차지한다.

 

최악의 경우 메모리 사용량 :

2 * 200,000(간선의 개수) * 8byte = 400,000 * 8 = 3,200,000byte = 3.05MB <<< 512MB

코드 2

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

public class Main {
    static int N, M, R;
    static int[] ans;
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        ans = new int[N+1];
        visited = new boolean[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 u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        bfs(R);
        for(int i=1; i<=N; i++)
            bw.write(ans[i] + "\n");
        bw.close();
    }
    static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        int count = 1;

        q.offer(start);
        visited[start] = true;
        ans[start] = count++;

        while(!q.isEmpty()){
            int now = q.poll();
            Collections.sort(graph.get(now), Collections.reverseOrder()); //graph를 내림차순 정렬
            for(int tmp : graph.get(now)){ //인접 노드 탐색
                if(!visited[tmp]){
                    q.offer(tmp);
                    visited[tmp] = true;
                    ans[tmp] = count++;
                }
            }
        }
        return;
    }
}

Note

• 인접 리스트를 사용해 그래프를 처음 표현해보았다.