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; // 맵을 탈출할 수 없음
}
}'자료구조 > 문제풀이' 카테고리의 다른 글
| [백준 JAVA] 2307 도로검문 (0) | 2024.10.05 |
|---|---|
| [백준 JAVA] 22859 HTML 파싱 (0) | 2024.10.05 |
| [백준 JAVA] 1929 소수 구하기 (1) | 2024.10.03 |
| [백준 JAVA] 13022 늑대와 올바른 단어 (0) | 2024.10.03 |
| [백준 JAVA] 22948 원 이동하기 2 (0) | 2024.10.02 |