[Algorithm]Baekjoon 21772번 : 가희의 고구마 먹방

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
int r, c, t, sy, sx;
char arr[101][101] = { 0 };
int dirs[5][2] = { {0,0}, {-1,0}, {1,0}, {0,-1}, {0,1} };
int answer = 0;
 
void DFS(int y, int x, int time, int eatenSweetPotatoCount)
{
    if (time == t)
    {
        answer = max(answer, eatenSweetPotatoCount);
        return;
    }
 
    for (int i = 0; i < 5; ++i)
    {
        int nextY = y + dirs[i][0];
        int nextX = x + dirs[i][1];
 
        if (nextY < 0 || nextY == r) continue;
        if (nextX < 0 || nextX == c) continue;
        if (arr[nextY][nextX] == '#') continue;
 
        if (arr[nextY][nextX] == 'S')
        {
            arr[nextY][nextX] = '.'; // 먹었단 표시
            DFS(nextY, nextX, time + 1, eatenSweetPotatoCount + 1);
            arr[nextY][nextX] = 'S'; // 다시 원상복귀. 다른 방향으로의 탐색에서 먹어야하니까
        }
        else
        {
            DFS(nextY, nextX, time + 1, eatenSweetPotatoCount);
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> r >> c >> t;
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> arr[i][j];
 
            if (arr[i][j] == 'G')
            {
                arr[i][j] = '.';
                sy = i;
                sx = j;
            }
        }
    }
 
    DFS(sy, sx, 0, 0);
    cout << answer;
}
 
 

 

진짜 알고리즘 너무 오랜만에 풀어서 그런가... DP식으로 풀었다가 시간을 좀 오래썼다.

왜 안되나 고민하다가 문제 테스트케이스1번에서 T값을 늘린다음 실행해봤더니 고구마를 과도하게 먹었었다.

생각해보니 같은 노드에 재방문은 되게는 했는데, 문제는 고구마를 먹은곳에서 또 먹는 로직이 수행되게 코드를 짰었다..