[BOJ] 16173: 점프왕 쩰리(Small) (JAVA)

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

 

 

풀이

 

BFS로 풀었습니다.

처음엔 최단 거리를 구하라는 건줄 알고 visited 배열을 int 배열로 만들었는데 그냥 유무만 검증하면 됐군요ㅎㅎ

 

2
0 0
0 -1

 

메모리 초과가 발생한다면 위 반례를 사용해보시길!

 

 

전체코드

package 백준renew;

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

public class 실버4_16173_점프왕쩰리 {
	static int N;
	static int goX[] = {0, 1};
	static int goY[] = {1, 0};
	static int map[][];
	static int visited[][];
	static class Node{
		int x;
		int y;
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		visited = 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());
			}
		}
		
		Go();
		
		if(visited[N-1][N-1] == 0) {
			sb.append("Hing");
		}else {
			sb.append("HaruHaru");
		}
		
		bw.write(sb.toString());
		bw.close();
		
	}
	public static void Go() {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(0, 0));
		visited[0][0] = 1;
		
		while(!queue.isEmpty()) {
			Node n = queue.poll();
			
			for(int i=0; i<2; i++) {
				int newX = n.x + goX[i]*map[n.x][n.y];
				int newY = n.y + goY[i]*map[n.x][n.y];
				
				if(newX < 0 || newX >= N || newY < 0 || newY >= N || visited[newX][newY]!=0) {
					continue;
				}
				
				queue.offer(new Node(newX, newY));
				visited[newX][newY] = visited[n.x][n.y] + 1;
				
				if(newX == N-1 && newY == N-1) {
					return;
				}
			}
		}
	}
}