문제

풀이 과정

완전 탐색 문제, DFS() 를 통해, 출발점 부터 T 만큼 갈 수 있는 모든 경로를 탐색한다. 80% 에서 에러가 났는데, 갔던 자리를 다시 되돌아왔을 때 최대 고구마가 나올 수도 있는 경우였다.

5 5 12
. . s . .
. . s . .
s s g s s
. . s . .
. . s . .

그냥 방문처리 하지말고 한번더 탐색해주면 된다.

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int R, C, T;
    static int[] pos;
    static char[][] map;
    static final int[] DR = new int[]{-1, 0, 1, 0};
    static final int[] DC = new int[]{0, -1, 0, 1};

    static int ans = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        for (int i = 0; i < R; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                map[i][j] = temp[j];
                if (map[i][j] == 'G') pos = new int[]{i, j};
            }
        }

        DFS(pos[0], pos[1], 0, 0);
        System.out.println(ans);
    }

    private static void DFS(int r, int c, int dist, int eat) {
        if (dist >= T) {
            ans = Math.max(eat, ans);
            return;
        }

        for (int d = 0; d < 4; d++) {
            int nr = r + DR[d];
            int nc = c + DC[d];

            if (!check(nr, nc)) continue;
            if (map[nr][nc] == '#') continue;
            if (map[nr][nc] == 'S') {
                map[nr][nc] = '.';
                DFS(nr, nc, dist + 1, eat + 1);
                map[nr][nc] = 'S';
            } else {
	              DFS(nr, nc, dist + 1, eat);
						}
        }
    }

    private static boolean check(int r, int c) {
        if (r < 0 || r >= R || c < 0 || c >= C) return false;
        return true;
    }
}