[백준 1189번] 컴백홈 - java

문제 설명

1. 첫째 줄에 맵의 크기랑 이동거리가 주어진다.

2. .은 갈수 있는 곳, T는 장애물로 주어진다.

3. 오른쪽 아래부터 시작해서 오른쪽 위까지 이동거리로 이동할 수 있는 경우의 수를 구한다.

4. 한번 지나간 길로는 못간다.

풀이 과정

 1. DFS 문제이다.

 2. 한번 지나갔거나, 장애물이 있는 곳은 true, 나머지는 false로 구한다.

 3. 현재 위치에서 DFS할 때에 이동할 곳을 이동처리하고 그 DFS끝나면 다시 이동 가능하게 하면 된다. (가게 되면 방문한거니까)

 

코드

/******************************************************************************

                            Online Java Compiler.
                Code, Compile, Run and Debug java program online.
Write your code in this editor and press "Run" button to execute it.

*******************************************************************************/
import java.util.*;

public class Main
{
  private static final int[] xMove = {0, 0, -1, 1};
  private static final int[] yMove = {-1, 1, 0, 0};
  private static boolean map[][];
  private static int ans = 0;
  private static int K;
  
	public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      String input = sc.nextLine();
      
      String[] strList = input.split(" ");
      int[] num = new int[strList.length];
      
      for(int i=0; i<strList.length; i++) {
        num[i] = Integer.parseInt(strList[i]);
      }
      
      K = num[2];
      map = new boolean[num[0]][num[1]];
      
      for(int i=0; i<num[0]; i++) {
        input = sc.nextLine();
        for(int j=0; j<num[1]; j++) {
          if (input.charAt(j) == 'T') {
            map[i][j] = true;
          }
        }
      }
      
      map[map.length-1][0] = true;
      dfs(map.length-1, 0, 1);
      System.out.println(ans);
  }
  
  private static void dfs(int x, int y, int move) {
    
    if (x == 0 && (y == map[0].length-1)) { 
      if (move == K) ans++;
      return;
    }
    
    for (int i=0; i<4; i++) {
      int xTo = x + xMove[i];
      int yTo = y + yMove[i];
      
      if (xTo < 0 || yTo < 0 || xTo >= map.length || yTo >= map[0].length || map[xTo][yTo]) continue;
      map[xTo][yTo] = true;
      dfs(xTo, yTo, move+1);
      map[xTo][yTo] = false;
    }
  }
}