[Java] 백준 16173번 문제, 점프왕 쩰리(Small)

<문제 링크>

 

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

16173번: 점프왕 쩰리 (Small)

 

---

<풀이>

 

게임 조건은 다음과 같다.

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

 

이동 가능한 방향이 오른쪽과 아래 뿐이기 때문에 그래프 탐색을 진행할 때 오른쪽(r, c+1)과 아래(r+1, c)에 대해서만 확인하면 된다.

기본적인 BFS를 수행하되 다음 탐색 위치를 확인하는 보폭이 현재 위치의 값이기 때문에 r + board[r][c] 또는 c + board[r][c]가 board 범위 내에 있다면 que에 삽입하고, 그렇지 않다면 삽입하지 않고 다음 탐색을 진행하면 된다.

 

---

<코드>

board[][]: 보드, 맵

visited[][]: 방문 여부

success: 게임 승리 여부

---

import java.util.*;

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

        int N = sc.nextInt();
        int[][] board = new int[N][N];
        boolean[][] visited = new boolean[N][N];

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

        bfs(board, visited);

        sc.close();
    }

    static void bfs(int[][] board, boolean[][] visited){
        int len = board.length;
        boolean success = false;
        Queue<int[]> que = new LinkedList<>(); // 큐
        que.add(new int[] {0, 0}); // 시작 정점 추가

        while (!que.isEmpty()) {
            int[] focus = que.poll();
            int r = focus[0], c = focus[1];
            visited[r][c] = true;

            if(board[r][c] == -1){
                success = true;
                break;
            }

            int bottom = r + board[r][c], right = c + board[r][c];

            if (bottom < len && !visited[bottom][c]){
                que.add(new int[] {r + board[r][c], c});
                visited[bottom][c] = true;
            }
            if (right < len && !visited[r][right]){
                que.add(new int[] {r, c + board[r][c]});
                visited[r][right] = true;
            }
        }

        if(success){
            System.out.println("HaruHaru");
        }else{
            System.out.println("Hing");
        }
    }
}