[골드5] 백준 15558번 : 점프 게임

코드 1줄이 부족해서 2달이나 걸린 문제...

'점프 게임' 문제 바로가기

사진은 좀 부끄럽지만 어쨌든 내 힘으로 풀었다는게 뿌듯해서 올려봤다.
나는 답을 안보고 풀고 싶었다. 조금만 더 하면 할 수 있을 것 같아서... (집착!😃)
그래서 2달 전에 안풀렸을 때 '나중에 다시 도전하자' 하며 넘겼고 바로 오늘 다시 시도했다.
결과는 성공!

원인 분석

나는 예전에도 지금도 DFS로 풀었다.
왜냐하면 종료 조건이 1개의 경로라도 존재한다면 바로 끝나는 거라서, 경로를 끝까지 먼저 가봐야겠다고 생각했다.
그런데 이전에 틀렸던 코드와 비교하니 딱 1줄이 달랐다.

함수 dfs(현재 위치) {
	...
    if(다음 위치로 갈 수 있으면 and 방문한 적 없으면) {
    	visit[현재 위치] = true
        dfs(다음 위치);
        visit[현재 위치] = false; // 이 부분이 없었던 것이 원인!
    }
	
}

재귀를 통해 길을 만들어가며 막다른 길에 다다르면 다시 돌아온다.
그리고 다시 새로운 길로 이동한다.
그렇기 때문에 되돌아오면서 이동했던 길을 재방문이 가능하게 만들어야 한다.

정답 코드

public class Main {
    static int N, K, answer;
    static int[][] arr;
    static boolean[][] visit;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new int[2][N];
        visit = new boolean[2][N];
        for(int i = 0; i < 2; i++) {
            char[] chs = br.readLine().toCharArray();
            for(int j = 0; j < chs.length; j++) {
                arr[i][j] = chs[j]-'0';
            }
        }
        
        visit[0][0] = true;
        dfs(0,0,0);
        
        System.out.print(answer);
        br.close();
    }
    
    private static boolean dfs(int r, int c, int time) {
        if(c+K >= N || c+1 >= N) {
            answer = 1;
            return true;
        }
        
        // 1칸 전진
        if(arr[r][c+1] == 1 && !visit[r][c+1]) {
            visit[r][c+1] = true;
            if(dfs(r, c+1, time+1)) return true;
            visit[r][c+1] = false;
        }
        // 1칸 후진
        if(c-1 >= 0 && arr[r][c-1] == 1 && c-1 > time && !visit[r][c-1]) {
            visit[r][c-1] = true;
            if(dfs(r, c-1, time+1)) return true;
            visit[r][c-1] = false;
        }
        // k 점프
        if(arr[1-r][c+K] == 1 && !visit[1-r][c+K]) {
            visit[1-r][c+K] = true;
            if(dfs(1-r, c+K, time+1)) return true;
            visit[1-r][c+K] = false;
        }
        
        return false;
    }
}