[백준] 1189번. 컴백홈(JAVA)

문제

https://www.acmicpc.net/problem/1189

---

풀이(22분)

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

public class Main {

    static int r, c, k, answer;
    static char[][] map;
    static boolean[][] visited;
    static int[][] direction = {
            {1,0},
            {-1,0},
            {0,-1},
            {0,1}
    }; // 4방향 탐색

    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()); // 초기 입력

        map = new char[r][c]; // 길 정보
        visited = new boolean[r][c]; // 방문 정보

        for(int i = 0 ; i < r; i++){
            String line = br.readLine();
            for(int j = 0; j < c; j++){
                map[i][j] = line.charAt(j); // line 입력이기 때문에 charAt으로 처리
            }
        }

        visited[r-1][0] = true; // 시작 지점 방문 처리
        dfs(r-1, 0, 1); // dfs 시작

        System.out.println(answer);
    }

    static void dfs(int row, int col, int length){
        if(row == 0 && col == c-1 && length == k){
            answer++;
            return;
        }

        for(int i = 0; i < 4; i++){
            int nextRow = row + direction[i][0];
            int nextCol = col + direction[i][1];
            if(nextRow >= 0 && nextRow < r && nextCol >= 0 && nextCol < c){ // 지도 범위 체크
                if(map[nextRow][nextCol] != 'T' && !visited[nextRow][nextCol]){ // 갈 수 있는 길인지 && 방문한 적은 없는 곳인지
                    visited[nextRow][nextCol] = true; // 방문 체크
                    dfs(nextRow, nextCol, length + 1); // dfs
                    visited[nextRow][nextCol] = false; // 방문 해제(백트래킹)
                }
            }
        }
    }
}

 

간단한 dfs 문제이다. 

매개변수가 3개만 사용되었기에 별도의 클래스를 사용하지 않고, 모두 넘겨주게 하였다.

 

다만, 문제 풀이에 있어 시간이 22분이나 소요된 부분은 초기 시작의 length를 1로 해주어야 했다는 것이다.

이동거리를 체크하는 문제였기에 당연히 시작 지점이 0이라고 생각했으나 정답이 나오지 않았고, 수정을 통하여 해결했다.