백준 16174 - 점프왕 쩰리 (Large)

Java

16174 번 - 점프왕 쩰리 (Large)

문제

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

‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

접근 방법

젤리의 정보 (행, 열, 현재 점프할 수 있는 거리)를 저장할 객체를 선언한다.
BFS를 사용하기로 하여, 점프할 젤리들의 정보를 담을 Queue를 선언하였다.
젤리 하나를 poll한 다음, 오른쪽 / 아래를 탐색하여 거리 만큼 점프를 하여 갈 수 있으면 해당 위치와 그 위치의 거리 값을 queue에 넣어 다음에 점프할 젤리로 저장한다.

bfs를 반복하다, 만약 위치하는 지점에 도달하면 HaruHaru를 리턴

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[][] map;
	static boolean[][] vis;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	
    	map = new int[n][n];
    	vis = new boolean[n][n];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
    	boolean isArrived = false;
    	
		// ---------------- BFS 시작 ---------------
    	int[] dy = {1,0};
    	int[] dx = {0,1};
    	
    	Queue<Jelly> queue = new LinkedList<>();
    	queue.add(new Jelly(0, 0, map[0][0]));
    	
    	Jelly j;
    	int y, x, v, ny, nx;
    	end : while(!queue.isEmpty()) {
    		j = queue.poll();
    		y = j.y;
    		x = j.x;
    		v = j.v;
    		
    		for(int i = 0; i < 2; i++) {
    			ny = y + v * dy[i];
    			nx = x + v * dx[i];
    			// 목표한 위치에 도달 했으면
    			if(isIn(ny, nx) && map[ny][nx] == -1) {
    				isArrived = true;
    				break end;
    			}
    			// 방문하지 않았으며, map 안에 있으면
    			if(isIn(ny, nx) && !vis[ny][nx]) {
    				vis[ny][nx] = true;
    				queue.add(new Jelly(ny,nx,map[ny][nx]));
    			}
    		}
    	}
		// ---------------- BFS 끝 ---------------
		
    	if(isArrived)
    		System.out.println("HaruHaru");
    	else
    		System.out.println("Hing");
    	br.close();
	}

	static class Jelly{
		int y,x,v;

		public Jelly(int y, int x, int v) {
			super();
			this.y = y;
			this.x = x;
			this.v = v;
		}		
	}
	
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= n)
            return false;
        return true;
    }
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점

없습니다.