백준 21772번 가희의 고구마 먹방 C++

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

21772번: 가희의 고구마 먹방

 

백트래킹 + bfs 를 이용해서 해결하였다. 이미 방문했던 곳이라도 다시 방문하는게 핵심인 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int r, c, t;
int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };
int ans = 0;

vector<vector<int>> board;

void BT(int row, int col, int moveCnt, int eatSp) {
    if (moveCnt >= t) {
        ans = max(ans, eatSp);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nextRow = row + dRow[i];
        int nextCol = col + dCol[i];
        if (nextRow < 0 || nextRow >= r) continue;
        if (nextCol < 0 || nextCol >= c) continue;
        if (board[nextRow][nextCol] == '#') continue;
        if (board[nextRow][nextCol] == 'S') {
            board[nextRow][nextCol] = '.';
            BT(nextRow, nextCol, moveCnt + 1, eatSp + 1);
            board[nextRow][nextCol] = 'S';
        }
        else {
            BT(nextRow, nextCol, moveCnt + 1, eatSp);
        }
    }
}

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

    cin >> r >> c >> t;
    int startRow = -1;
    int startCol = -1;
    board = vector<vector<int>>(r, vector<int>(c));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            char ch;
            cin >> ch;
            board[i][j] = ch;
            if (board[i][j] == 'G') {
                startRow = i;
                startCol = j;
            }
        }
    }
    BT(startRow, startCol, 0, 0);
    cout << ans;
}