[C++]백준(BOJ) 31575번 도시와 비트코인 문제풀이

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

---

문제

전날에 비해 비트코인의 시세가 백만원이나 오른 어느 아침, 진우는 거래소에 가서 비트코인을 매도하려고 한다. 현재 비트코인의 시세가 점점 떨어지고 있기 때문에 진우는 최대한 빨리 거래소에 가야 한다.

도시는 가로 N, 세로 M 크기의 격자 모양으로 이루어졌다. 진우는 북서쪽 끝에 있고 거래소는 남동쪽 끝에 있다. 도시의 일부 구역은 공터 또는 도로라서 진우가 지나갈 수 있지만, 어떤 구역은 건물이 있어서 진우가 갈 수 없다.

진우는 최대한 빨리 거래소에 가야 하므로, 동쪽(오른쪽) 또는 남쪽(아래쪽)으로만 이동하여 거래소로 도착할 수 있어야 한다. 진우를 도와 거래소로 갈 수 있는지 구하는 프로그램을 작성하여라. 진우의 현재 위치가 거래소일 수 있다.

---

입력

첫 번째 줄에 도시의 가로 크기 N과 세로 크기 M(1≤N,M≤300)이 주어진다.

두 번째 줄부터 M개의 줄에는 도시의 형태를 나타내는 N개의 정수가 공백을 사이에 두고 주어진다. 각 칸이 1인 경우 진우가 갈 수 있는 칸을 의미하고 0인 경우 진우가 갈 수 없는 칸을 의미한다.

왼쪽 위의 끝 칸과 오른쪽 아래의 끝 칸은 모두 1이다.

---

출력

첫 번째 줄에 진우가 거래소로 갈 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

---

예제 입력, 출력

---

알고리즘 분류

다이나믹 프로그래밍

그래프이론

그래프탐색

너비우선탐색

깊이우선탐색

---

해설

문제의 설명에 따르면 진우는 N * M 형태의 격자의 왼쪽 위 끝부터 오른쪽 아래 끝(비트코인 거래소)까지 이동해야 한다. 단 1이 써져있는 칸만 이동할 수 있고 0인 경우에는 이동할 수 없고, 매우 급하기 때문에 오른쪽, 혹은 아래쪽으로만 이동하여야 한다.

 

해당 문제를 해결하기 위해서는 BFS, 혹은 DFS를 사용하면 될 것으로 보인다.

C++ STL에서 제공하는 큐를 이용하여 BFS를 구현하여 문제를 해결하였다.

코드의 대략적인 로직은 다음과 같다.

 

1. 도시의 상태를 입력받아 map 2차원 배열에 저장

 

2. 왼쪽 위 끝(1, 1)부터 BFS를 수행하여 오른쪽 아래 끝(m, n)에 도달할 수 있는지 판단. 가능하면 cleared 플랙을 true로 바꿈

 

3. BFS 수행시 다음 정점(오른쪽, 아래쪽으로 이동한 정점)이 탐색 가능한지는 맵밖으로 나가지 않는지, 방문된적 없는지로, 갈 수 있는 길인지(0이 아니어야함) 로 판단

 

4. main함수로 돌아와 플랙에 따라 결과 출력

 

문제를 해결할 때 다음 사항을 

 

1. 오른쪽, 아래쪽 2방향으로만 이동이 가능하다는 점,

2. 가로 n 세로 m 크기를 입력받을 때, for문의 내부, 외부 둘중 어디에 배치해야 하는지,

3. 방문가능한 노드인지 판별하는 조건에서(이동한 좌표 nx, ny가 맵밖으로 나갔는지)

4. nx, ny를 n과 m 둘중 어느 것과 비교해야 하는지

 

정확히 판단하면서 문제를 해결하면 쉽게 맞을 수 있는 문제라고 생각한다.

---

소스코드

#include <iostream>
#include <queue>

#define SIZE 301
using namespace std;

int map[SIZE][SIZE];  // 지도의 상태 저장할 2차원 배열
bool visited[SIZE][SIZE]; // 해당 위치가 방문되었는지 여부를 저장하는 2차원 배열
int dx[2] = { 1, 0 }; // 오른쪽, 아래쪽 이동 정의
int dy[2] = { 0, 1 }; 
queue<pair<int, int>> q; // 좌표형태를 푸시 받을 수 있는 큐

int n, m; // n: 가로 크기, m: 세로 크기
bool cleared = false;

// 초기화 함수
void init() {
    for (int i = 1; i <= m; i++) { // 세로
        for (int j = 1; j <= n; j++) { // 가로
            map[i][j] = 0;
            visited[i][j] = false;
        }
    }
}

// x, y좌표부터 BFS를 수행하는 함수
void bfs(int x, int y) {
    q.push({ x, y }); // 큐에 시작점 푸시
    visited[x][y] = true; // 방문했음 표시
    while (!q.empty()) { // 큐가 빌때까지 반복
        x = q.front().first; // 현재 정점 업데이트
        y = q.front().second;
        q.pop();

        if (x == m && y == n) { // 만약 도착점이어도 종료
            cleared = true; // 클리어
            return;
        }

        // 오른쪽, 아래쪽 탐색
        for (int i = 0; i < 2; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 맵밖을 나가지 않는지, 방문된적 없는지, 갈 수 있는 길인지(0이 아닌지)
            if (nx <= m && ny <= n && !visited[nx][ny] && map[nx][ny] != 0) {
                q.push({ nx, ny }); // 만족한다면 큐에 푸시
                visited[nx][ny] = true; // 방문했음 표시
            }
        }
    }
}

int main() {
    cin >> n >> m; // 가로 크기(n), 세로 크기(m)

    init();
    for (int i = 1; i <= m; i++) { // 세로
        for (int j = 1; j <= n; j++) { // 가로
            cin >> map[i][j];
        }
    }

    bfs(1, 1); // 시작점부터 BFS 수행

    if (cleared) { 
        cout << "Yes";
    }
    else {
        cout << "No";
    }

    return 0;
}