[Algorithm] BOJ 3109 빵집

문제 링크

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

문제 풀이

첫번째 열에서 마지막 열까지 도달할 수 있는 루트가 몇개인지 묻는 문제이다.
이동방향은 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래로 제한되어있다.

최단거리를 구하는 문제가 아니라 루트의 갯수를 물어보는 문제이므로, 깊이 우선 탐색을 이용해서 끝까지 도달한 루트를 먼저 찾는 것이 유리할 것 같다고 생각해서 dfs 를 이용해서 구현하였다.

오른쪽 아래 부터 탐색을 시작해서 루트를 확정하면, 가능했던 아래쪽의 루트 형성을 방해할 수 있어서 가능한 루트의 조합을 모두 찾아서 가장 많이 도달할 수 있는 루트를 다시 봐야한다.

이를 방지하기 위해 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 (위에서 아래) 순서로 그리디하게 탐색을 진행하도록 하였다.

코드

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;


int n, m;
int answer = 0;
string map[10000];
int visited[10000][500];

// 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선
int dx[] = {-1, 0, 1};
int dy[] = {1, 1, 1};

int dfs(int x, int y) {

    visited[x][y] = 1;
    if (y == m-1) {
        answer++;
        return 1;
    }

    for (int i=0; i<3; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (visited[nx][ny] || map[nx][ny] == 'x') continue;
        
        if (dfs(nx, ny) return 1;
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for (int i=0; i<n; i++) {
            cin >> map[i];
    }
    memset(visited, 0, sizeof(visited));
    for (int i=0; i<n; i++) {
        dfs(i, 0);
    }
    cout << answer;

    return 0;
}