백준 3109 빵집 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/3109

(1) 조건 분석 📊

2. 코드가 나오기까지 🛠️

1. 최대한 상단에 있는 것을 골라줘야 추후 가스관 출발지에서 갈 수 있는 도착지의 범위가 넓어진다.

2. 도착지의 범위가 넓어질수록 더 많은 경로를 가질 수 있다.

(1) 중복 탐색 방지

1. 이전 경로가 실패한 경로라면, 실패한 루트를 그대로 따라가는 계산 시간 낭비를 줄인다.

2. 이전 경로가 성공한 경로라면, 중복된 경로 탐색 시간 낭비를 줄인다.

(2) 시간복잡도 분석 ⏳

3. 코드 🌐

(1) SUDO CODE 💬

// 간단한 의사 코드
	1. 입력 받기
  2. (0,0) 좌표부터 대각 상단, 가로 일자, 대각 하단 순으로 DFS
  3. 만약 경로를 발견했다면 계산을 멈추고 다음 좌표로 넘어간다.
  4. 경로를 발견하지 못했다면, 실패 경로를 최대한 찾아서 다음 계산 중복을 줄인다.

(2) JAVA CODE ☕

import java.util.*;
import java.io.*;
 // b 3109 빵집
public class Main {
    static int R,C;
    static char [][] map;
    static int [] dir = new int [] {-1,0,1};
    static int pipe = 1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        for(int i = 0; i < R; i++){
            String row = br.readLine();
            for (int j = 0; j < C; j++){
                map[i][j] = row.charAt(j);
            }        }        int answer = 0;
        for(int i = 0; i < R; i++){
            if(dfs(i,0)) answer++;
        }

        System.out.println(answer);
    }    public static boolean dfs(int r, int c){
        // 기저 조건
        if(c == C-1) {
            map[r][c] = 'H';
            pipe++;
            return true;
        }
        for (int i = 0; i < 3; i++) {
            int nr = r + dir[i];
            int nc = c + 1;
            if(OOB(nr,nc)) continue;
            if(map[nr][nc] != '.') continue;
            map[r][c] = (char) (pipe+'0');
            if(dfs(nr,nc)) return true;
        }        return false;
    }
    public static boolean OOB(int r, int c){
        return r < 0 || c < 0 || r >= R || c >= C;
    }
}

4. 트러블 슈팅 or 배운 점📝

4%에서 틀리면 해봐야할 반례

15 15
.xxxxxxxxxx....
...x.......xxx.
...x.......x...
..xx.......xx..
...x........xx.
.x.x......x.x..
...x......xx...
.x.x....xxx....
.x....x.x......
.x.....xx.x....
.x..x.xx.......
.....xx........
....x..........
......x........
...............
---
// 답: 4