09 Jun 2023

[Java] 백준 16174번: 점프왕 쩰리 (Large)

16174

풀이 방법

쩰리씨를 오른쪽 아래 -1로 표시된 곳까지 보내는 문제이다. 이 문제에서 중요한 점은 두 가지다.

이동할 수 있는 칸 수는 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다.
- 오른쪽 아래 / 아래 오른쪽 방식으로 갈 수 없고 무조건 한 방향으로만 가야 한다.
칸에 쓰여있는 수가 0일 수도 있다.
- 0일 경우에는 제자리 뛰기를 무한 반복해 시간 초과가 날 수 있으므로 BFS에서도 방문 배열이 필수적으로 요구된다.

이 두 가지만 체크한다면 BFS/DFS 둘 다 풀 수 있을 것 같다. 나는 BFS로 해결했다.

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16174_점프왕_쩰리 {
	static int[] dr = {0,1};
	static int[] dc = {1,0};
	static int[][] MAP;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		MAP = new int[N][N];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				MAP[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		bfs(0, 0, N);
	}
	
	private static void bfs(int sr, int sc, int N) {
		Queue<int[]> q = new LinkedList<>();
		boolean[][] v = new boolean[N][N];
		q.add(new int[] {sr, sc});
		v[sr][sc] = true;
		
		while(!q.isEmpty()) {
			int[] poll = q.poll();
			
			if(MAP[poll[0]][poll[1]] == -1) {
				System.out.println("HaruHaru");
				return;
			}
			
			for(int d=0; d<2; d++) {
				int nr = poll[0] + MAP[poll[0]][poll[1]] * dr[d];
				int nc = poll[1] + MAP[poll[0]][poll[1]] * dc[d];
				
				if(nr>=0 && nr<N && nc>=0 && nc<N && !v[nr][nc]) {
					v[nr][nc] = true;
					q.add(new int[] {nr, nc});
				}
			}
		}
		System.out.println("Hing");
	}

}

Thank You For Reading

점점 강해지고 있습니다.