문제 내용은 입력으로 배열의 가로 세로 크기를 받은 뒤, 그 다음 입력으로는 숫자를 쭉 받게 되는데 이후 쩰리는 배열의 0,0 인덱스에서부터 시작하고 현재 밟고 있는 인덱스의 값 만큼 우측과 아래쪽으로 이동할 수 있다.
어떻게 잘 이동해서 배열의 가장 마지막 인덱스 값인 -1로 들어오는데 성공하면 HaruHaru 실패하면 Hing을 출력해주면 된다.
주의해야 할 점이 현재 밟고있는 인덱스의 값 만큼만 우측, 하단으로 이동이 가능하고, 현재 밟고 있는 발판이 0이라면 한 칸도 움직이지 못하므로 Hing을 출력해주면 되겠다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int size;
static int[][] map;
static boolean status;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
size = Integer.parseInt(br.readLine());
map = new int[size][size];
for (int i = 0; i < size; i++) {
int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int j = 0; j < size; j++) {
map[i][j] = arr[j];
}
}
boolean[][] visited = new boolean[size][size];
dfs(0, 0, visited);
if (status) {
System.out.println("HaruHaru");
} else {
System.out.println("Hing");
}
}
public static void dfs(int i, int j, boolean[][] visited) {
visited[i][j] = true;
int current = map[i][j];
if (current == 0) {
return;
}
if (map[i][j] == map[size - 1][size - 1]) {
status = true;
return;
}
// 가로이동
if (i + current < size) {
dfs(i + current, j, visited);
visited[i + current][j] = false;
}
// 세로이동
if (j + current < size) {
dfs(i, j + current, visited);
visited[i][j + current] = false;
}
}
}문제를 풀어보자면 먼저 입력을 받아 2차원 배열에 모두 넣어준 후, DFS를 통해 모든 사례를 확인해봐야 하는데 현재 인덱스 값 만큼 우측, 하단으로 쭉쭉 이동해서 2차원 배열의 마지막 인덱스까지 가는 데 성공하면 boolean에 따로 처리를 해 주고, 그 외에는 모두 실패니 Hing을 출력해주면 된다.
가장 주의할 점은 인덱스에 0이 들어오면 움직이지 못하기 때문에 무한하게 dfs 돌리다가 스택 오버플로우 떨어지는데 이 부분만 예외처리를 해 주면 깔끔하게 끝낼 수 있다
Leave a Reply