백준 16173번 점프왕 쩰리(Small)-JAVA

📝문제

📝알고리즘

//정사각형 구역의 값을 2차원 행렬에 입력받고
//dfs(0,0)부터 시작해서 true 값을 반환하면 "HaruHaru"를
//false값을 반환하면 "Hing"을 출력
//dfs 메서드는 다음과 같이 작성
//경계를 벗어나거나 이미 방문한 구역을 가면 false 반환
//구역의 값이 -1에 도달하면 true 반환
//그렇지 않으면 현재 구역을 방문했다고 기록하고
//아래로 구역에 있는 수만큼 또는 오른쪽으로 구역에 있는 수만큼 더해서
//dfs 탐색을 계속함

📝구현

import java.util.*;

public class Main {
    static int N;
    static int[][] square;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        square = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                square[i][j] = scanner.nextInt();
            }
        }

        if (dfs(0, 0)) {
            System.out.println("HaruHaru");
        } else {
            System.out.println("Hing");
        }
    }

    public static boolean dfs(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N || visited[x][y]) {
            return false;
        }

        if (square[x][y] == -1) {
            return true;
        }

        visited[x][y] = true;

        int jump = square[x][y];

        return dfs(x + jump, y) || dfs(x, y + jump);
    }
}

📌기록하고 싶은 내용

최소 점프 횟수가 아닌 도착 가능 여부만 확인하는 경우에는 DFS가 효율적일 수도 있음..

문제 풀 때 경계 조건 세세하게 체크하기!