[백준] 15558번: 점프 게임

문제

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

 

풀이

모든 경로를 탐색하며 목표점인 N칸 이상을 넘어갈 수 있는지 판별하는 문제이다. 손으로 그림 몇 번 그려보니 bfs로 해결이 가능할 것 같아서 bfs 알고리즘을 활용하였다.

 

칸을 이동하는 경우 중 반대편 줄의 i + k칸으로 이동하는 경우 선언한 int변수 isLeft의 값을 toggle 작업(1이면 0으로 바꾸고, 0이면 1로 바꾸기)을 해주어야 했는데, 어떻게 해야할지 고민을 좀 했다.. 비트연산자 XOR로 변환을 했는데 생각해보니 isLeft = 1 - isLeft로도 변환이 가능하다...!

 

사실 기존에 isLeft를 boolean 변수로 선언해서 사용하긴 했는데 if 분기가 많아 코드가 지저분해 보여서 isLeft를 int 타입으로 바꾸고 ArrayList에 왼쪽/오른쪽 줄에 대한 정보를 지니는 배열을 넣었다.

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int k;
    static List<int[]> arr;
    static List<boolean[]> visited;
    
    static class Node {
        private int number; // 현재 칸의 번호
        private int isLeft; // 왼쪽줄 오른쪽줄 구분 위한 값
        private int limit; // 사라지는 칸의 번호

        public Node(int number, int isLeft, int limit) {
            this.number = number;
            this.isLeft = isLeft;
            this.limit = limit;
        }
    }
    
    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());

        arr = new ArrayList<>();
        int[] left = br.readLine().chars().map(chr -> chr - '0').toArray();
        int[] right = br.readLine().chars().map(chr -> chr - '0').toArray();
        arr.add(right);
        arr.add(left);

        visited = new ArrayList<>();
        boolean[] leftVisited = new boolean[N];
        boolean[] rightVisited = new boolean[N];
        visited.add(rightVisited);
        visited.add(leftVisited);

        br.close();
        
        int result = bfs();
        System.out.println(result);
    }

    private static int bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 1, -1));
        visited.get(1)[0] = true;
        
        while(!queue.isEmpty()) {
            Node current = queue.poll();
            int number = current.number;
            int isLeft = current.isLeft;
            int limit = current.limit;

            // 목표 값 N 넘으면 1
            if(number + 1 >= N || number + k >= N) {
                return 1;
            }
            // 범위를 벗어나지 않고 해당 인덱스의 값이 0이 아닐 경우 큐에 추가
            if(arr.get(isLeft)[number + 1] != 0 && !visited.get(isLeft)[number + 1]) {
                queue.offer(new Node(number + 1, isLeft, limit + 1));
                visited.get(isLeft)[number + 1] = true;
            }
            if(number - 1 >= 0 && arr.get(isLeft)[number - 1] != 0 && number - 1 > limit + 1 && !visited.get(isLeft)[number - 1]) {
                queue.offer(new Node(number - 1, isLeft, limit + 1));
                visited.get(isLeft)[number - 1] = true;
                
            }
            if(arr.get(isLeft ^ 1)[number + k] != 0 && !visited.get(isLeft ^ 1)[number + k]) {
                queue.offer(new Node(number + k, isLeft ^ 1, limit + 1));
                visited.get(isLeft ^ 1)[number + k] = true;
            }
        }
        return 0;
    }
}