[BOJ][Java] 백준 3109번: 빵집

1일 1PS 24일차! ㄴ

📚 문제

---

골드 2

• dfs 문제
• 왼쪽 위에서부터 출발해 최대한 위쪽으로 이동하면서 오른쪽으로 가면 된다.
• 이때 이미 이동한 블럭은 밟을 수 없고 이전 사람이 갔다가 실패한 블럭도 굳이 갈 필요가 없다. 따라서 이동하면서 밟은 블록은 무조건 체크한다.
• Stack 을 활용해 가장 우선순위로 두고 싶은 것을 마지막에 push 한다.
• Stack 은 출발때마다 초기화해야한다.

💡 포인트

---

1. 0부터 R-1 까지 루프를 돌면서 출발한다.
2. 출발하면서 아래 대각선, 오른쪽, 위 대각선으로 이동이 가능할 때 해당 순서 그대로 push 한다.
3. 가장 마지막에 push 된 순서대로 C-1 번째에 도착하면 카운팅하며 즉시 break 하고 stack 을 초기화한다.

💻 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

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

        char[][] map = new char[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        Stack<int[]> stack;
        int result = 0;
        for (int i = 0; i < R; i++) {
           stack = new Stack<>();
           int[] temp = {i, 0};
           stack.push(temp);

           while(!stack.isEmpty()){
               int[] loc = stack.pop();
               int[] temp2;
               map[loc[0]][loc[1]] = 'O';

               if (loc[1] == C - 1){
                   result += 1;
                   break;
               }

               if (loc[0] < R - 1 && map[loc[0] + 1][loc[1] + 1] == '.'){
                   temp2 = new int[]{loc[0] + 1, loc[1] + 1};
                   stack.push(temp2);
               }
               if (map[loc[0]][loc[1] + 1] == '.'){
                   temp2 = new int[]{loc[0], loc[1] + 1};
                   stack.push(temp2);
               }
               if (loc[0] > 0 && map[loc[0] - 1][loc[1] + 1] == '.'){
                   temp2 = new int[]{loc[0] - 1, loc[1] + 1};
                   stack.push(temp2);
               }
           }
        }
        System.out.println(result);
    }
}