백준 3109 빵집

1. 문제에 대하여 📦

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

(1) 조건 분석 📊

첫 번째 열부터 시작해서 마지막 열까지 이을 수 있는 경로의 개수를 구하라.
경로를 잇는 파이프라인은 /, -, \ (대각선 상단, 일자 가로, 대각선 하단)으로 밖에 못한다.

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

KEY WORD: 그리디 알고리즘, 백트래킹, 정렬

빵집 가스관에서의 출발지는 되도록 맨 위에서 출발해서 도착지 또한 되도록 상단에 있는 곳으로 도착하려 해야 한다. 이유는 다음과 같다.

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

위의 2가지 때문에 해당 문제는 그리디 알고리즘으로 푸는 문제이다. 최대한 상단으로 가보고 안되면, 나머지 경로를 탐색한다. 또한 다음 경로가 되는지 안되는지 확인하기 때문에 백트래킹이라고도 볼 수 있다.

(1) 중복 탐색 방지

목적지 도달 실패 경로이든 성공 경로이든 방문 흔적을 남겨 다음 출발지에서 동일한 위치로 가지 못하게 한다.

1. 이전 경로가 실패한 경로라면, 실패한 루트를 그대로 따라가는 계산 시간 낭비를 줄인다.
2. 이전 경로가 성공한 경로라면, 중복된 경로 탐색 시간 낭비를 줄인다.

(2) 시간복잡도 분석 ⏳

만약 해당 문제를 완전탐색으로 풀었다면, 좌표 하나당 선택지가 3개이므로, $3^{(R \times C)}$ 번이다. R이 최대 $10,000$개, C가 최대 $500$ 개이므로 시간초과가 된다. 하지만 위의 그리디 알고리즘 + 백트래킹으로 문제를 풀면, 중복 탐색 시간을 줄이므로 시간적 이득을 볼 수 있다.

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