[백준] 1600번:말이 되고픈 원숭이 (Java 자바)

문제

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

1600번: 말이 되고픈 원숭이

 

풀이 및 소스코드

 

왜 말이 되고픈지 모르겠당..

넘 어려웠다.

k별로도 방문체크를 해줘야했기때문에 인생 최초로 3차배열에 방문표시를 해줬다.

이 때문에 푸는 게 오래걸린 것 같다.

 

처음에 dfs로 풀려고 했으나, 시간초과가 났다.

bfs로 바꿨는데 6%에서 자꾸 틀렸다고 했다.

현재 좌표에 대한 k_cnt 값을 고려해주지 않고, 그저 k 만 넘지 않았으면 시간 비교를 해줬기 때문에 논리적 오류가 생긴 것 같다.

 

6%에서 틀렸습니다. 가 뜨는 사람들은 봐야할 반례

1
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0

 

정답 : 6

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {
	static int n,m,k;
	static int[][] map;
	static boolean[][][] v;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		k = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		
		v = new boolean[n][m][k+1]; //k카운트에 대해 방문표시 할 배열. n행 m열 말의 이동을 k번 했다.
		
		map = new int[n][m];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		if(n==1&&m==1) {
			System.out.println("0");
			System.exit(0);
		}
		
		System.out.println(go_monkey());
	}
	
	public static int go_monkey() {
		PriorityQueue<node> q = new PriorityQueue<>();
		int[] dx = {1, 0, -1, 0, -2, -1, 1, 2, -2, -1, 1, 2};
		int[] dy = {0, 1, 0, -1, 1, 2, 2, 1, -1, -2, -2, -1};
		//4~11 : 말처럼
		
		q.add(new node(0, 0, 0, 0));
		v[0][0][0] = true;
		
		while(!q.isEmpty()) {
			node now = q.poll();
			int x = now.x;
			int y = now.y;
			int time = now.time;
			int k_cnt = now.k_cnt;
			if(x==n-1&&y==m-1) return time;
			for(int i=0;i<12;i++) {
				int nowx = x+dx[i];
				int nowy = y+dy[i];
				if(nowx<0||nowy<0||nowx>=n||nowy>=m) continue;
				if(map[nowx][nowy] == 1) continue;
				if(i>=4&&k_cnt>=k) break;
				if(i>=4) { 
					if(!v[nowx][nowy][k_cnt+1]) {
						q.add(new node(nowx, nowy, time+1, k_cnt+1));
						v[nowx][nowy][k_cnt+1] = true;
					}
				}else {
					if(!v[nowx][nowy][k_cnt]) {
						v[nowx][nowy][k_cnt] = true;
						q.add(new node(nowx, nowy, time+1, k_cnt));
					}
				}
			}
		}
		return -1;
	}
}

class node implements Comparable<node>{
	int x,y,time,k_cnt;

	public node(int x, int y, int time, int k_cnt) {
		super();
		this.x = x;
		this.y = y;
		this.time = time;
		this.k_cnt = k_cnt;
	}

	@Override
	public int compareTo(node o) {
		if(o.time==this.time) {
			return this.k_cnt-o.k_cnt;
		}
		return this.time-o.time;
	}
	
}