백준 16173번 : 점프왕 쩰리 (Small) (C 언어)

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

16173번: 점프왕 쩰리 (Small)

Code:

#include <stdio.h>
 
int arr[5][5] = { 0, };
int n;
int flag = 0;
int dx[] = { 0,1 };
int dy[] = { 1,0 };
 
void dfs(int y, int x) {
    
    int jump = arr[y][x];
    if (jump == 0)
    {
        return;
    }
    for (int i = 0; i < 2; i++)
    {
        int x_n = x + dx[i] * jump;
        int y_n = y + dy[i] * jump;
        if (y >= n || x >= n)
            continue;
        if (y == n - 1 && x == n - 1) {
            flag = 1;
            return;
        }
        dfs(y_n, x_n);
    }
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    dfs(0, 0);
 
    if (flag == 1)
        printf("HaruHaru");
    else
        printf("Hing");
 
    return 0;
}

문제 설명

게임 캐릭터 '쩰리'는 점프하는 것을 좋아하는 젤리입니다. 그러나 단순한 점프만으로는 지루함을 느낀 '쩰리'는 새로운 점프 게임을 찾고 있습니다. 이 게임은 특정한 규칙에 따라 진행되며, '쩰리'가 최종 단계에 도달하여 승리할 수 있는지를 판단하는 것이 목표입니다.

게임 구역은 가로와 세로의 칸 수가 같은 정사각형으로 이루어져 있습니다. '쩰리'는 이 정사각형 구역 내에서만 움직일 수 있으며, 이 구역 외부로 나가게 되면 게임에서 패배합니다. '쩰리'의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위에 위치한 칸입니다. '쩰리'는 오른쪽과 아래쪽으로만 이동할 수 있으며, 한 번에 이동할 수 있는 칸의 수는 현재 밟고 있는 칸에 쓰여 있는 수 만큼입니다. 게임에서의 승리 조건은 '쩰리'가 가장 오른쪽 맨 아래 칸에 도달하는 것입니다.

이제 주어진 코드를 통해 게임 구역에서 '쩰리'가 최종 단계에 도달할 수 있는지를 판단해보겠습니다.

코드 설명

주어진 코드는 C 언어로 작성되었으며, 주어진 게임 구역에서 깊이 우선 탐색(DFS) 알고리즘을 활용하여 '쩰리'가 최종 단계에 도달할 수 있는지를 확인합니다.

주요 변수

• arr: 2차원 배열로 게임판의 구역 정보를 저장합니다.
• n: 게임 구역의 크기 (가로, 세로의 칸 수)를 나타냅니다.
• flag: '쩰리'의 승리 여부를 나타내는 플래그 변수입니다.
• dx, dy: '쩰리'가 오른쪽과 아래쪽으로 이동하기 위한 방향을 나타내는 배열입니다.

주요 함수

• dfs(int y, int x): 깊이 우선 탐색(Depth-First Search)을 수행하는 함수로, '쩰리'의 이동을 모사합니다.

실행 흐름

1. 입력으로 게임 구역의 크기와 각 칸에 쓰여진 수를 받습니다.
2. 시작 위치에서 dfs 함수를 호출하여 '쩰리'의 이동을 탐색하고 최종 단계에 도달할 수 있는지 확인합니다.
3. 승리 여부에 따라 "HaruHaru" 또는 "Hing"을 출력합니다.

이제 주어진 코드를 통해 게임 구역에서 '쩰리'가 최종 단계에 도달할 수 있는지를 판단하고 결과를 출력합니다.