[백준 16174번] 점프왕 쩰리 (Large) - java

문제 설명

1. 게임판 크기 N 이 주어진다.

2. 현 위치의 숫자만큼만 오른쪽 혹은 아래로 이동 가능하다.

3. 왼쪽 위부터 시작해서 오른쪽 아래로 갈 수 있는지를 체크하면 된다.

풀이 과정

1. DFS

2. 굉장히 쉬운 문제다. 그냥 위치 확인하고 DFS 해주면 간단하게 풀린다.

3. 현재 위치를 지나왔다고 체크하고, 거기서 점프하는걸 하면 해결 가능

(근데 나는 살짝 더럽게 풀었는데, 그냥 check라는 배열을 하나 더 만들면 조금 더 깔끔하게 해결 가능하다.)

코드

import java.util.*;
import java.io.*;

public class Main
{
    private static int N;
    private static int[][] map;
    private static int[] xMove = {1, 0};
    private static int[] yMove = {0, 1};
    private static String ans = "Hing";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[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(0, 0);
        System.out.println(ans);
    }

    private static void DFS(int x, int y) {
        // 판 밖으로 나가면 체크
        if (x >= N || y >= N) return;
        // 한번 확인했으면 더이상 확인하지 않는다. (원래 check를 해야 하는데 그냥 이렇게 함)
        if (map[x][y] == -2) {
            return;
        }
        // 목적지 도착
        if (map[x][y] == -1) {
            ans = "HaruHaru";
        }
        // 이미 목적지를 도착했으니 더이상은 검색 필요 없다.
        if (ans.equals("HaruHaru")) return;

        // 현재 위치 값 보고
        int now = map[x][y];
        map[x][y] = -2; // 지금 위치는 탐색 완료
        for(int i=0; i<2; i++) {
            // 그래서 현재 위치에서 갈 수 있는 곳을 다 확인
            int xTo = now * xMove[i];
            int yTo = now * yMove[i];

            // 이동이 불가능하다면(이동 후에도 현위치면 볼 필요가 없음)
            if(xTo==0 && yTo==0) return;

            // 다시 DFS
            DFS(x + xTo, y + yTo);
        }
    }
}