[백준] 31575번 도시와 비트코인 : BFS vs DP(동적계획법) 어떤 게 더 빠를까?

 

 

문제

 

전날에 비해 비트코인의 시세가 백만원이나 오른 어느 아침, 진우는 거래소에 가서 비트코인을 매도하려고한다.

현재 비트코인의 시세가 점점 떨어지고 있기 때문에 진우는 최대한 빨리 거래소에 가야 한다.

 

도시는 가로 N, 세로 M 크기의 격자 모양으로 이루어졌다. 진우는 북서쪽 끝에 있고 거래소는 남동쪽 끝에 있다.

도시의 일부 구역은 공터 또는 도로라서 진우가 지나갈 수 있지만, 어떤 구역은 건물이 있어서 진우가 갈 수 없다.

 

진우는 최대한 빨리 거래소에 가야 하므로, 동쪽(오른쪽) 또는 남쪽(아래쪽)으로만 이동하여 거래소로 도착할 수 있어야 한다.

진우를 도와 거래소로 갈 수 있는지 구하는 프로그램을 작성 하여라.

 

출처 : https://www.acmicpc.net/problem/31575

 

[그림1] 비트코인 팔려고 뛰는 진우

 

 

문제 핵심 요약

 

• 격자 크기 : N x M (최대 300 x 300)
• 이동 방향 : 동쪽(오른쪽), 남쪽(아래쪽) 으로만 이동
• 목표 : 시작점 (0,0)에서 끝점 (M-1, N-1)까지 갈 수 있는가

 

 

 

 

방법 1) BFS (너비 우선 탐색)

 

BFS는 마치 길치인 제가 구글 지도를 켜고 모든 골목길을 하나씩 다 가보는 것과 같습니다.

큐 (Queue)를 이용해서 현재 위치에서 갈 수 있는 다음 칸을 탐색하는 방법이죠.

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]); // 가로(열)
        int M = Integer.parseInt(input[1]); // 세로(행)

        int[][] map = new int[M][N];
        boolean[][] isVisited = new boolean[M][N];

        for(int i = 0; i < M; i++) {
            String[] row = br.readLine().split(" ");
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(row[j]);
            }
        }

        // 큐에는 {행, 열} 좌표를 저장
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        isVisited[0][0] = true;

        // 이동 방향: 남, 동
        int[] dr = {1, 0};
        int[] dc = {0, 1};

        boolean canFinish = false;
        while(!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

            if(r == M - 1 && c == N - 1) {
                canFinish = true;
                break;
            }

            for(int i = 0; i < 2; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if(nr >= 0 && nr < M && nc >= 0 && nc < N 
                   && !isVisited[nr][nc] && map[nr][nc] == 1) {
                    isVisited[nr][nc] = true;
                    queue.offer(new int[] {nr, nc});
                }
            }
        }
        System.out.println(canFinish ? "Yes" : "No");
    }
}

• 특징 : "상하좌우" 어디로든 갈 수 있는 일반적인 미로 찾기에 최적화되어 있습니다.
• 단점 : 이 문제처럼 이동 방향이 제한적일 때는 큐에 좌표 객체를 넣고 빼는 과정이 불필요한 메모리와 시간을 잡아먹을 수 있습니다.

 

 

 

 

 

방법 2) DP (동적 계획법)

 

이동 방향이 오른쪽과 아래로만 딱 정해져 있다면? 굳이 큐를 쓸 필요가 없습니다.

"내가 이 칸에 오려면, 위쪽 칸이나 왼쪽 칸에서 왔겠지?" 라는 생각으로 한 칸씩 채워나가는 방식입니다. 

마치 테트리스 블록을 쌓는 것 같죠!

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        int[][] map = new int[M][N];
        for (int i = 0; i < M; i++) {
            String[] row = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(row[j]);
            }
        }

        // 도달 가능 여부 저장 배열
        boolean[][] dp = new boolean[M][N];
        dp[0][0] = true; // 시작점은 무조건 가능!

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                // 현재 칸이 길(1)이 아니면 지나갈 수 없음
                if (map[i][j] == 0) continue;

                // 1. 위쪽 칸에서 올 수 있는가?
                if (i > 0 && dp[i - 1][j]) dp[i][j] = true;
                
                // 2. 왼쪽 칸에서 올 수 있는가?
                if (j > 0 && dp[i][j - 1]) dp[i][j] = true;
            }
        }
        System.out.println(dp[M - 1][N - 1] ? "Yes" : "No");
    }
}

 

• 특징 : 단순 배열 연산이라 속도가 광속입니다. (비트코인 떡락 속도만큼이나 빠름!)
• 단점 : 오직 한 방향으로만 전진할 수 있는(순환이 없는) 구조에서만 사용 가능합니다.

 

 

 

 

 

한눈에 정리 해보기

 

비교 항목	BFS (탐색형)	DP (축적형)
속도	보통 (객체 생성 비용 발생)	매우 빠름 (단순 반복문)
메모리	Queue와 방문 배열 사용	DP 배열 하나로 끝!
생각의 난이도	기본 알고리즘만 알고있으면 쉬움	꼬아서 내면 어려울 것
추천 상황	4방향 이동 / 최단 거리 계산	방향이 제한적 / 도달 여부만 체크할 때

 

마무리하며...

단순히 "도착할 수 있니?"라고 묻는 문제에서는 DP가 훨씬 효율적이지만, 길 찾기의 기본기를 익히기에는 BFS가 아주 좋은 연습이 됩니다. 비트코인 시세는 예측할 수 없어도, 알고리즘 정답은 예측할 수 있습니다!

 

 

 

감사합니다.