글 읽기 - 자바 - 말이 되고픈 원숭이 시간초과 문제...

imsosleepy 6년 전 0

테스트케이스도 맞고

몇가지 테스트케이스 올려주신게 있어서 맞춰봐도 맞는데

제출하면 시간초과가 납니다.

분명 사소한 이유같은데 식견이 짧아서 정확한 문제를 모르겠네요..

조언 주시면 감사하겠습니다..ㅜ

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int M;
	static int N;
	static int K;
	static int[][] arr;
	static int[][] count;
	static boolean[][][] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		K = sc.nextInt();
		M = sc.nextInt();
		N = sc.nextInt();

		arr = new int[N][M];
		visited = new boolean[N][M][K+1];
		count = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

		int count = bfs();
		System.out.println(count);
	}

	public static int bfs() {
		visited[0][0][K] = true;
		Monkey start = new Monkey(0, 0, K);
		Queue<Monkey> q = new LinkedList<Monkey>();
		q.offer(start);
		
		int[] dx = { 1, -1, 0, 0 };
		int[] dy = { 0, 0, 1, -1 };
		int[] ddx = { 1, 2, 2, 1, -1, -2, -2, -1 };
		int[] ddy = { 2, 1, -1, -2, -2, -1, 1, 2 };
		
		while (!q.isEmpty()) {
			Monkey temp = q.poll();
			if (temp.x == M - 1 && temp.y == N - 1) {
				return count[temp.x][temp.y];
			}
			
			
			for (int i = 0; i < 4; i++) {
				int nx = temp.x + dx[i];
				int ny = temp.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= M || ny >= N)
					continue;
				if (visited[nx][ny][K] == true)
					continue;
				if (arr[nx][ny] == 1)
					continue;
				else {
					int nowKnight = temp.knight;
					visited[nx][ny][nowKnight] = true;
					Monkey newMon = new Monkey(nx, ny, nowKnight);
					count[nx][ny] = count[temp.x][temp.y] + 1;
					q.offer(newMon);
				}
			}
			
			if (temp.knight > 0) {
				
				for (int i = 0; i < 8; i++) {
					int nx = temp.x + ddx[i];
					int ny = temp.y + ddy[i];

					if (nx < 0 || ny < 0 || nx >= M || ny >= N)
						continue;
					if (visited[nx][ny][K] == true)
						continue;
					if (arr[nx][ny] == 1)
						continue;
					else {
						int nowKnight = temp.knight-1;
						visited[nx][ny][nowKnight] = true;
						count[nx][ny] = count[temp.x][temp.y] + 1;
						Monkey newMon = new Monkey(nx, ny, nowKnight);
						q.offer(newMon);
					}
				}

			} 
		}
		return -1;
	}

	public static class Monkey {
		int x;
		int y;
		int knight;

		public Monkey(int x, int y, int knight) {
			this.x = x;
			this.y = y;
			this.knight = knight;
		}
	}
}

bupjae 6년 전 0

if 문 안에서의 visited 배열의 3번째 index는 왜 항상 K인가요?

imsosleepy 6년 전 0

현재 위치에서 점프할 수 있는 회수인 temp.knight로 변경했는데도

여전히 시간초과가 나네요.

bupjae 6년 전 0

77번째 줄의 경우 방문여부를 체크해야 하는 곳은 temp.knight 가 아니라 nowKnight 로 보입니다.

imsosleepy 6년 전 0

답변 정말 감사드립니다.

답변해주신 정확히 그부분이 잘못되어있었네요.

그리고 가로, 세로의 입력도 잘못받고있었습니다.

생각보다 놓친 오류가 많았네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

자바 - 말이 되고픈 원숭이 시간초과 문제...

imsosleepy 6년 전 0

bupjae 6년 전 0

imsosleepy 6년 전 0

bupjae 6년 전 0

imsosleepy 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말