[백준 3109번] 빵집 - java

문제 설명

1. R*C 격자가 주어지고, '.'은 갈 수 있는 길 'X' 는 갈 수 없는길(건물) 이다.

2. 왼쪽 끝에서부터 시작해서 오른쪽 끝으로 연결이 가능하면 파이프가 이어지는것.

3. 하나의 시작점에서는 하나만 도달한다.

4. 이미 연결되면 그 다음에는 연결되지 않는다.

5. 그래서 도달한게 몇개인지 맞추면 된다.

 

풀이 과정

 1. DFS, 그리디이다.

 2. 백트래킹도 가능할 것 같기는 한데... 나는 DFS로 풀었고 그 이유는

 3. 위에서부터 아래로 가면서, 그리고 위로 가면서 확인하면 결국 갈 수 있는 길 자체가 정해진다.(그리디의 일종?)

 4. 즉, 위에서부터 확인하고 올라가기 - 직선 - 내려가기 할 때에 위에서 이미 갔으면 그거 자체가 하나의 루트가 된다. 즉 아래에서 이거때문에 못간다고 해도 달라질게 없다.

 5. 그래서 위에서부터 내려가면서 DFS + 그리디 하면 쉽게 풀 수 있는 문제이다.

 

코드

 

import java.util.*;

public class Main {
    private static int[] xMove = {1, 1, 1};
    private static int[] yMove = {-1, 0, 1};
    
    private static boolean map[][]; 
    private static int ans = 0;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int R = sc.nextInt();
        int C = sc.nextInt();
        sc.nextLine(); // 개행을 위해 넣는다.
        
        map = new boolean[R][C];
        
        // 간단하게 장애물 유무를 true/false로 넣는다.
        // true면 뭔가 장애물이 있는겨.
        for(int i=0; i<R; i++) {
          String input = sc.nextLine();
          for(int j=0; j<C; j++) {
            char index = input.charAt(j);
            if (index == '.') {
              map[i][j] = false;
            } else {
              map[i][j] = true;
            }
          }
        }
        
        // 위에서부터 DFS 시작
        for(int i=0; i<R; i++) {
          dfs(0, i);
        }
        
        System.out.println(ans);
    }
    
    private static boolean dfs(int x, int y) {
      for (int i=0; i<3; i++) {
        int xTo = x + xMove[i]; // 얘는 어차피 앞으로만 간다.
        int yTo = y + yMove[i]; // 지금보다 위/직선/아래로 이동한다.
        	// 박스 내에서 움직이기
    		if(xTo<0 || xTo>=map[0].length || yTo<0 || yTo>=map.length) continue;
    		
            // 그래서 그쪽으로 갔을 때에
            // 장애물이 없는 길이라면
    		if(!map[yTo][xTo]) {
              // 이게 목적지라면?
    		  if(xTo == map[0].length - 1) {
    		    ans++; // 답이고
    		    return true; // 이 길이 정답이라고 하고, 더이상의 DFS는 없다.
    		  }
    		  
              // 이길은 지나감(즉 장애물이 된다.)
              // 참고로 이거 다 해줘도 되는 이유는 어차피 여기서 못가면 다른곳에서도 못가기 떄문
              // 여기서 가면 다른곳에서 못가기도 하고
    		  map[yTo][xTo] = true;
    		  if(dfs(xTo, yTo)) return true; // DFS결과 정답이면 정답 루트 색칠
    		}
      }
  		
  		return false;
    }
}