Coding Test
백준 점프왕 쩰리 (Large)(16174)
댕발바닥
2024. 3. 18. 20:45
간단한 DFS문제 풀었습니다.
https://www.acmicpc.net/problem/16174
오른쪽, 아래로 이동하면서 마지막 칸에 도달할 수 있는지 여부만 체크하면된다.
가는길에 방문 여부만 관리하면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static boolean[][] visited;
static boolean answer;
public static void main(String[] args) throws IOException {
solution();
}
public static void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] map = 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++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(map, 0, 0);
if (answer) {
System.out.println("HaruHaru");
} else {
System.out.println("Hing");
}
}
public static void dfs(int[][] map, int x, int y) {
visited[x][y] = true;
int p = map[x][y];
if (x == N-1 && y == N-1) {
answer = true;
}
if (x + p < N && !visited[x + p][y]) {
dfs(map, x + p, y);
}
if (y + p < N && !visited[x][y + p]) {
dfs(map, x, y + p);
}
}
}