[백준 JAVA] 15558 점프 게임

15558 점프 게임

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

문제설명

• 2개의 행과 n개의 열로 이루어진 맵이 주어진다. 각 셀은 0 또는 1로 이루어져 있다.
• 1은 점프할 수 있는 위치를 의미하고, 0은 점프할 수 없는 위치를 의미한다.
• 주어진 위치에서 왼쪽으로 1칸, 오른쪽으로 1칸, 또는 k칸 점프할 수 있다.
• 첫 번째 행의 (0,0) 위치에서 시작하여 목표는 오른쪽 끝(n-1) 또는 다른 행으로 점프하여 탈출한다.
• 탈출이 가능하면 1을 출력하고, 불가능하면 0을 출력한다.

문제풀이

• 입력 처리:
  • 첫 줄에서 n(맵의 열 길이)과 k(최대 점프 길이)를 읽는다.
  • 다음 두 줄에서 각각의 행을 읽고, 2차원 배열 map에 저장한다.
• BFS (너비 우선 탐색):
  • BFS를 사용하여 탐색을 진행한다.
  • BFS는 현재 위치에서 가능한 모든 점프를 큐에 추가하여, 차례로 처리하는 방식이다.
  • 초기 위치 (0, 0)을 큐에 추가하고 방문한 위치를 기록한다.
  • 큐가 빌 때까지 반복하면서 다음 위치로의 점프를 시도한다:
    • 왼쪽으로 1칸, 오른쪽으로 1칸, k칸 점프 시도.
    • 점프가 유효한지 (범위, 방문 여부, 점프 가능 여부) 확인하고, 유효하다면 큐에 추가한다.
  • 만약 열 인덱스가 n 이상이 되면 탈출이 가능하므로 true를 반환한다.
• 결과 출력:
  • BFS 탐색이 끝나고도 탈출하지 못한 경우 false를 반환하고, 결과를 출력한다.

O(n log⁡ n)   시간복잡도

• BFS의 경우 모든 노드를 방문해야 하므로 최악의 경우는 각 위치에 대해 3개의 가능한 이동을 탐색하게 된다.
• 맵의 각 셀을 최대 1번씩 방문하므로 시간 복잡도는 O(n)이다.
• 각 셀에서 최대 3번의 이동을 고려하므로 전체 시간 복잡도는 O(n)이다.

따라서 이 문제의 전체 시간 복잡도는 O(n)이다.

전체코드

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

public class Main {
    static int n, k; // n: 맵의 길이, k: 최대 점프 길이
    static int map[][]; // 게임 맵을 나타내는 2차원 배열

    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]; // 2행 n열로 맵 초기화

        // 두 개의 맵 행 읽기
        for (int i = 0; i < 2; i++) {
            String str = br.readLine(); // 현재 행을 문자열로 읽기
            for (int j = 0; j < n; j++) {
                map[i][j] = str.charAt(j) - '0'; // 문자를 정수(0 또는 1)로 변환
            }
        }

        // 맵에서 탈출할 수 있는지 확인
        if (go()) {
            System.out.println(1); // 탈출 가능하면 1 출력
        } else {
            System.out.println(0); // 탈출 불가능하면 0 출력
        }
    }

    static boolean go() {
        boolean visit[][] = new boolean[2][n]; // 방문한 위치를 추적하는 2차원 배열
        int dc[] = {-1, 1, k}; // 가능한 열 이동: 왼쪽, 오른쪽, 점프
        Queue<int[]> q = new LinkedList<int[]>(); // BFS를 위한 큐
        q.add(new int[] {0, 0, 0}); // (행 0, 열 0, 시간 0)에서 시작
        visit[0][0] = true; // 시작 위치를 방문한 것으로 표시

        // BFS 수행
        while (!q.isEmpty()) {
            int cur[] = q.poll(); // 현재 위치와 시간을 가져옴
            for (int i = 0; i < 3; i++) {
                int nc = cur[1] + dc[i]; // 새로운 열 인덱스 계산
                int nr = cur[0]; // 행은 처음에 그대로 유지
                int time = cur[2]; // 현재 시간 가져오기

                if (i == 2) {
                    nr = (cur[0] == 1) ? 0 : 1; // 점프 시 행을 전환
                }

                if (nc >= n) {
                    return true; // 성공적으로 맵을 탈출
                }
                if (nc <= time) continue; // 뒤로 점프하거나 이미 방문한 위치로 점프할 수 없음
                if (visit[nr][nc]) continue; // 이미 방문한 위치이면 건너뛰기
                if (map[nr][nc] == 0) continue; // 점프할 수 없는 셀에는 착지할 수 없음

                visit[nr][nc] = true; // 새로운 위치를 방문한 것으로 표시
                q.add(new int[] {nr, nc, time + 1}); // 새로운 위치를 큐에 추가
            }
        }
        return false; // 맵을 탈출할 수 없음
    }
}