"백준 16173번: 점프왕 쩰리 (Small)" 문제를 풀어보았다!

🤔 문제 설명

‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.

1. ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
2. ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
3. ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
4. ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
5. ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.

새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

---

✅ 나의 풀이

⛰️ 실패작1

보자마자 이 문제는 저번에 풀었던 DFS문제와 비슷하다는걸 깨달았다. 그래서 방향이동을 배열로 만들어 반복문을 통해 이동하고 재귀호출하는 방식으로 만들었다.

#include <iostream>
#include <vector>
using namespace std;

int N;
int dx[2] = {0, 1};
int dy[2] = {1, 0};

vector<vector<int>> board;
string answer;

void DFS(int x, int y) {
    if (x >= N || y >= N) {
        return;
    }

    int jump = board[x][y];
    if (jump == -1) {
        answer = "HaruHaru";
        return;
    }

    board[x][y] = 0;

    for (int i = 0; i < 2; i++) {
        int nx = x + dx[i] * jump;
        int ny = y + dy[i] * jump;

        if (nx < N && ny < N && board[nx][ny] != -1) { // 이동할 수 있는 범위 내에서만 재귀 호출
            DFS(nx, ny);
        }
    }
}

int main() {
  
    cin >> N;

    for (int i = 0; i < N; i++) {
        vector<int> row;
        
        for (int j=0;j<N;j++) {
            int num;
            cin >> num;
            row.push_back(num);
         }

         board.push_back(row);
     }

     answer = "Hing";
     DFS(0, 0);

     cout << answer;

     return 0;
}

➡️ " ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다. " 라는 내용을 빼고 만들었다.

⛰️ 실패작2

문제를 다시 읽고 칸에 쓰인 숫자 만큼 이동하도록 변경하였다. 또한 코드 최적화까지 진행하였다.

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<vector<int>> board;
string answer;

void DFS(int x, int y)
{
    if (x > N || y > N)
    {
        return;
    }

    int jump = board[x][y];
    if (jump == -1)
    {
        answer = "HaruHaru";
        return;
    }

    // 오른쪽으로 점프
    int nx = x + jump;
    int ny = y;

    DFS(nx, ny);

    // 아래쪽으로 점프
    nx = x;
    ny = y + jump;

    DFS(nx, ny);
}

int main()
{

    cin >> N;

    board.resize(N, vector<int>(N));

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
        }
    }

    answer = "Hing";
    DFS(0, 0);

    cout << answer;

    return 0;
}

➡️ 런타임 오류(OutOfBounds) 발생

😂 성공

방문여부를 체크하는 2차원 배열을 만들어서 확인하고 이동할때 이동한 좌표값이 범위내인지 확인하는 부분을 추가하였다!

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<vector<int>> board;
vector<vector<bool>> visited;
string answer;

void DFS(int x, int y)
{
    if (x >= N || y >= N)
    {
        return;
    }

    int jump = board[x][y];
    if (jump == -1)
    {
        answer = "HaruHaru";
        return;
    }

    // 오른쪽으로 점프
    int nx = x + jump;
    int ny = y;

    if (nx >= 0 && nx < N && !visited[nx][ny]) { // 아직 방문하지 않은 경우에만 재귀 호출
        visited[nx][ny] = true; // 방문 체크
        DFS(nx, ny);
    }

    // 아래쪽으로 점프
    nx = x;
    ny = y + jump;

    if (ny >= 0 && ny < N && !visited[nx][ny]) { // 아직 방문하지 않은 경우에만 재귀 호출
        visited[nx][ny] = true; // 방문 체크
        DFS(nx, ny);
   }
}

int main()
{

    cin >> N;

    board.resize(N, vector<int>(N));
    visited.resize(N, vector<bool>(N, false)); // 초기값은 모두 false로 설정

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
        }
    }

    answer = "Hing";
    visited[0][0] = true; // 시작 위치(0, 0)를 방문했다고 표시
    DFS(0, 0);

    cout << answer;

    return 0;
}