글 읽기 - 100% 에서 틀렸습니다. 확인 해주 실 수 있으신가요

taxol1203 3년 전 0

원숭이가 점프하는 횟수와 움직임의 횟수를 나타내는 3차원 배열 `move`를 통하여 문제를 풀어보았습니다.

먼저 해결하신 분들의 풀이와의 차이라면, queue에 이동 횟수를 저장하고, bfs가 끝닌 이후 move[k][n-1][m-1]에 저장된 마지막 도착지에 있는 값들 중 제일 작은 값을 출력하도록 하였는데, 100%를 찍고 계속 틀리니 답답합니다.

혹시 반례나, 코드의 오류 지적해주시면 감사드립니다

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

public class Main {
	static int n, m, result = Integer.MAX_VALUE, k;
	static int[][] board;
	static int[][][] move;
	static boolean visited[][][];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	k = stoi(br.readLine());
    	
    	stk = new StringTokenizer(br.readLine());
    	m = stoi(stk.nextToken());
    	n = stoi(stk.nextToken());
    	board = new int[n][m];
    	move = new int[k + 1][n][m];
    	visited = new boolean[k+1][n][m];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			board[i][j] = stoi(stk.nextToken());
    		}
    	}
    	for(int i = 0; i < k + 1; i++) {
    		visited[i][0][0] = true;
    	}
    	
    	bfs();
    	
    	for(int i = 0; i < k + 1; i++) {
    		if(visited[i][n-1][m-1]) {
    			result = Math.min(result, move[i][n-1][m-1]);
    		}
    	}
    	
    	
    	if(result != Integer.MAX_VALUE)
    		System.out.println(result);
    	else
    		System.out.println(-1);
    	
    	br.close();
	}
	// 우 하 상 좌
	static int[] dy = {0, 1, -1, 0};
	static int[] dx = {1, 0, 0, -1};
	
	// 말이 점프하는 방향, 숫자는 점프 위치가 시계 방향으로 나타내었을 때, 1~8
	// 3 4 1 2 5 6 7 8
	static int[] hy = {1, 2, -2, -1, 2, 1, -1, -2};
	static int[] hx = {2, 1, 1, 2, -1, -2, -2, -1};
	
	static void bfs() {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(k, 0, 0));
		// lv은 몇 번째 움직임인지 나타냄
		int y, x, z, ny, nx, find = 1, cnt = 0, lv = 1;
		while(!q.isEmpty()) {
			// 몇 번째의 움직임인지 나타내기 위한 반복문
			while(find-- != 0) {
				Point p = q.poll();
				y = p.y;
				x = p.x;
				z = p.z;
				for(int i = 0; i < 4; i++) {
					ny = y + dy[i];
					nx = x + dx[i];
					if(isIn(ny,nx) && board[ny][nx] != 1 && !visited[z][ny][nx]) {
						move[z][ny][nx] = lv;		
						visited[z][ny][nx] = true;
						q.add(new Point(z, ny, nx));
						cnt++;
					}
				}
				// 말 점프
				if(z > 0) {
					for(int i = 0; i < 8; i++) {
						ny = y + hy[i];
						nx = x + hx[i];
						if(isIn(ny,nx) && board[ny][nx] != 1 && !visited[z][ny][nx]) {
							move[z - 1][ny][nx] = lv;
							visited[z - 1][ny][nx] = true;
							q.add(new Point(z - 1, ny, nx));
							cnt++;
						}
					}
				}
			}
			lv++;	// 다음 움직임
			find = cnt;
			cnt = 0;
		}
		
	}
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
    
	static class Point{
		int z,y,x;


		public Point(int z, int y, int x) {
			super();
			this.z = z;
			this.y = y;
			this.x = x;
		}


		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("Point [y=").append(y).append(", x=").append(x).append(", z=").append(z).append("]");
			return builder.toString();
		}
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

uhuru0614 3년 전 1

83라인

if(isIn(ny,nx) && board[ny][nx] != 1 && !visited[z][ny][nx])

if(isIn(ny,nx) && board[ny][nx] != 1 && !visited[z-1][ny][nx])

taxol1203 3년 전 0

어처구니 없는 실수였습니다. 감사합니다

iknowkis 1년 전 1

W와 H가 1인 테스트 케이스가 있습니다.

1
1 1
0

// Ans: 0

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

문제

문제

출처

ICPC

100% 에서 틀렸습니다. 확인 해주 실 수 있으신가요

taxol1203 3년 전 0

uhuru0614 3년 전 1

taxol1203 3년 전 0

iknowkis 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말