백준 3109 빵집 (C++)

3109번: 빵집

dfs를 이용한 문제이다. 이 문제에서 중요한 부분은 다음으로 이동하는 좌표의 순서이다. 오른쪽, 오른쪽 대각 위, 오른쪽 대각 아래 3가지의 경우로 좌표를 이동하게 되는데 보통 반복문을 0부터 시작하기 때문에 시작이 첫째 열, 첫째 행이다. 그렇기에 도착 지점도 위에서부터 차례대로 접근하는 것이 가장 이상적이다. 그러므로 좌표의 이동을 나타내는 dy, dx를 오른쪽 대각 위, 오른쪽, 오른쪽 대각 아래 순으로 지정해주었다. 반복문을 돌면서 dfs를 돌게 되는데 x 좌표가 가장 오른쪽에 도달했을 경우 tf=true를 해주고 result++를 해준다. 이 후 tf=true이기 때문에 이전 dfs 내의 반복문은 모두 멈추게되고 이를 반복해주어 result를 구해주고 출력해주었다.
단순히 좌표 이동 순서에 의미를 두지 않고 dfs를 풀어왔었는데 이번 문제를 통해 순서의 중요성에 대해 인지할 수 있었다. 이 점을 잘 기억해두어야 겠다.

#include <iostream>

using namespace std;

int R, C, result = 0;
char A[10000][500];
int dy[3] = { -1,0,1 };
int dx[3] = { 1,1,1 };
bool check[10000][500], tf = false;

void dfs(int y, int x) {
    if (x == C - 1) {
        tf = true;
        result++;
        return;
    }

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

        if (tf) break;
        if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
        if (A[ny][nx] == 'x') continue;
        if (check[ny][nx]) continue;

        check[ny][nx] = true;
        dfs(ny, nx);
    }
}

void solution() {
    for (int i = 0; i < R; i++) {
        tf = false;
        dfs(i, 0);
    }

    cout << result;
}

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

    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}