[백준]16174: 점프왕 쩰리 - JAVA

[백준]16174: 점프왕 쩰리 

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

16174번: 점프왕 쩰리 (Large)

풀이

약간 변형된 BFS문제로 탐색을 하면서 오른쪽, 아래 방향 중에서 이동할 수 있는 방향으로 점프할 수 있는 칸 만큼 점프하며 이동한다. 

 

최소 값을 구하는 것이 아니기 때문에 DFS, BFS, 브루트포스 등 다양하게 풀 수 있다. 이동할 수 있는 방향 만큼 이동할 수 있다면 큐에 담아 이동하도록 구현하였다.

 

한 번 이동할 때마다 점프를 해서 이동하기 때문에 중간에 방향을 바꿀 수 없다. 즉, 현재 위치에 입력된 보드의 숫자 만큼 왼쪽 또는 아래쪽으로만 이동할 수 있다는 말이다. 이를 구현하기 위해 좌표를 이동할 때 이동 위치에 board의 현재 값 만큼 곱해주었다.

 

만약 현재 위치가 -1이 된다면, 마지막 노드에 도착한 것이므로 ""HaruHaru"를 출력해 주었다. BFS탐색을 하는 동안 마지막 노드에 도착하지 못해 탐색이 종료되었다면 "Hing"을 출력해 주었다.

 

코드

import java.util.*;
 
public class Main {
    
    static int n;
    static int[][] board;
    static int[] dx = {0, 1};
    static int[] dy = {1, 0};
    static boolean[][] visited;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        board = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = scan.nextInt();
            }
        }
 
        visited = new boolean[n][n];
        bfs();
    }
 
    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        visited[0][0] = true;
        q.offer(new int[] {0, 0});
        
        while(!q.isEmpty()) {
            int[] current = q.poll();
            int count = board[current[0]][current[1]];
 
            if(count == -1) {
                System.out.println("HaruHaru");
                return;
            }
 
            for(int i = 0; i < 2; i++) {
                int nx = current[0] + dx[i] * count;
                int ny = current[1] + dy[i] * count;
                if(nx >= 0 && ny >= 0 && nx < n && ny < n && visited[nx][ny] == false) {
                    visited[nx][ny] = true;
                    q.offer(new int[] {nx, ny});
                }
    
            }
        }
        System.out.println("Hing");
    }
}