[백준] 16173 점프왕 쩰리 (Small) | DFS, 브루트포스, 그래프 | 실버 Ⅳ | JAVA

📌 문제

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

 

⭐ 문제 소개

젤리 캐릭터인 '쩰리'가 정사각형 게임판에서 목표 지점(맨 오른쪽 아래 칸)에 도달할 수 있는지 판별하는 문제입니다. 문제의 핵심은 주어진 이동 규칙을 따르면서 목표 지점에 도달할 수 있는 경로를 탐색하는 것입니다.

⭐ 문제 풀이 과정

1. 그래프 탐색 활용

이 문제는 그래프 탐색을 통해 해결할 수 있습니다.

• DFS (깊이 우선 탐색): 재귀적으로 경로를 탐색하며 도달 가능한 모든 칸을 방문합니다.
• BFS (너비 우선 탐색): 큐를 활용해 단계별로 탐색하며 경로를 찾습니다.

2. 유효한 이동 조건

탐색을 진행할 때 다음 조건을 만족해야 합니다:

• 다음 칸이 게임판 내에 있어야 합니다.
• 이동할 수 있는 칸 수를 정확히 사용해야 합니다.

3. 탐색 종료 조건

• 목표 지점(-1)에 도달하면 탐색을 종료하고 성공을 출력합니다.
• 모든 경로를 탐색했음에도 도달하지 못하면 실패를 출력합니다.

⭐ 알고리즘 선택: DFS를 사용한 풀이

DFS는 간결하게 구현할 수 있어 작은 크기의 게임판에 적합합니다.

✅ 정답 코드

import java.util.Scanner;

public class Main {
    static int N;
    static int[][] board;
    static boolean[][] visited;
    static boolean success = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력 처리
        N = sc.nextInt();
        board = new int[N][N];
        visited = new boolean[N][N];

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

        // DFS 탐색 시작
        dfs(0, 0);

        // 결과 출력
        System.out.println(success ? "HaruHaru" : "Hing");

        sc.close();
    }

    // DFS 메서드
    static void dfs(int x, int y) {
        // 범위 밖이거나 이미 방문한 경우
        if (x < 0 || x >= N || y < 0 || y >= N || visited[x][y]) {
            return;
        }

        // 목표 지점에 도달한 경우
        if (board[x][y] == -1) {
            success = true;
            return;
        }

        // 현재 위치 방문 처리
        visited[x][y] = true;

        // 이동할 칸 수
        int jump = board[x][y];
        if (jump > 0) {
            // 오른쪽으로 이동
            dfs(x, y + jump);
            // 아래로 이동
            dfs(x + jump, y);
        }
    }
}

코드 설명

1. 입력 처리
   • 게임판의 크기 NNN과 각 칸의 값을 입력받습니다.
   • visited 배열을 사용해 방문 여부를 기록합니다.
2. DFS 구현
   • 현재 위치에서 이동 가능한 칸(오른쪽, 아래)을 재귀적으로 탐색합니다.
   • 방문한 칸은 다시 방문하지 않도록 처리합니다.
   • 목표 지점(-1)에 도달하면 success를 true로 설정하고 탐색을 종료합니다.
3. 결과 출력
   • success가 true이면 "HaruHaru", 아니면 "Hing"을 출력합니다.