글 읽기 - 런타임 에러 입니다. 여러 test_case 찾아서 넣었는데 정답이였습니다.

skfnxh0124 6년 전 0

DFS문제 처음 풀어서 나름 생각해보고 풀이했었습니다. 틀린 부분 찾으면 큐로 다시 풀려고 하는데요.

알고리즘은

1. 값이 1인 곳의 위치를 인덱스 구조체에 집어 넣습니다.

2. dfs를 인덱스 구조체에서 위치를 가져와서 실행합니다.

3. 이차원 배열 2개를 이용해서 하루가 지날 때마다 번갈아 가면서 저장합니다

4. 0 -> 1 익은 토마토 위치를 인덱스 구조체에 집어넣어서 날짜가 지나갔을때 시작점으로 선택합니다.

이렇게 코드를 구현했습니다... 구조체를 전역변수로 선언하고 동적할당하니 "중단점을 트리거했습니다" 오류가 나서

문제에서 주어진 가장 큰 값으로 인덱스 구조체 크기 결정했습니다.

이 코드에서 논리적인 오류가 있다면 이야기해주세요.

감사합니다.

#include<iostream>
#include <cstdio>

using namespace std;

struct index {
	int x=0;
	int y=0;
};
void dfs(int start_i, int start_j, int direct);

int cnt = 0;//Index 갯수
bool A1 = true; //순서 정하기
int M, N;
bool state_change = false;
int **arr1;
int **arr2;
int **check;

struct index *Index;
int main()
{
	
	scanf("%d%d", &M, &N);
	getchar();
	
	Index = new index[1000*1000];
	//index 받을 구조체.
	
	 arr1 = new int*[N];
	 arr2 = new int*[N];
	 check = new int*[N];
	
	for (int i = 0; i < N;i++)
	{
		arr1[i] = new int[M];
		arr2[i] = new int[M];
		check[i] = new int[M];
	}
	//배열에 저장.
	
	for (int i = 0; i < N;i++)
	{
		for (int j = 0; j < M; j++)
		{
			
			
			scanf("%d", &arr1[i][j]);
			
			arr2[i][j] = arr1[i][j];
			check[i][j] = 0;
			if (arr1[i][j] == 1)
			{
				Index[cnt].x = i;
				Index[cnt].y = j;
				cnt++;
			}
			
		}
		
	}
	
	//베열 값 저장하기. 및 index저장하기.
	int day_count = 1;
	int ans;
	int st = 0;
	while (true)
	{
		if (cnt == 0)
		{
			ans = -1;
			break;
		}
		else
		{
			
			int Cnt = cnt;
			for (st ; st < Cnt; st++)
			{
				dfs(Index[st].x, Index[st].y,0);
			}
			
			if (state_change == false)
			{
				if (day_count ==1)
				{
					int t = 0;
					for (int i = 0; i < N; i++)
						for (int j = 0; j < M; j++)
						{
							if (A1 == true)
							{
								if (arr2[i][j] == 0)
									t++;

							}
							else
							{
								if (arr1[i][j] == 0)
									t++;
							}

						}
					if (t == 0)
						ans = 0;
					else
						ans = -1;
					break;
				}
				else
				{
					int t = 0;
					for (int i = 0; i < N; i++)
						for (int j = 0; j < M; j++)
						{
							if (A1 == true)
							{
								if (arr2[i][j] == 0)
									t++;

							}
							else
							{
								if (arr1[i][j] == 0)
									t++;
							}

						}
					if (t == 0)
						ans = day_count-1;
					else
						ans = -1;
					break;
				}
			}
			else if (state_change == true)
			{
				if (A1 == true)
					A1 = false;
				else if(A1==false)
					A1 = true;
				day_count++;
				state_change = false;
				
			}

		}

	}
	cout << ans << endl;
	
	
}

void dfs(int start_i, int start_j,int direct)
{
	//direct 0 초기, 1 왼쪽 2 오른쪽 3 아래 4 위
	if (start_i < 0 || start_i >= N)
		return;
	if (start_j < 0 || start_j >= M)
		return;
	
	if (A1 == true)
	{
		
		if (check[start_i][start_j] == 0)
		{
			check[start_i][start_j] = 1;
			
			if (arr1[start_i][start_j] == -1)
				return;
			else if (arr1[start_i][start_j] == 0)
			{
				arr2[start_i][start_j] = 1;
				Index[cnt].x = start_i;
				Index[cnt].y = start_j;
				cnt++;
				check[start_i][start_j] = 0;
				state_change = true;
				
			}
			else if (arr1[start_i][start_j] == 1)
			{
				if (arr2[start_i][start_j] != 1)
					arr2[start_i][start_j] = 1;
				if (direct == 0)
				{
					dfs(start_i - 1, start_j, 2);
					dfs(start_i, start_j - 1, 3);
					dfs(start_i + 1, start_j, 1);
					dfs(start_i, start_j + 1, 4);
				}
				else if (direct == 1)
				{

					dfs(start_i, start_j - 1, 3);
					dfs(start_i + 1, start_j, 1);
					dfs(start_i, start_j + 1, 4);
				}
				else if (direct == 2)
				{
					dfs(start_i - 1, start_j, 2);
					dfs(start_i, start_j - 1, 3);

					dfs(start_i, start_j + 1, 4);
				}
				else if (direct == 3)
				{
					dfs(start_i - 1, start_j, 2);
					dfs(start_i, start_j - 1, 3);
					dfs(start_i + 1, start_j, 1);

				}
				else if (direct == 4)
				{
					dfs(start_i - 1, start_j, 2);

					dfs(start_i + 1, start_j, 1);
					dfs(start_i, start_j + 1, 4);
				}

			}
			
		}

			
		
		

	}
	else if (A1 == false)
	{
		
		if (check[start_i][start_j] == 0)
		{
			check[start_i][start_j] = 1;
			
			if (arr2[start_i][start_j] == -1)
				return;
			else if (arr2[start_i][start_j] == 0)
			{
				arr1[start_i][start_j] = 1;
				state_change = true;
				Index[cnt].x = start_i;
				Index[cnt].y = start_j;
				cnt++;
				check[start_i][start_j] = 0;
			}
			else if (arr2[start_i][start_j] == 1)
			{
				if (arr1[start_i][start_j]==0)
					arr1[start_i][start_j] = 1;

				if (direct == 0)
				{
					dfs(start_i - 1, start_j, 2);
					dfs(start_i, start_j - 1, 3);
					dfs(start_i + 1, start_j, 1);
					dfs(start_i, start_j + 1, 4);
				}
				else if (direct == 1)
				{

					dfs(start_i, start_j - 1, 3);
					dfs(start_i + 1, start_j, 1);
					dfs(start_i, start_j + 1, 4);
				}
				else if (direct == 2)
				{
					dfs(start_i - 1, start_j, 2);
					dfs(start_i, start_j - 1, 3);

					dfs(start_i, start_j + 1, 4);
				}
				else if (direct == 3)
				{
					dfs(start_i - 1, start_j, 2);
					dfs(start_i, start_j - 1, 3);
					dfs(start_i + 1, start_j, 1);

				}
				else if (direct == 4)
				{
					dfs(start_i - 1, start_j, 2);

					dfs(start_i + 1, start_j, 1);
					dfs(start_i, start_j + 1, 4);
				}
			}
			
		}

	}	
}

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

문제

문제

출처

ICPC

런타임 에러 입니다. 여러 test_case 찾아서 넣었는데 정답이였습니다.

skfnxh0124 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말