BOJ 9944 : NxM 보드 완주하기

풀이 상세

DFS

풀이 요약

1. 모든 맵을 다 돌기까지 공의 방향을 최소 몇번 바뀌는지 구하는 문제
2. 먼저 맵을 만들 때 . 의 갯수를 세어서, 만약 완전 탐색시 모든 조건을 통과하여 . 의 갯수 0 이 되었을 때가 모든 맵을 빠짐없이 다 돈 것으로 판단한다.
3. 기존에 갔던 값에서 방문처리를 다시 복귀시켜기 편하도록 DFS 를 활용하였다. 시간 초과를 벗어나기 위해 어느정도의 백트래킹은 해주는 게 좋다. 가령, 임의의 최소 이동 횟수를 먼저 구했다면 그보다 큰 값이 나오는 경우는 더이상 확인할 이유가 없다.
4. 처음 문제는 1칸씩 다음 칸으로 이동하도록 했더니 시간 초과가 나왔다. 1칸 씩 움직이기보다는 반복문을 통해 현재 다음칸으로 이동할 수 최대한의 거리까지 다 이동 한 후에 한 번에 처리하는 것으로 시간초과를 해결하였다.

배운점

• 식에는 빨리 도달했는데, 딴 곳에 정신팔리다가 시간을 허비했다.

정답

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

public class Main {
    static final int dr[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stk;
    static int R, C, cnt, currAns;
    static final int RESULT_MAX = 987654321;
    static char map[][];
    static boolean visited[][];

    private static void input() throws IOException {
        R = Integer.parseInt(stk.nextToken());
        C = Integer.parseInt(stk.nextToken());
        map = new char[R][C];
        visited = new boolean[R][C];
        cnt = 0;
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                if (map[i][j] == '.') cnt++;
            }
        }
        currAns = RESULT_MAX;
    }

    private static void DFS(int r, int c, int dist, int result) {
        if (currAns < result) return;
        if (dist == 0) {
            currAns = result;
            return;
        }
        for (int d = 0; d < 4; d++) {
            int currDist = 0;
            int nr = r + dr[d];
            int nc = c + dc[d];
            while (nr >= 0 && nr < R && nc >= 0 && nc < C && map[nr][nc] == '.' && !visited[nr][nc]) {
                visited[nr][nc] = true;
                currDist++;
                nr += dr[d];
                nc += dc[d];
            }
            if(currDist == 0) continue;
            nr -= dr[d];
            nc -= dc[d];
            DFS(nr, nc, dist - currDist, result + 1);
            while(--currDist >= 0) {
                visited[nr][nc] = false;
                nr -= dr[d];
                nc -= dc[d];
            }
        }
    }

    private static void solve() {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j] == '.') {
                    int dist = cnt;
                    visited[i][j] = true;
                    DFS(i, j, dist-1, 0);
                    visited[i][j] = false;
                }
            }
        }
    }

    private static void output(int T) {
        if(cnt == 1) {
            System.out.printf("Case %d: %d\n", T, 0);
            return;
        }
        System.out.printf("Case %d: %d\n", T, currAns == RESULT_MAX ? -1 : currAns);
    }

    public static void main(String[] args) throws IOException {
        int T = 1;
        while (true) {
            try {
                stk = new StringTokenizer(br.readLine());
                input();
                solve();
                output(T++);
            } catch (Exception e) {
                return;
            }
        }
    }
}

틀린답

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

public class Main {
    static final int dr[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stk;
    static int R, C, cnt, currAns;
    static final int RESULT_MAX = 987654321;
    static char map[][];
    static boolean visited[][];

    private static void input() throws IOException {
        R = Integer.parseInt(stk.nextToken());
        C = Integer.parseInt(stk.nextToken());
        map = new char[R][C];
        visited = new boolean[R][C];
        cnt = 0;
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                if (map[i][j] == '.') cnt++;
            }
        }
        currAns = RESULT_MAX;
    }

    private static void DFS(int r, int c, int dist, int vect, int result) {
        if (currAns < result) return;
        if (dist == 0) {
            currAns = result;
            return;
        }
        for (int d = vect; d < vect + 4; d++) {
            int nr = r + dr[d % 4];
            int nc = c + dc[d % 4];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if (map[nr][nc] == '*') continue;
            if (visited[nr][nc]) continue;
            visited[nr][nc] = true;
						// 1칸 씩 가면 안된다. 시간초과가 나온다.
            DFS(nr, nc, dist - 1, d, d == vect ? result : result + 1);
            visited[nr][nc] = false;
        }
    }

    private static void solve() {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j] == '.') {
                    int dist = cnt;
                    visited[i][j] = true;
                    DFS(i, j, dist, 0, 0);
                    visited[i][j] = false;
                }
            }
        }
    }

    private static void output(int T) {
        System.out.printf("Case %d: %d\n", T, currAns == RESULT_MAX ? -1 : currAns);
    }

    public static void main(String[] args) throws IOException {
        int T=1;
        while (true) {
            try {
                stk = new StringTokenizer(br.readLine());
                input();
                solve();
                output(T++);
            } catch (Exception e) {
                return;
            }
        }
    }
}