[백준] 24444 : 알고리즘 수업 - 너비 우선 탐색 1 (Deque vs. LinkedList)

문제 출처 : https://www.acmicpc.net/problem/24444

소요 시간 : 시도(30m) + 풀이(20m)

---

문제

---

시도

 

문제에서 주어진 Pseudo 코드를 기반으로 코드를 작성했다. 

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

public class Main {

    private static BufferedReader br;
    private static StringTokenizer st;
    private static boolean[] visited;
    private static ArrayList<ArrayList<Integer>> graph;
    private static Queue<Integer> queue;
    private static int[] answer;

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

        int n = Integer.parseInt(st.nextToken());    // 5 ~ 100,000
        int m = Integer.parseInt(st.nextToken());    // 1 ~ 200,000
        int r = Integer.parseInt(st.nextToken());    // 1 ~ n

        answer = new int[n + 1];

        visited = new boolean[n + 1];
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());

        int u, v;    // 1 <= u < v <= n
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());

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

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

        bfs(r);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(answer[i]).append("\n");
        }

        System.out.print(sb);
    }

    public static void bfs(int r) {
        queue = new LinkedList<>();
        queue.add(r);
        visited[r] = true;

        int idx = 1;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            answer[u] = idx++;

            ArrayList<Integer> graphSon = graph.get(u);
            for (int i = 0; i < graphSon.size(); i++) {
                int v = graphSon.get(i);
                if (!visited[v]) {
                    visited[v] = true;
                    queue.add(v);
                }
            }
        }
    }
}

 

정답이었고, 총 980 ms가 소요되었다. 

---

풀이

 

더 좋고 깔삼한 풀이를 찾아 다른 사람 코드를 참고했다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

//	오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다.
//	아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
//
//	N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다.
//	정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.
//
//	인접 정점은 오름차순으로 방문한다.

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 정점의 수
		int M = Integer.parseInt(st.nextToken()); // 간선의 수
		int R = Integer.parseInt(st.nextToken()); // 시작 정점

		List<Integer>[] contact = new ArrayList[N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());

			// 무방향 그래프이므로, 양쪽 방향이 모두 연결되어 있다고 해주어야 한다.
			if (contact[from] == null)
				contact[from] = new ArrayList<>();
			contact[from].add(to);
			if (contact[to] == null)
				contact[to] = new ArrayList<>();
			contact[to].add(from);
		}

		boolean[] visited = new boolean[N + 1]; // 해당 정점의 방문 여부를 저장할 배열
		int[] sequence = new int[N + 1]; // 해당 정점에 몇 번째로 방문했는지 기록할 배열
		Deque<Integer> Queue = new ArrayDeque<>(); // 정점의 방문을 다룰 덱! (큐처럼 쓸거임)

		int cnt = 1; // 초기 방문 순서 1
		// 목표 : 정점 R부터 오름차순 너비 우선으로 방문해보자!	
		Queue.addLast(R);
		visited[R] = true;
		sequence[R] = cnt++;
		while (!Queue.isEmpty()) {
			int curr = Queue.pollFirst();
			// 현재 정점에 연결된 간선이 있다면
			if (contact[curr] != null) {
				// 오름차순으로 정렬하고 방문해보자.
				Collections.sort(contact[curr]);
				for (int j = 0; j < contact[curr].size(); j++) {
					int target = contact[curr].get(j);
					// 물론 방문한 적 없을 때만 방문해야 한다.
					if (visited[target] == false) {
						visited[target] = true;
						sequence[target] = cnt++;
						Queue.addLast(target);
					}
				}
			}
		} // 목표 while문 끝나는 곳

		for (int k = 1; k <= N; k++)
			sb.append(sequence[k]).append("\n");

		System.out.println(sb);
		br.close();

	} // main
} // class}

 

풀이 로직에 차이는 없었지만, 이 사람의 코드가 820 ms로 더 빨랐다.

 

왜 더 빠른지 찾아보니 이 코드는 간선을 정렬할 때, queue에 저장되는 숫자만을 정렬하는 반면 나는 모든 간선 집합에 대해 정렬을 시도하여 더 시간이 소요된 것이었다.

 

이 사실을 토대로 내 기존 코드도 변환해보니 기존 980ms 에서 904ms로 훨씬 줄어들었다.

---

알게 된 점

 

◈ 기존 코드와 참고 코드를 비교한 결과 (powered By. chatGPT)

제공된 코드가 여러 이유로 인해 여러분의 코드보다 빠른 것으로 나타나는데, 이러한 이유는 다음과 같습니다: 

1. 인접 리스트 사용: 제공된 코드는 그래프를 나타내는 데 인접 리스트 표현을 사용합니다(List<Integer>[] contact). 이는 희소한 그래프에 대해 인접 행렬보다 효율적인 표현입니다. 이것은 인접한 정점을 더 빨리 탐색할 수 있게 해줍니다.

2. 인접한 정점 정렬: 코드는 각 정점의 인접 정점 목록을 오름차순으로 정렬합니다. 이렇게 함으로써 정점이 큐에서 제거될 때 교환 횟수를 줄일 수 있습니다.

3. 효율적인 자료 구조 사용: 코드는 큐 연산에 대해 Deque (ArrayDeque<Integer>)를 사용하고 있을 수 있습니다. 이는 Queue (LinkedList<Integer>)를 사용하는 것보다 상수 요소와 메모리 사용 면에서 더 효율적일 수 있습니다.

 

4. 루프 내 조건 검사 횟수 감소: 코드는 주요 루프 내에서 조건 검사 횟수를 최소화하도록 설계되어 있으며 그래프를 효율적으로 탐색합니다.

 

5. 이미 방문한 노드에 대한 조기 종료: 코드는 노드를 큐에 추가하기 전에 이미 방문되었는지 여부를 확인합니다. 이는 불필요한 작업을 줄일 수 있고 효율성을 향상시킬 수 있습니다.

 

실제로 코드의 성능은 여러 가지 요인에 영향을 받을 수 있으며, 구현의 작은 변경이 때로는 눈에 띄는 성능 향상을 가져올 수 있습니다. 특정 문제와 작업하는 데이터 집합의 특성을 고려하는 것이 좋습니다.

 

chatGPT로 분석한 성능상 차이가 발생하는 이유로 LinkedList와 Deque 인터페이스의 구현체 ArrayDeque 간 차이 또한 지적 받아 이를 탐구할 필요를 느꼈다.

 

	LinkedList	ArrayDeque
접근 시간	O(n)	O(1) 특정 인덱스로 이동 가능
삽입 및 삭제 시간	O(1)	양쪽 : O(1) / 중간 : O(n)
메모리 사용	각 노드에 다음/이전 노드에 대한 참조로 메모리 사용이 상대적으로 많음	배열 기반으로 메모리 사용이 효율적
적합 사용 사례	리스트 중간 삽입/삭제가 자주 발생하고, 메모리 사용량이 크게 문제되지 않을 때	양쪽 끝에서 빈번한 삽입/삭제가 필요하거나 덱 구조 특성이 필요할 때