백준 1600 말이 되고픈 원숭이 - JAVA

문제

입/출력

이 문제를 푸는데 3시간이 걸렸다. 혼자 푼 건 아니고 로직은 맞는데 메모리 초과가 나서 구선생님의 도움을 받았다.

배열로는 메모리 초과가 뜨는데 Monkey 객체로 푸니까 문제가 풀렸다. 마치 int를 long으로 선언해서 맞은 기분이랄까?

 

6%에서 자꾸 시간 초과, 메모리 초과, 틀렸습니다가 떠가지고 너무 당황스러웠다. 

 

문제 풀이의 핵심은 다음과 같다.

1. 최소한의 동작으로 목적지 도달 -> BFS(너비 우선 탐색)
2. 벽이 있는 곳은 가지 못함
3. 쓸모없는 탐색, 함수 호출 제거
4. 배열이 아닌 객체 선언 및 생성을 통한 메모리 초과 해결

 

제가 정답률 하락에 기여했슴다!

 

package boj;

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

public class Boj_1600 {
	static int[][] monkeyD = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
	static int[][] horseD = { { -2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 } }; // 좌상
	static int[][] map;
	static boolean[][][] visited;
	static int answer = -1;
	static int K, W, H;

	static class Monkey {
		int r, c, cnt, jump;

		Monkey(int r, int c, int cnt, int jump) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.jump = jump;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		StringTokenizer stz = new StringTokenizer(br.readLine());
		W = Integer.parseInt(stz.nextToken());
		H = Integer.parseInt(stz.nextToken());

		map = new int[H][W];
		visited = new boolean[H][W][K + 1];
		for (int i = 0; i < H; i++) {
			stz = new StringTokenizer(br.readLine());
			for (int j = 0; j < W; j++) {
				map[i][j] = Integer.parseInt(stz.nextToken());
			}
		}

		Queue<Monkey> q = new LinkedList<>();
		visited[0][0][0] = true;
		q.offer(new Monkey(0, 0, 0, 0));
		bfs(q, H - 1, W - 1);

		System.out.println(answer);
	}

	private static void bfs(Queue<Monkey> q, int targetR, int targetC) {

		while (!q.isEmpty()) {
			Monkey temp = q.poll();

			if (temp.r == targetR && temp.c == targetC) {
				answer = temp.cnt;
				return;
			}

			for (int i = 0; i < monkeyD.length; i++) {
				int nr = temp.r + monkeyD[i][0];
				int nc = temp.c + monkeyD[i][1];

				if (!check(nr, nc))
					continue;

				if (visited[nr][nc][temp.jump])
					continue; // 방문한 적 있니?
				visited[nr][nc][temp.jump] = true;
				q.offer(new Monkey(nr, nc, temp.cnt + 1 , temp.jump));
			}

			if (temp.jump == K)
				continue;

			for (int i = 0; i < horseD.length; i++) {
				int nr = temp.r + horseD[i][0];
				int nc = temp.c + horseD[i][1];

				if (!check(nr, nc))
					continue;
				if (visited[nr][nc][temp.jump + 1])
					continue; // 방문한 적 있니?

				visited[nr][nc][temp.jump + 1] = true;
				q.offer(new Monkey(nr, nc, temp.cnt + 1, temp.jump + 1));
			}

		}
	}

	private static boolean check(int nr, int nc) {
		return 0 <= nr && nr < H && 0 <= nc && nc < W && map[nr][nc] != 1;
	}
}