문제
‘젤리’는 튀는 것을 좋아하는 젤리입니다. ‘젤리’는 점프하는 것만으로도 지루함을 느끼고 새로운 점프 게임을 해보고 싶어 합니다. 새로운 점프 게임의 조건은 다음과 같습니다.
- ‘젤리’는 가로 세로 사각형의 개수가 같은 사각형 영역에서만 이동할 수 있습니다. ‘젤리’가 사각형 영역을 벗어나면 땅에 떨어져 즉시 게임에서 패배합니다.
- ‘젤리’의 시작점은 항상 사각형의 가장 왼쪽 위 사각형입니다. 다른 시작점에서 시작하지 않습니다.
- 젤리가 움직일 수 있는 방향은 오른쪽과 아래뿐입니다. 올라가거나 떠날 수 없습니다.
- “Jelly”가 가장 오른쪽 사각형과 아래쪽 사각형에 도달하는 순간 즉시 “Jelly”가 승리하여 게임이 종료됩니다.
- “체리”가 한 번에 이동할 수 있는 칸의 수는 그가 현재 있는 칸에 적힌 수와 같습니다. 필드에 표시된 숫자보다 더 많이 또는 더 적게 이동할 수 없습니다.
새로운 게임이 마음에 들었던 ‘젤리’는 계속 게임을 했고 결국 최종 단계에 이르렀다. 그러나 게임을 하는 영역이 너무 넓어져서 이 게임을 이길 수 있는지 없는지 판단할 수 없게 되었습니다. ‘젤리’는 유능한 프로그래머인 당신에게 주어진 분야에서 이길 수 있는지 알아보라고 부탁했습니다. ‘젤리’를 도와 주어진 플레이 영역에서 끝점(오른쪽 하단 사각형)에 도달할 수 있는지 확인하세요!
기입
첫 번째 입력 라인은 게임 영역의 크기 N을 제공합니다(2 ≤ N ≤ 3).
게임판의 영역(지도)은 두 번째 입력 줄부터 마지막 입력 줄까지 지정됩니다.
-1은 게임판의 승점(우하단 셀)에 적고 나머지 셀에는 0에서 100 사이의 정수를 적는다.
누르다
‘jelly’가 끝점에 도달할 수 있으면 “HaruHaru”(따옴표 없이)가 인쇄되고, 그렇지 않으면 “Hing”(따옴표 없이)이 한 줄에 인쇄됩니다.
문제 설명
점프킹 젤리 문제는 젤리가 정사각형 보드의 첫 번째 위치(0,0)에서 마지막 위치(N – 1, N -1)로 이동할 수 있는지 여부를 결정하는 것입니다.
움직일 수 있는 사각형은 젤리가 밟고 있는 사각형 위에 있고, 이동 가능한 방향은 오른쪽과 아래뿐이다.
가장 중요한 것은 3칸을 움직일 수 있다면 3칸을 움직여야 한다는 것입니다. 1칸 또는 2칸 이동하지 마십시오.
논평
Jelly the King of Jump의 문제는 오른쪽 하단에서 하나씩 이동할 수 있는 영역을 검색하면서 끝 위치에 도달할 수 있는지 확인하는 것입니다.
- 전체 검색을 수행할 수 없습니다.
- 밟으려는 광장의 이동공간을 이용한 BFS 또는 DFS 검색을 이용하세요.
- 최종 위치에 도달하면 “HaruHaru”를 출력하고 도달할 수 없으면 “Hing”을 출력합니다.
DFS로 해결했는데 BFS 조회를 하셔도 상관없습니다.
DFS 조회는 스택과 재귀를 사용하여 두 가지 방법으로 해결되었습니다.
1. 스택이 있는 DFS 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String() args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int()() board = new int(N)(N);
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
board(i)(j) = Integer.parseInt(st.nextToken());
}
}
System.out.println(dfs(board));
br.close();
}
static public String dfs(int()() board) {
Stack<Node> stack = new Stack<>();
boolean()() visited = new boolean(N)(N);
stack.add(new Node(0, 0, board(0)(0)));
while(!stack.isEmpty()) {
Node cur = stack.pop();
int x = cur.x;
int y = cur.y;
int count = cur.count;
if (board(x)(y) == -1) {
return "HaruHaru";
}
if (visited(x)(y)) {
continue;
}
visited(x)(y) = true;
if (x + count < N && !visited(x + count)(y)) {
stack.add(new Node(x + count, y, board(x + count)(y)));
}
if (y + count < N && !visited(x)(y + count)) {
stack.add(new Node(x, y + count, board(x)(y + count)));
}
}
return "Hing";
}
}
class Node {
int x;
int y;
int count;
public Node(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}2. 재귀 함수가 있는 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int()() board;
static boolean()() visited;
public static void main(String() args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
board = new int(N)(N);
visited = new boolean(N)(N);
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
board(i)(j) = Integer.parseInt(st.nextToken());
}
}
System.out.println(dfs(0, 0));
br.close();
}
static public String dfs(int x, int y) {
int count = board(x)(y);
visited(x)(y) = true;
if (count == -1) {
return "HaruHaru";
}
if (x + count < N && !visited(x + count)(y) && !dfs(x + count, y).equals("Hing")) {
return "HaruHaru";
}
if (y + count < N && !visited(x)(y + count) && !dfs(x, y + count).equals("Hing")) {
return "HaruHaru";
}
return "Hing";
}
}