백준 1189 컴백홈 JAVA

문제

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

---

입출력

---

예제

---

태그

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹

---

풀이

• 완전탐색을 이용한다.

• dfs를 섞은 방식이다.

• 평소 상하좌우 이동의 경우 bfs를 많이 사용했지만 Queue를 사용하지 않고 dfs만을 이용해 풀이한다.

• 방문처리 배열을 만들고 조건에 맞춰 답을 구한다.

---

코드

정답 코드

/**
 * 1189_컴백홈
 *
 * 완전탐색 - dfs 이용
 * visited 배열을 통해 방문처리를 해준다.
 */

public class P_1189 {
    static int R, C, K;
    static char[][] map;
    static boolean[][] visited; // 방문처리를 위한 배열
    static int[] mx = {-1,1,0,0};
    static int[] my = {0,0,-1,1};
    static int cnt = 0; // 답

    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];
        for (int i = 0; i < R; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = tmp.charAt(j);
            }
        }
        visited = new boolean[R][C];
        visited[R-1][0] = true; // 시작 위치를 방문처리 해준다.

        dfs(1, new Point(R-1, 0)); // 이동횟수+1이 답이므로 depth를 1부터 시작해준다.
        System.out.println(cnt);
    }

    static void dfs(int depth, Point p) {
        if (depth == K) {
            if (p.y == 0 && p.x == C-1) {
                cnt++;
                return;
            }
        }

        for (int i = 0; i < 4; i++) {
            int ny = p.y + my[i];
            int nx = p.x + mx[i];

            if (0<=nx && nx<C && 0<=ny && ny<R) {
               if (map[ny][nx] == '.' && visited[ny][nx] == false) {
                   visited[ny][nx] = true;
                   dfs(depth+1, new Point(ny, nx));
                   visited[ny][nx] = false;
               }
            }
        }

    }

    static class Point {
        int y;
        int x;

        public Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}