[BOJ] 1189 컴백홈 - JAVA

1. 문제

1189번: 컴백홈

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

 

첫 줄에 거리가 K인 가짓수를 출력한다.

---

2. 풀이

static 변수

int R,C,K	입력값
char[][] map	입력값(지도)
int count	거리가 K인 길의 가짓수
int[][] deltas	이동 가능한 곳

 

Main

초기 위치(왼쪽 맨 아래)를 방문표시한 후 dfs를 호출한다.

count를 출력한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   R = Integer.parseInt(st.nextToken());
   C = Integer.parseInt(st.nextToken());
   K = Integer.parseInt(st.nextToken());

   map = new char[R][C];

   for(int i=0;i<R;i++){
      map[i] = in.readLine().toCharArray();
   }

   map[R-1][0] = 'x';
   dfs(R-1,0, 1);

   System.out.println(count);
}

 

DFS

파라미터로 r,c,cnt를 받는다. 각각 현 위치와 경로 길이를 저장한다.

1.  cnt가 K이상이면 더 이상 탐색할 필요 없으므로 끝낸다.

2.  목적지(r==0 && c==C-1)에 도달하면 끝내되, cnt==K일 경우 count+1한다.

3.  현 위치 (r,c)에서 갈 수 있는 (nr,nc)를 찾는다. 범위에 벗어나있거나 '.'이 아닌 경우 continue한다. 

4.  재귀호출하기 전 map에 방문표시한다. 돌아오면 원복한다.

public static void dfs(int r, int c, int cnt){
   if(cnt>K) return;
   if(r==0 && c == C-1){
      if(cnt==K) count++;
      return;
   }

   int nr,nc;
   for(int[] d:deltas){
      nr = r+d[0];
      nc = c+d[1];
      if(nr<0||nc<0||nr>=R||nc>=C||map[nr][nc]!='.') continue;
      map[nr][nc] = 'x';
      dfs(nr,nc,cnt+1);
      map[nr][nc] = '.';
   }
}

 

전체 코드

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

public class BOJ_1189_컴백홈 {
   static int R,C,K;
   static char[][] map;
   static int count = 0;
   static int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1}};
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      R = Integer.parseInt(st.nextToken());
      C = Integer.parseInt(st.nextToken());
      K = Integer.parseInt(st.nextToken());

      map = new char[R][C];

      for(int i=0;i<R;i++){
         map[i] = in.readLine().toCharArray();
      }

      map[R-1][0] = 'x';
      dfs(R-1,0, 1);

      System.out.println(count);
   }
   public static void dfs(int r, int c, int cnt){
      if(cnt>K) return;
      if(r==0 && c == C-1){
         if(cnt==K) count++;
         return;
      }

      int nr,nc;
      for(int[] d:deltas){
         nr = r+d[0];
         nc = c+d[1];
         if(nr<0||nc<0||nr>=R||nc>=C||map[nr][nc]!='.') continue;
         map[nr][nc] = 'x';
         dfs(nr,nc,cnt+1);
         map[nr][nc] = '.';
      }
   }
}

---

3. 결과