99클럽 코테 스터디 Java 5일차 TIL - 알고리즘 수업 - 너비 우선 탐색 1 : 백준 24444번 - BFS

1. 오늘의 문제 - 알고리즘 수업 - 너비 우선 탐색 1 - 백준 : 24444번

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

 

 

이름부터가 BFS로 풀라고 떠먹여준다.

BFS는 참 좋다.

공식만 알고 있으면 되니까.

문제에서 친절하게 공식도 알려준다.

2. 문제 풀이 전략

2 - 1. 인접리스트로 접근

정점수가 100,000 개이므로, 인접행렬로 그래프를 표현하면 메모리초과가 발생할 것이다.

인접리스트로 그래프를 표현하자.

// static int[][] adjMatrix;  // 인접 행렬 안됩니다!
static List<List<Integer>> adjList;

 

2 - 2. 정렬

예시의 입력을 살펴보면, 1번 정점과 4번 정점이 연결 되고, 1번 정점과 2번 정점이 연결 된다.

결과적으로, 1번 정점과 연결된 정점들은 [4, 2] 가 되는 것이다.

문제에서 요구한 것이 "오름차순" 이므로 정렬 해준다.

 

2 - 3. 양방향 그래프 체크해주기

양방향 그래프이므로 1번 정점과 4번 정점이 연결되었다는 입력을 받으면, 4번 정점과 1번 정점도 연결 되었음을 표현해줘야 한다.

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    adjList.get(a).add(b);
    adjList.get(b).add(a);             // 양방향 그래프 표현해주기!
}

 

2 - 4. 방문 순서 변수 사용하기

방문 순서를 담고 있는 변수가 필요하다

static int orderCount = 1;

 

2 - 5. Queue 자료구조는 Deque을 사용하는 게 좋다. (Stack 도 마찬가지)

BFS는 Queue 자료구조를 사용해야 한다.

나는 Queue를 사용할 때는 항상 Deque을 사용한다.

사실, Queue 뿐만 아니라 Stack을 사용할 때도 Deque을 쓴다.

Deque은 양쪽으로 넣고 뺄 수 있는 자료구조라서 Queue로 사용해도 되고, Stack으로 사용해도 된다.

단순히, 간편해서 사용하는 것이 아니라, 성능 차원에서 더욱 효율이 좋다.

 

현재, 나는 Sonarlint 라는 정적 코드 분석 도구를 사용중인데, 코드를 작성하면 문제가 될 수 있는 부분에서 경고를 해준다.

여기서, Stack 이나 Queue를 선언하면 Deque으로 바꾸라고 알려준다.

Stack 이랑 Queue가 옛 버전에서 만들어진 자료구조라 동기적으로 실행되어서 Deque을 쓰라고 알고 있는데,

자세한 건 chat GPT, 구글링해서 알아보자.

아래에 자세히 정리해 둔 블로그 글이 있다.

https://vanslog.io/posts/language/java/why-use-deque-instead-of-stack/

[Java] 왜 Stack 대신 Deque를 사용하는가? | Vanslog

 

Deque 을 사용하는 방식은 아래처럼 사용하면 된다.

// Queue 로 사용하기
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);  // 큐에 요소 추가
queue.add(2);   // 큐에 요소 추가
int front = queue.poll();  // 큐의 맨 앞 요소 제거 및 반환
int peek = queue.peek();  // 큐의 맨 앞 요소 조회 (제거하지 않음)


// Stack 으로 사용하기
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);  // 스택에 요소 추가
int top = stack.pop();  // 스택의 맨 위 요소 제거 및 반환
int peek = stack.peek();  // 스택의 맨 위 요소 조회 (제거하지 않음)

 

2 - 6. BFS 로직

문제에서 친절하게 알려줬으니, 고대로 작성하면 된다!

while (!queue.isEmpty()) {
    int cur = queue.poll();
    for (int x : adjList.get(cur)) {
        if (ch[x] == 0) {
            ch[x] = orderCount++;
            queue.add(x);
        }
    }
}

 

3. 풀이

package io.conduktor.demos.dfsbfs.hanghaecote99.middler;

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

// 5. 알고리즘 수업 - 너비 우선 탐색 1 - 백준 : 24444
public class Bfs5 {

    static int N;
    static int M;
    static int start;
    static List<List<Integer>> adjList;
    static int[] ch;
    static int orderCount = 1;

    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());
        start = Integer.parseInt(st.nextToken());

        adjList = new ArrayList<>();
        for (int i = 0; i <=N; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adjList.get(a).add(b);
            adjList.get(b).add(a);
        }
        for (int i = 1; i < N; i++) {
            Collections.sort(adjList.get(i));
        }
        ch = new int[N + 1];
        Deque<Integer> queue = new ArrayDeque<>();
        ch[start] = orderCount++;
        queue.add(start);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int x : adjList.get(cur)) {
                if (ch[x] == 0) {
                    ch[x] = orderCount++;
                    queue.add(x);
                }
            }
        }

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

        bw.write(sb.toString());

        bw.flush();
        bw.close();
        br.close();
    }
}

 

4. 소감

BFS는 공식만 알고 있으면 간단하게 해결되는 게 많다.

BFS. 고마운 존재.