[백준] 21772 : 가희의 고구마 먹방

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

21772번: 가희의 고구마 먹방

---

• 처음에는 bfs 로 풀려고 했는데, 그렇게 될 경우 방문 여부를 두어 제약이 걸릴 경우 경로가 제대로 검사되지 않는다는 점과, 방문 체크를 하지 않을 경우에는 같은 위치를 여러번 방문하여 고구마를 여러번 먹는다는 위험이 있었다.
• 두번째로는 재귀적으로 백트래킹을 통해 방문 지점을 검사하면서 가능한 모든 경로에 대해서 고구마를 먹는 식으로 했는데, 이 경우에는 장애물이나 벽으로 인해 움직일 공간이 없는 경우가 있어 방문했던 지점을 되돌아가야 하는 경우를 고려하지 못한다.
• 따라서 방문 여부를 백트래킹으로 관리하는 것이 아닌, 진짜로 고구마를 먹었다 뱉었다 하는 식으로 모든 경로를 검사해준다.
• 어차피 4방향에 대해서 T 가 최대 10 이니 간단히 생각했을 때 4^10 이므로 연산량은 충분하다.

---

#include <iostream>

using namespace std;

int R, C, T, answer;
int map[100][100];
int dir[4] = {1, -1, 0, 0};     // 4방향 정보

void bt(int r, int c, int score, int depth)         // dfs 로 경로 검사 + 백트래킹으로 고구마 관리
{
    if(depth == T)                                  // 가능한 거리 다 움직여봤을 때 최대값 갱신
    {
        if(score > answer) answer = score;
        return;
    }
    for(int i = 0 ; i < 4 ; i++)                    // 현재 위치에서 4방향으로 또 한칸 움직임
    {
        int nr = r + dir[i];
        int nc = c + dir[3-i];
        if(nr>=0 && nr < R && nc >= 0 && nc < C && map[nr][nc] != -1)
        {
            bool tmp = false;
            if(map[nr][nc] == 1)                    // 고구마 위치면 먹어치우고
            {
                map[nr][nc] = 0;
                tmp = true;
            }
            bt(nr, nc, score + tmp, depth+1);       // 다음 칸으로 또 움직임
            if(tmp) map[nr][nc] = 1;                // 고구마가 있던 자리라면 되돌려놓음
        }
    }
}

int main(void)
{
    cin >> R >> C >> T;

    char tmp;
    int sr, sc;
    for(int r = 0 ; r < R ; r++)
    {
        for(int c = 0 ; c < C ; c++)
        {
            cin >> tmp;
            if(tmp == 'G') sr=r, sc=c;              // 시작점 지정, 빈칸은 기본 0
            else if(tmp == 'S') map[r][c] = 1;      // 고구마는 1
            else if(tmp == '#') map[r][c] = -1;     // 장애물은 -1
        }
    }
    
    bt(sr, sc, 0, 0);
    cout << answer << endl;
}