[백준] 3109번 빵집 C++ 코드

코드

#include <iostream>
#include <cstring>

using namespace std;

int r, c;
char a[10003][503];
bool visited[10003][503];

// DFS를 이용하여 파이프 경로 찾기
bool go(int row, int col) {
    // 범위를 벗어나거나, 건물('x')일 경우 탐색 불가
    if (row < 0 || row >= r || a[row][col] == 'x') return false;

    // 이미 방문한 경우 탐색 불가
    if (visited[row][col]) return false;

    // 현재 칸을 방문했다고 표시
    visited[row][col] = true;

    // 마지막 열에 도달하면 성공적으로 파이프를 설치한 것
    if (col == c - 1) return true;

    // 우상향 -> 오른쪽 -> 우하향 순으로 경로 탐색
    if (go(row - 1, col + 1)) return true; // 우상향
    if (go(row, col + 1)) return true;     // 오른쪽
    if (go(row + 1, col + 1)) return true; // 우하향

    // 어떤 방향도 성공하지 못하면 false 반환
    return false;
}

int main() {
    cin >> r >> c;

    // 격자 입력
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> a[i][j];
        }
    }

    // 방문 배열 초기화
    memset(visited, false, sizeof(visited));

    int result = 0;

    // 첫 번째 열의 각 행에서 출발
    for (int i = 0; i < r; i++) {
        // 각 행에서 파이프 설치가 성공하면 카운트 증가
        if (go(i, 0)) {
            result++;
        }
    }

    // 설치 가능한 최대 파이프 개수 출력
    cout << result << '\n';

    return 0;
}

풀이

이 문제, 처음에는 dp로 접근했었다. 진행방향이 정해져있고 사이클이 없다는 것이 확실하기 때문이다. 그런데, 내가 접근한 dp로는 해결할 수 없다는 것을 깨달았다. 내 설계는 왼쪽에서 오른쪽으로 갈 수 있는 경로의 수를 찾는 코드라면, 해당 문제는 겹치지 않는 최대 경로의 수를 찾아야했기 때문이다. 그래서 한 번 설치하면 다시 방문할 수 없다는 조건을 고려해야 했다.

그리고 최대한 많이 설치해야하기 때문에, 오른쪽 위 -> 오른쪽 -> 오른쪽 아래 순서로 탐색해야 한다. 즉 경로 우선순위를 두는 그리디적 접근이 필요하다. 먼저 상단 경로를 확보한 뒤 아래쪽 경로를 탐색해야 다른 경로와의 충돌을 방지하고, 최대한 많은 경로를 설치할 수 있기 때문이다.