3109번 : 빵집 [JAVA]

문제 링크

성공 여부(걸린 시간): 실패(15분)

아이디어 

처음에는 DP로 접근해서 점화식을 세워보았는데, 예제 입력에 대해서는 정답이 나오지만 조금만 변형된 반례가 나오면 깨지는 허술한 풀이였다.
즉, 이 문제는 단순히 경우의 수를 세는 DP 문제가 아니라, 실제로 파이프를 설치할 수 있는 경로의 최대 개수를 찾는 탐색 문제라는 점을 깨달았다.

그래서 다른 방법을 고민하다가 힌트를 참고했는데, 정답 풀이 방식은 바로 DFS(깊이 우선 탐색) 이었다.

핵심 아이디어

1. 탐색 순서: 현재 위치에서 오른쪽으로 이동할 때,
   • 우상향(대각선 위 오른쪽)
   • 우측(바로 오른쪽)
   • 우하향(대각선 아래 오른쪽)
     순서대로 탐색한다.
     이렇게 하는 이유는, 위쪽 경로가 먼저 확보되면 아래쪽 경로에 영향을 덜 주고 더 많은 파이프라인을 설치할 수 있기 때문이다.
2. 방문 처리 방식:
   • 일반적인 DFS는 "방문했다 → 방문 처리"를 먼저 하지만, 여기서는 재귀 호출을 먼저 실행하고, 성공한 경우에만 방문 처리를 한다.
   • 즉, 도착점(y == C-1)까지 연결되면 그 경로를 확정 짓고 result++로 카운트한다.
   • 만약 성공하면, 그 순간 바로 return 해서 다른 불필요한 경로 탐색을 막는다.
3. 경로 차단:
   • 어떤 경로에서 실패했더라도 그 위치는 다른 경로에서 다시 사용할 수 없으므로 map[x][y] = 0 으로 막아준다.
   • 이렇게 해야 중복 탐색을 방지하고 시간 초과를 피할 수 있다.

• 전체 풀이 흐름
• 맵을 입력받아 '.'인 칸을 통로(1)로 저장한다.
• 각 행(0 ~ R-1)에서 출발해 DFS를 수행한다.
• DFS 과정에서 오른쪽 끝(y == C-1)에 도달하면 파이프 설치 성공 → result++.
• 최종적으로 모든 행을 시작점으로 탐색한 후, result를 출력한다.

풀이 코드

import java.io.*;
import java.util.*;

public class Main {
    static int R, C, result=0;
    static boolean success;
    static int [][] map;
    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());
        map = new int[R][C];
        for(int i=0; i<R; i++){
            String input = br.readLine();
            for(int j=0; j<C; j++){
                if(input.charAt(j)=='.'){
                    map[i][j] = 1;
                }
            }
        }
        for(int i=0; i<R; i++){
            success=false;
            DFS(i, 0);
        }
        System.out.print(result);
    }
    static int [] dx ={-1, 0, 1};
    static void DFS(int x, int y){
        if(y==C-1){//도달
            result++;
            map[x][y] = 0;
            success= true;
            return;
        }
        for(int i =0; i<3; i++){
            int mx = x+dx[i];
            int my = y+1;
            if(canGo(mx, my)&&map[mx][my]==1){
                DFS(mx, my);
                map[x][y] = 0;
                if(success){
                    return;
                }
            }
        }

    }
    static boolean canGo(int x, int y){
        return x>=0&&y>=0&&x<R&&y<C;
    }
}