글 읽기 - TC 돌려도 어디가 잘못된건지 모르겠습니다 도와주세요!!

huds093 5년 전 0

주어진 테스트케이스 뿐만 아니라 사이트에 올라와있는 테스트케이스들이랑 다른 분들이 오류발견했다고 하셨던 테스트케이스 모두 돌려봤는데 다 정답이 나옵니다. 제출하면 틀렸다고 나오네요ㅠㅠ

대체 어디가 잘못된걸까요?

import java.util.Scanner;
public class Main {

	static int[] map[], cnt[], visit[], S = new int[2], D = new int[2];
	static int[] water_x, water_y, q_x, q_y;
	static int r,c, front_w, rear_w, rear, front;
	final static int HEDGEHOG = 1, WATER = -1, ROCK = -2, CAVE = -3, LAND = 0;
	static boolean flag = false;
	
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);

		r = sc.nextInt();
		c = sc.nextInt();
		int k=0;

		map = new int[r][c];
		cnt = new int[r][c];
		q_x = new int[1000];
		q_y = new int[1000];
		water_x = new int[r*c];
		water_y = new int[r*c];
		visit = new int[r][c];
		
		for(int i=0; i<r; i++)
		{
			String a = sc.next();
			for(int j=0; j<c; j++)
			{
				char ch = a.charAt(j);
				if(ch == '*')
				{
					k = WATER;
					water_x[rear_w] = i;
					water_y[rear_w++] = j;
				}
				else if(ch == 'S')
				{
					S[0] = i;
					S[1] = j;
					k = HEDGEHOG;
				}
				else if(ch == 'D')
				{
					D[0] = i;
					D[1] = j;
					k = CAVE;
				}
				else if(ch == 'X')
					k = ROCK;
				else
					k = LAND;
				map[i][j] = k;
			}
		}

		if(bfs())
			System.out.println(cnt[D[0]][D[1]]);
		else
			System.out.println("KAKTUS");
	}

	public static boolean bfs()
	{
		//put start&water into queue
		q_x[rear] = S[0];
		q_y[rear++] = S[1];

		while(front < rear)
		{			
			int x = q_x[front];
			int y = q_y[front++];
			
			if(map[x][y] == HEDGEHOG || map[x][y] == LAND || map[x][y] == WATER)
			{
				check(x,y);
				visit[x][y] = 1;
			}
		}
		return flag;
			
	}

	public static void check(int x, int y)
	{
		int[] dir_x = {-1, 0, 1, 0}, dir_y = {0, 1, 0, -1};

		for(int i=front_w; i<rear_w; i++)
		{
			q_x[rear] = water_x[i];
			q_y[rear++] = water_y[i];
			front_w++;
		}
		
		for(int i=0; i<4; i++)
		{
			int tmp_x = x + dir_x[i];
			int tmp_y = y + dir_y[i];

			if(tmp_x<0 || tmp_y<0 || tmp_x>r-1 || tmp_y>c-1)
				continue;

			if(map[x][y] == HEDGEHOG || map[x][y] == LAND)
			{
				if(map[tmp_x][tmp_y] == LAND && visit[x][y] == 0)
				{
					cnt[tmp_x][tmp_y] = cnt[x][y] + 1;
					q_x[rear] = tmp_x;
					q_y[rear++] = tmp_y;
				}
				if(map[tmp_x][tmp_y] == CAVE)
				{
					cnt[tmp_x][tmp_y] = cnt[x][y] + 1;
					flag = true;
				}
			}
			else if(map[x][y] == WATER)
			{
				if(map[tmp_x][tmp_y] == LAND && visit[x][y] == 0)
				{
					map[tmp_x][tmp_y] = WATER;
					water_x[rear_w] = tmp_x;
					water_y[rear_w++] = tmp_y;
				}
			}
		}
	}
}

50 50
SD************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************

이런 큰 데이터를 넣으면 runtime err가 뜨게됩니다.

q_x = new int[1000];
q_y = new int[1000];

때문입니다.

R과 C의 범위를 살펴보면 50 이하니까

q_x = new int[2500];
q_y = new int[2500];

이런식 으로 짜줘야 합니다.

huds093 5년 전 0

댓글 감사합니다 :)

처음에 배열 초기화할 때 r*c*r 정도의 크기를 할당했었는데 아예 '틀렸습니다'라고 떠서 1000으로 바꿨더니 런타임에러가 납니다. 2500정도의 크기도 마찬가지구요ㅠㅠ

알고리즘 자체에 문제가 있는걸까요? ㅜㅠ

y305205 5년 전 0

찾아보니까 대회 공식 TC가 있네요

http://hsin.hr/coci/archive/2006_2007/

여기서 이 문제 찾아서 몇개 돌려보세여..

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

문제

문제

출처

ICPC

TC 돌려도 어디가 잘못된건지 모르겠습니다 도와주세요!!

huds093 5년 전 0

y305205 5년 전 0

huds093 5년 전 0

y305205 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말