[Java] 15558 점프 게임

문제

문제
상근이는 오른쪽 그림과 같은 지도에서 진행하는 게임을 만들었다.

지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다. 

칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 
안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다.

가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며, 매 초마다 아래 세 가지 행동중 하나를 해야 한다.

한 칸 앞으로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i+1번 칸으로 이동한다.

한 칸 뒤로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i-1번 칸으로 이동한다.

반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한다.
예를 들어, 현재 있는 칸이 왼쪽 줄의 i번 칸이면, 오른쪽 줄의 i+k번 칸으로 이동해야 한다.

N번 칸보다 더 큰 칸으로 이동하는 경우에는 게임을 클리어한 것이다.

게임을 재밌게 하기 위해서, 상근이는 1초에 한 칸씩 각 줄의 첫 칸이 사라지는 기능을 만들었다.
즉, 게임을 시작한지 1초가 지나면 1번 칸이 사라지고, 2초가 지나면 2번 칸이 사라진다.
편의상 유저가 먼저 움직이고, 칸이 사라진다고 가정한다.

즉, 이번에 없어질 칸이 3번 칸인데, 상근이가 3번 칸에 있다면,
3번 칸에서 다른 칸으로 이동하고 나서 3번 칸이 없어지는 것이다.

각 칸의 정보가 주어졌을 때, 게임을 클리어 할 수 있는지, 없는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000)

둘째 줄에는 왼쪽 줄의 정보가 주어진다. 
i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다.
셋째 줄에는 오른쪽 줄의 정보가 주어지고, 각 문자의 의미는 왼쪽 줄의 의미와 동일하다.

왼쪽 줄의 1번 칸은 항상 안전한 칸이다.

출력
게임을 클리어할 수 있으면 1을, 없으면 0을 출력한다.

 

문제 풀이

처음에는 DFS로 옆라인 k칸을 이동하는 경우, 같은 라인 +1칸을 이동하는 경우, -1칸을 이동하는 경우를 모두 탐색하며 결과를 출력하려고 했다. 그러나 14%에서 시간초과가 발생했다. 아무래도 BFS인 듯하다.

BFS로 변경한 뒤에도 메모리 초과나 시간초과에 여러번 실패를 겪었고 코드를 다듬는 과정이 필요했다.

검사하는 배열을 int에서 boolean으로 변경했고 정지 조건도 단순화 시켰다. 자세한건 주석으로 처리한다.

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

public class N15558 {
    private static int N,k, result = 0;
    private static int [][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        map = new int[2][N];

        for(int line = 0; line < map.length; line++){
            String[] tiles = br.readLine().split("");
            for(int tile = 0; tile < map[line].length; tile++) {
                int t = Integer.parseInt(tiles[tile]);
                map[line][tile] = t;
            }
        }

        dfs(0, 0, -1);

        System.out.println(result);
    }

    public static void dfs(int currLine, int currTile, int turn){
        // 이미 결과가 나왔다면 종료
        if(result == 1)
            return;

        // N턴이 지나 타일이 모두 사라지면 이동할 수 없기 때문에 종료
        if(turn > N - 1) {
            System.out.println(turn);
            return;
        }

        // 해당 턴이 확인하려는 타일보다 크다면 
        // 이미 사라진 타일을 지나려는 것이기 때문에 종료
        if(turn >= currTile)
            return;

        // 첫 타일 보다 뒷 타일을 확인하려는 경우 종료
        if(currTile < 0)
            return;

        // 확인하려는 타일이 N보다 크거나 같은 상황에서 타일 값이 1이라면 결과를 1로 변경하고 종료
        if(currTile > N - 1 || (currTile == N - 1 && map[currLine][currTile] == 1)) {
            result = 1;
            return;
        }

        // 해당 타일이 이동할 수 없는 타일이라면 종료
        if(map[currLine][currTile] == 0)
            return;

        // 옆 라인 k칸, 같은 라인 +1칸, -1칸 이동해보기
        if(currLine == 0) {
            dfs(1, currTile + k, turn + 1);
            dfs(0, currTile + 1,  turn + 1);
            dfs(0, currTile - 1,  turn + 1);
        }else{
            dfs(0, currTile + k, turn + 1);
            dfs(1, currTile + 1,  turn + 1);
            dfs(1, currTile - 1,  turn + 1);
        }
    }
}

자바 코드

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

public class Main {
    private static int N,k;
    private static boolean [][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

	// n칸보다 더 이동했을 때의 성공을 검사해야하기 때문에 버무이를 N + 1 + k로 잡는다.
    // 최대 n + k 칸 만큼 더 갈 수 있다.
        map = new boolean[2][N + 1 + k];

        for(int line = 0; line < 2; line++){
            String tiles = br.readLine();
            for(int tile = 0; tile < N; tile++) {
                if(tiles.charAt(tile) == '0')
                    map[line][tile] = true;
            }
        }

        bfs();
    }

    public static void bfs(){
        Queue<int[]> q = new LinkedList<>();
        int[] start = {0, 0, -1};
        q.add(start);

        while(!q.isEmpty()){
            int[] curr = q.poll();

	// n칸보다 더 갔으면 1을 출력하고 종료
            if(curr[1] >= N - 1) {
                System.out.println(1);
                return;
            }
	// 이동할 수 없는 자리이거나 이미 확인한 자리 일 경우에는 확인하지 않는다.
            if(!map[1 - curr[0]][curr[1] + k]) {
            	// 확인한 자리이기 때문에 true로 처리하여 다시 확인하지 않는다.
                map[1 - curr[0]][curr[1] + k] = true;
                q.offer(new int[]{1 - curr[0], curr[1] + k, curr[2] + 1});
            }
            if(!map[curr[0]][curr[1] + 1]) {
                map[curr[0]][curr[1] + 1] = true;
                q.offer(new int[]{curr[0], curr[1] + 1, curr[2] + 1});
            }
            // -1로 이동할 경우에는 해당 턴을 확인하여 이동하려는 칸이 해당 턴 + 1보다 클 경우에만
            // 이동가능 처리를 한다.
            if(curr[1] - 1 > curr[2] + 1 && curr[1] - 1 > -1 && !map[curr[0]][curr[1] - 1]) {
                map[curr[0]][curr[1] - 1] = true;
                q.offer(new int[]{curr[0], curr[1] - 1, curr[2] + 1});
            }
        }
		
        // 큐가 빌때까지 도착을 못했으면 종료
        System.out.println(0);
    }
}