BOJ_16173 : 점프왕 쩰리 (Small)

👉 문제링크

16173번: 점프왕 쩰리 (Small)

---

---

🔸 문제 분석 🔸

• n x n 크기의 게임판에서 왼쪽 위 (0,0)부터 탐색하며 오른쪽 아래 (n-1, n-1)에 도착할 수 있는지 결과를 출력한다.
  • 현재 게임판 위치의 값만큼 오른쪽 혹은 아래쪽 한 방향으로 정확히 그 값만큼 움직일 수 있다.
  • 판을 넘어가면 안된다.

🔸 코드 🔸

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++){                // 입력 받기
            for (int j = 0; j < n; j++){
                arr[i][j] = sc.nextInt();
            }
        }

        boolean[][] visit = new boolean[n][n];      // 해당 좌표 방문 여부
        Queue<Pair> queue = new LinkedList<>();     // 큐
        queue.add(new Pair(0,0));             // 큐의 첫 값

        boolean goal = false;
        while (!queue.isEmpty()) {                  // 큐 반복 계산
            Pair p = queue.poll();
            visit[p.x][p.y] = true;
            int len = arr[p.x][p.y];

            if (len == -1){
                goal = true;
                break;
            }

            if (p.x+len < n && visit[p.x+len][p.y] == false){
                queue.add(new Pair(p.x+len, p.y));
            }
            if (p.y+len < n && visit[p.x][p.y+len] == false){
                queue.add(new Pair(p.x, p.y+len));
            }
        }
        if (goal) {
            System.out.println("HaruHaru");
        } else {
            System.out.println("Hing");
        }
    }
    private static class Pair {
        int x, y;
        private Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

🔸 코드 해석 🔸

• BFS를 사용해서 게임판을 탐색했다.
  • 큐의 원소는 Pair클래스를 직접 만들어 x, y 좌표값을 사용했다.
  • 오른쪽 혹은 아래쪽으로 움직였을때 게임판 내의 범위인지, 방문했던 좌표인지 확인한다.
  • 바닥의 값이 -1인 좌표에 도착하면 성공이고, 큐의 원소가 하나도 남지 않을때 까지 도착하지 못하면 실패이다.

---

🔸 end 🔸

• BFS를 오랜만에 연습해 볼 수 있었던 좋은 문제였다.
  • visit을 사용하는걸 깜빡해서 1회 메모리 초과가 났었다.
• n의 범위가 3까지이므로 Brute Force나 DFS등 연습해 보기 쉬운 문제이다.