[백준] 1189 컴백홈 (JAVA)

문제 링크:

1189번: 컴백홈

 

 

난이도: 실버1

 

 

문제:

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

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

 

 

입력:

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

 

 

출력:

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

 

 

문제 이해:

이 문제는 처음부터 예제를 통해 설명하고 있어 이해하기 어렵지 않다.

 

좀 더 쉽게 말하자면, 왼쪽 하단이 출발지, 오른쪽 상단이 목적지이다.

첫 번째 줄에는 행(row) 과 열(column) 의 수가 주어지고 (예제 입력 1에서는 3과 4),
그 다음에는 출발지에서 목적지까지 이동해야 하는 거리가 주어진다 (예제 입력 1에서는 6).

 

이후에는 각 칸의 상태를 입력하는데,

• ‘T’ 는 장애물을 의미하고,
• ‘.’ 는 이동할 수 있는 길을 의미한다.

입력을 모두 완료한 뒤에는,
주어진 거리만큼 이동하여 출발지에서 목적지까지 도달할 수 있는 모든 경우의 수를 구하는 것이다.

 

즉, 문제의 예시에서처럼 예제 입력 1은 해당 규칙에 따라 계산된 결과를 보여주며,
출발점(a)에서 시작해 b, c 순으로 이동하는 과정을 나타낸다.

 

 

구현 방향:

작성자는 처음에 DFS와 BFS 중 어느 방식을 사용할지 고민하였다.
그러나 이 문제는 모든 가능한 경로를 탐색해야 하므로,
백트래킹 과정이 필수적이라 판단하여 DFS 방식을 선택하였다.

 

구체적으로, 출발지에서 시작하여 상·하·좌·우 방향으로 이동 가능한 경로를 재귀적으로 탐색한다.
탐색 도중 목적지에 도달하면 경우의 수를 1 증가시키고,
해당 경로의 탐색을 종료(백트래킹)한다.

 

또한, 현재까지 이동한 거리가 입력값 K를 초과한 경우에는
더 이상 탐색할 필요가 없으므로 즉시 백트래킹을 수행한다.

 

이 과정을 반복하여, 이동 거리 K와 목적지 조건을 동시에 만족하는 모든 경로의 개수를 계산하였다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

 

정답코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int R,C,K;
    static char[][] matrix;
    static boolean[][] visited;
    static int[] dx={-1,1,0,0};
    static int[] dy={0,0,-1,1};
    static int result=0; //결과


    public static void solve(int x, int y, int dist){
       //거리가 6이고 목적지인 경우
        if(dist==K && x==0 && y==C-1) {
            result++;
            return;
        }

        //탐색이 더이상 필요 없을때
        if(dist>K) return;

        for(int d=0; d<4; d++){
            int nx=x+dx[d];
            int ny=y+dy[d];

            if(nx<0 || ny<0 || nx>R-1 || ny>C-1) continue;
            //방문하지 않았고 장애물이 아니라면 방문
            if(!visited[nx][ny] && matrix[nx][ny]!='T'){
                visited[nx][ny]=true;
                solve(nx,ny,dist+1);
                visited[nx][ny]=false; //백트래킹
            }

        }
    }

    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());
        K=Integer.parseInt(st.nextToken());

        matrix=new char[R][C];
        visited=new boolean[R][C];

        for(int i=0; i<R; i++){
            StringBuilder sb=new StringBuilder(br.readLine());
            for(int j=0; j<C; j++){
                matrix[i][j]=sb.charAt(j);
            }
        }
        //초기 세팅 끝


        //출발지 부터 탐색 시작
        visited[R-1][0]=true;
        solve(R-1,0,1);

        //결과 출력
        System.out.println(result);


    }
}

 

 

마무리하며:

최근 여러 백트래킹 알고리즘 문제를 풀어보면서,
이제는 해당 유형의 문제를 해결하는 데 큰 어려움이 없음을 느꼈다.
과거라면 해결하지 못했을 문제를 이제는 쉽게 풀 수 있게 되어,
스스로의 성장도 실감할 수 있었다.

 

또한 이 문제는 백트래킹과 재귀의 기본 원리를 명확히 이해할 수 있는 좋은 예시이기 때문에,
해당 개념을 익히고자 하는 사람들에게 추천할 만한 문제라고 생각한다.

 

 

감사합니다.