자바(백준) 21772 가희의 고구마 먹방

오답 노트 & 새로 알게 된 점

해당 문제는 약 2, 3일 고민하면서 풀었던 것 같다. 물론 혼자 힘으로 풀지 못하고, 오카방에 여쭤봐서 힌트를 얻고, 문제를 해결했다. 처음 문제 접근은 bfs, dfs에서 고민을 당연하게도 했다. bfs를 진행하다가 뭔가 아닌 것 같아서 dfs를 사용했다. 그래서 처음에는 dfs를 들어갈 때마다 새로운 visit배열을 만들고(왜냐하면 먹었던 고구마를 또 먹을 수 없기 때문) 이상하게 코드를 짰다.

 

도대체 어떻게 하면 먹었던 고구마를 다시 먹지 않으면서 그 길을 지나갈 수 있을까? 라는 생각을 했다. 

나는 항상 백트레킹이나 dfs를 풀면 무조건 visit 했으면 continue 하고 봐 이런 식이였다. 그러나 이 문제를 통해 틀에 박힌 생각을 깼다. 이 문제에서는 visit를 continue 하게 되는 순간 풀리지 않았다.

 

가희가 고구마를 먹고 나서 다른 길로 갔다가 고구마를 다시 먹은 길로 돌아올 수 있기 때문이다.

 

그래서 해결점은 벽만 아니면 넘어갈 수 있고, 고구마가 있을 경우 최초 방문 시에만 고구마의 개수를 늘려준다.

 

즉, 범위는 총 4가지로 나눌 수 있다.

 

• 재방문일 경우
  • 고구마 : depth + 1
  • .        : depth + 1
• 최초 방문일 경우
  • 고구마 : depth + 1, count + 1
  • .         : depth + 1

 

물론 범위를 지정하기 전에 벽은 절대 못 지나가기 때문에 #일 경우에는 continue를 해준다. 그래서 재방문일 경우에는 하나의 if문으로 해결하고, 최초 방문일 경우에는. 와 S에 따라 if else if로 해주면 된다. 

그리고 또 하나 중요한 점은 고구마를 먹었을 경우 dfs가 끝나게 되면 방문했던 곳을 false 시켜주어야 한다.

---

코드

package BackTracking;
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int row, col, time;
    static char arr[][];
    static boolean visit[][];
    static int result = 0;
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,1,-1};
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        time = Integer.parseInt(st.nextToken());
        DPoint dp = null;
        arr = new char[row][col];
        visit = new boolean[row][col];
 
 
        for(int i = 0; i < row; i++){
            String str = br.readLine();
            for(int j = 0; j < col; j++){
                arr[i][j] = str.charAt(j);
                if(arr[i][j] == 'G'){
                    dp = new DPoint(i, j, 0);
                    //강아지가 있는 좌표 찍기
               }
            }
        }
 
        dfs(dp, 0);
        System.out.println(result);
    }
    static void dfs(DPoint dp, int count){
        if(dp.depth == time ){
            result = Math.max(result, count);
            return;
        }
        int x = dp.x;
        int y = dp.y;
        visit[x][y] = true;
        for(int i = 0; i < 4; i++){
            //1. visit가 true라 해도 벽만 아니면 그냥 지나갈 수 있다.
            //2. visit가 방문이어도 벽만 아니면 다시 재귀로
            //3. 최초방문일 때만 count + 1
            //4. 한번 방문했던 곳은 시간만 늘려준다.
            int X = x + dx[i];
            int Y = y + dy[i];
            if(!isRangeTrue(X, Y)) continue;
            //장애물만 아니면 지나갈 수 있다.
 
            if(arr[X][Y] == '#') continue;
 
            //방문을 했을 경우에는 지나는 갈 수 있다. 그래서 depth + 1만 --> 2번 해결
            //방문을 했을 경우에는 S든 G든 . 든 상관 X --> 2번, 4번
 
            if(visit[X][Y]){
                dfs(new DPoint(X, Y, dp.depth + 1), count);
            }
            //방문하지 않았을 경우
            //S이면 count + 1을 해주어야함
            //.이나 G면 방문표시하고 depth + 1
            
            else{
                if(arr[X][Y] == 'S'){
                    //최초방문일 떄만 count + 1 ---> 3번 해결
                    dfs(new DPoint(X, Y, dp.depth + 1), count + 1);
                    visit[X][Y] = false;
                }
                else{
                    dfs(new DPoint(X, Y, dp.depth + 1), count);
                }
            }
 
        }
    }
    static boolean isRangeTrue(int x, int y){
        return x >= 0 && x < row && y >= 0 && y < col;
    }
}
class DPoint{
    int x, y, depth;
    DPoint(int x, int y, int depth){
        this.x = x;
        this.y = y;
        this.depth = depth;
    }
}