백준 점프왕 쩰리 (Large)(16174)

 

간단한 DFS문제 풀었습니다.

 

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

16174번: 점프왕 쩰리 (Large)

 

오른쪽, 아래로 이동하면서 마지막 칸에 도달할 수 있는지 여부만 체크하면된다. 

가는길에 방문 여부만 관리하면 된다.

 

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);
        }


    }

}