백준 15558 점프 게임 (Java)

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

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


public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        boolean ans = false;

        int n = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());

        String lEft = reader.readLine();
        String rIght = reader.readLine();

        int[] left = new int[n + 1];
        int[] right = new int[n + 1];

        boolean[] vLeft = new boolean[n + 1];
        boolean[] vRight = new boolean[n + 1];


        for (int i = 1; i <= n; i++) {
            left[i] = lEft.charAt(i - 1) - '0';
            right[i] = rIght.charAt(i - 1) - '0';
        }

        Queue<Pair> queue = new ArrayDeque<>();

        queue.offer(new Pair(1, 0, false));
        vLeft[1] = true;

        while (!queue.isEmpty()) {
            Pair cur = queue.poll();
            if (cur.isRight) {
                vRight[cur.cur] = true;
            } else {
                vLeft[cur.cur] = true;
            }

            //반대편의 k칸으로 넘어가서 게임을 클리어할 수 있을 경우
            if (cur.cur + k > n) {
                ans = true;
                break;
            }

            if (cur.cur <= cur.sec) {
                continue;
            }

            //한 칸 앞으로 이동
            if (cur.isRight) {
                if (right[cur.cur + 1] == 1 && !vRight[cur.cur + 1]) {
                    queue.offer(new Pair(cur.cur + 1, cur.sec + 1, cur.isRight));
                    vRight[cur.cur + 1] = true;
                }
            } else {
                if (left[cur.cur + 1] == 1 && !vLeft[cur.cur + 1]) {
                    queue.offer(new Pair(cur.cur + 1, cur.sec + 1, cur.isRight));
                    vLeft[cur.cur] = true;
                }
            }


            //한 칸 뒤로 이동
            if (cur.isRight) {
                if (cur.cur > 1 && right[cur.cur - 1] == 1 && !vRight[cur.cur - 1]) {
                    queue.offer(new Pair(cur.cur - 1, cur.sec + 1, cur.isRight));
                    vRight[cur.cur - 1] = true;
                }
            } else {
                if (cur.cur > 1 && left[cur.cur - 1] == 1 && !vLeft[cur.cur - 1]) {
                    queue.offer(new Pair(cur.cur - 1, cur.sec + 1, cur.isRight));
                    vLeft[cur.cur - 1] = true;
                }
            }

            //반대편 k칸 이동
            if (cur.isRight) {
                if (left[cur.cur + k] == 1 && !vLeft[cur.cur + k]) {
                    queue.offer(new Pair(cur.cur + k, cur.sec + 1, !cur.isRight));
                    vLeft[cur.cur + k] = true;
                }
            } else {
                if (right[cur.cur + k] == 1 && !vRight[cur.cur + k]) {
                    queue.offer(new Pair(cur.cur + k, cur.sec + 1, !cur.isRight));
                    vRight[cur.cur + k] = true;
                }
            }


        }

        if (ans) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }

    }
}

class Pair {
    int cur;
    int sec;
    boolean isRight;

    public Pair(int cur, int sec, boolean isRight) {
        this.cur = cur;
        this.sec = sec;
        this.isRight = isRight;
    }
}

1. 문제

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

지도는 총 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을 출력한다.

2. 풀이

문제에 따르면 시작점에서 시작하여 3개의 이동 방식이 있다

• 현재 줄의 1칸 앞으로 이동
• 현재 줄의 1칸 뒤로 이동
• 옆 줄의 k칸 앞으로 이동

이에 따라 BFS로 문제를 풀 수 있다 생각했다.

 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        boolean ans = false;

        int n = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());

        String lEft = reader.readLine();
        String rIght = reader.readLine();

        int[] left = new int[n + 1];
        int[] right = new int[n + 1];

        boolean[] vLeft = new boolean[n + 1];
        boolean[] vRight = new boolean[n + 1];


        for (int i = 1; i <= n; i++) {
            left[i] = lEft.charAt(i - 1) - '0';
            right[i] = rIght.charAt(i - 1) - '0';
        }

문제에 필요한 값을 입력받고, BFS에 사용할 visit 배열을 좌우 각각 선언한다.

        Queue<Pair> queue = new ArrayDeque<>();

        queue.offer(new Pair(1, 0, false));
        vLeft[1] = true;
        
class Pair {
    int cur;
    int sec;
    boolean isRight;

    public Pair(int cur, int sec, boolean isRight) {
        this.cur = cur;
        this.sec = sec;
        this.isRight = isRight;
}

큐에 들어갈 Pair 클래스를 만들었다. 해당 클래스에는 현재 위치, 현재까지 지난 시간, 현재 좌우 중 어떤 줄에 위치하는지를 나타낸다. 처음에는 왼쪽 1번 칸에서 시작하므로 해당 위치를 큐에 넣어준다.

 

 while (!queue.isEmpty()) {
            Pair cur = queue.poll();
            if (cur.isRight) {
                vRight[cur.cur] = true;
            } else {
                vLeft[cur.cur] = true;
            }

            //반대편의 k칸으로 넘어가서 게임을 클리어할 수 있을 경우
            if (cur.cur + k > n) {
                ans = true;
                break;
            }

            if (cur.cur <= cur.sec) {
                continue;
            }

           
            }

			...
        }

큐를 돌면서 현재 위치에 해당하는 visit 배열의 값을 true로 바꿔준다. 또, 현재 칸에서 k칸을 넘어가는 것이 n번 칸을 넘어갈 경우 현재 칸에서 반대편의 k칸 앞으로 이동하여 게임을 클리어할 수 있음을 의미하므로 연산을 종료한다. 현재 칸이 현재 지난 시간 이하일 경우 해당 칸은 무너져 내린 것이므로 연산하지 않고 넘어간다.

 //한 칸 앞으로 이동
            if (cur.isRight) {
                if (right[cur.cur + 1] == 1 && !vRight[cur.cur + 1]) {
                    queue.offer(new Pair(cur.cur + 1, cur.sec + 1, cur.isRight));
                    vRight[cur.cur + 1] = true;
                }
            } else {
                if (left[cur.cur + 1] == 1 && !vLeft[cur.cur + 1]) {
                    queue.offer(new Pair(cur.cur + 1, cur.sec + 1, cur.isRight));
                    vLeft[cur.cur] = true;
                }
            }


            //한 칸 뒤로 이동
            if (cur.isRight) {
                if (cur.cur > 1 && right[cur.cur - 1] == 1 && !vRight[cur.cur - 1]) {
                    queue.offer(new Pair(cur.cur - 1, cur.sec + 1, cur.isRight));
                    vRight[cur.cur - 1] = true;
                }
            } else {
                if (cur.cur > 1 && left[cur.cur - 1] == 1 && !vLeft[cur.cur - 1]) {
                    queue.offer(new Pair(cur.cur - 1, cur.sec + 1, cur.isRight));
                    vLeft[cur.cur - 1] = true;
                }
            }

            //반대편 k칸 이동
            if (cur.isRight) {
                if (left[cur.cur + k] == 1 && !vLeft[cur.cur + k]) {
                    queue.offer(new Pair(cur.cur + k, cur.sec + 1, !cur.isRight));
                    vLeft[cur.cur + k] = true;
                }
            } else {
                if (right[cur.cur + k] == 1 && !vRight[cur.cur + k]) {
                    queue.offer(new Pair(cur.cur + k, cur.sec + 1, !cur.isRight));
                    vRight[cur.cur + k] = true;
                }

각 이동 방식에 대해 검증을 하고, 검증이 완료된 이동 방식에 대해서 큐에 다음 위치와 시간을 넣고, visit 배열을 갱신한다. 

 

연산이 끝나고 게임의 클리어 가능 여부를 0, 1로 출력하면 정답을 구할 수 있다.