Contents

백준 16173번, 점프왕 쩰리 (with. Java)

   Mar 2, 2025     4 min read

백준 16173번, 점프왕 쩰리 (with. Java) 에 대하여 알아본 글입니다.

코딩 테스트 문제를 풀며, 풀었던 문제에 대한 회고와 다른 풀이 방법을 알아보며, 알아가고자 합니다.

문제에 대해 먼저 알아보겠습니다.

문제

‘쩰리’는 점프하는 것을 좋아하는 젤리다.

단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다.

새로운 점프 게임의 조건은 다음과 같다.

‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다.

‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.

‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다.

다른 출발점에서는 출발하지 않는다.

‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다.

위쪽과 왼쪽으로는 이동할 수 없다.

‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.

‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다.

칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.

새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다.

하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다.

‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다.

‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

입력

입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.

입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.

게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

출력

‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.

문제 풀이

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

public class Main {
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, 1}, dy = {1, 0};

    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];
        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(0, 0);

        System.out.println("Hing");
    }

    private static void dfs(int X, int Y){
        if(map[X][Y] == -1){
            System.out.println("HaruHaru");
            System.exit(0);
        }
        for(int i = 0; i < 2; i++){
            int nx = X + dx[i] * map[X][Y];
            int ny = Y + dy[i] * map[X][Y];

            if(nx >= N || ny >= N || visited[nx][ny]) continue;
            visited[nx][ny] = true;
            dfs(nx, ny);
        }
    }
}

풀이 설명

이 코드는 깊이 우선 탐색(DFS)을 활용하여 N×N 크기의 2차원 배열을 탐색하는 프로그램입니다.

목표는 좌상단 (0,0)에서 출발하여 우하단에 위치한 -1 값에 도달할 수 있는지를 확인하는 것입니다.

먼저, BufferedReader를 이용하여 정수 N을 입력받고, 이를 기반으로 크기가 N×N인 map 배열과 방문 여부를 저장하는 visited 배열을 생성합니다.

이후, 반복문을 통해 N개의 줄에 걸쳐 입력된 값을 StringTokenizer를 사용하여 map 배열에 저장합니다.

dfs(0, 0)을 호출하여 깊이 우선 탐색을 시작합니다.

dfs 메서드는 현재 위치 (X, Y)를 기준으로 탐색을 진행하며, 현재 위치의 값이 -1이면 목표 지점에 도달한 것이므로 "HaruHaru"를 출력하고 프로그램을 즉시 종료합니다.

탐색은 오른쪽(dx = {0, 1})과 아래쪽(dy = {1, 0}) 두 방향으로만 이루어지며, 현재 위치 map[X][Y]의 값만큼 이동할 수 있습니다.

새로운 좌표 (nx, ny)를 계산한 후,

  • 배열 범위를 벗어나는 경우
  • 이미 방문한 위치인 경우

위의 조건에 해당하면 탐색을 중단하고, 아니라면 해당 위치를 방문 처리한 후 dfs(nx, ny)를 재귀적으로 호출하여 탐색을 이어갑니다.

모든 탐색이 종료될 때까지 -1에 도달하지 못했다면 "Hing"을 출력하여 목표 지점에 도달할 수 없음을 나타냅니다.

이 알고리즘은 DFS를 활용하여 경로를 탐색하며, 방문했던 위치를 체크하여 중복 탐색을 방지하는 방식으로 구현되었습니다.