글 읽기 - 토마토 어디가 틀렸는지 알려주실수 있나요?..

devbelly 4년 전 0

접근 방법이 아에 틀렸나요? ㅜ 문제 테스트 케이스들은 모두 통과했는데 가차없이 틀렸습니다가 뜨네요

초반 토마토가 여러개일 경우 동시에 bfs를 진행하기 위해 memo 배열을 선언하여 초반 토마토의 좌표를 저장한후

bfs에서 한개의 토마토를 익게하면 또 bfs를 호출(메모해놓은 초반토마토 좌표) 하는 식으로 코드를 작성했습니다.

#include <stdio.h>
#include <string.h>

int box[1000 + 2][1000 + 2];
int queue[2][1000001];
int distance[1000 + 2][1000 + 2];
int visited[1000 + 2][1000 + 2];
int memo[2][1000001];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0 ,0 ,1,-1 };
int front, rear;
int M, N;
int cnt=-1;
void bfs(int col, int row)
{
	cnt--; // 다른 시작점에서 bfs를 수행하기 위해 cnt 하나 감소. cnt는 memo 가면 찾을수 있음
	queue[0][rear] = col;
	queue[1][rear] = row; // 큐에 col , row 담기
	rear++;
	distance[col][row] = 0; // 거리
	visited[col][row] = 1; // 방문체크

	while (front < rear) //큐에 내용물이 있다면
	{
		int co = queue[0][front]; // pop 과정
		int ro = queue[1][front];
		front++;

		for (int i = 0;i < 4;i++) // 인접한 좌표 확인용
			if (box[co + dy[i]][ro + dx[i]] == 0&& visited[co + dy[i]][ro + dx[i]]==-1) // 박스에 익지 않은 토마토( 정수 0)가 있으며
																						// 아직방문하지 않았다면
			{
				queue[0][rear] = co + dy[i]; //큐에 좌표 담기
				queue[1][rear] = ro + dx[i];
				rear++;
				visited[co + dy[i]][ro + dx[i]] = 1; // 큐에 담으며 방문체크
				distance[co + dy[i]][ro + dx[i]] = distance[co][ro] + 1; //거리 + 1
				box[co + dy[i]][ro + dx[i]] = 1; // 해당 토마토 익음
				if (cnt>=0) // 처음 익은 토마토, 
				{
					bfs(memo[0][cnt], memo[1][cnt]); // 다시 bfs 수행.
					cnt--;
				}
				
			}
		
	}
}

int main()
{
	memset(distance, -1, sizeof(distance));
	memset(box, -1, sizeof(box));
	memset(visited, -1, sizeof(visited));
	
	scanf("%d%d", &M, &N); // 가로 , 세로

	for (int i = 1;i <= N;i++) 
		for (int j = 1;j <= M;j++) 
			scanf("%2d", &box[i][j]); // 토마토 담기

	for (int i = 1;i <= N;i++)
		for (int j = 1;j <= M;j++)
			if (box[i][j] == 1&& visited[i][j] == -1) // bfs를 수행할  가로,세로 좌표를 memo에 저장하기, 초반에 익은 토마토 메모
			{
				cnt++;
				memo[0][cnt] = i;
				memo[1][cnt] = j;
			}
	if(cnt>=0) // 메모한 좌표를 토대로 bfs 수행
		bfs(memo[0][cnt], memo[1][cnt]);
	

	//for (int i = 1;i <= N;i++)
	//{
	//	for (int j = 1;j <= M;j++)
	//		printf("%d", distance[i][j]);
	//	printf("\n");
	//}

	//for (int i = 1;i <= N;i++)
	//{
	//	for (int j = 1;j <= M;j++)
	//		printf("%d", box[i][j]);
	//	printf("\n");
	//}

	int max = -1;
	for (int i = 1;i <= N;i++) // 박스중 아직 안익은 것이 있다면
		for (int j = 1;j <= M;j++)
		{
			if (box[i][j] == 0)
			{
				printf("-1"); // -1 출력
				return 0;
			}
		}

	for (int i = 1;i <= N;i++) // 박스중 아직 안익은 것이 있다면
		for (int j = 1;j <= M;j++)
			if (distance[i][j] > max)
				max = distance[i][j]; // 큰숫자 뱉기
	printf("%d", max);
	return 0;
}

devbelly 4년 전 0

코드가 조금 수정되어습니다 ㅜㅜ

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

문제

문제

출처

ICPC

토마토 어디가 틀렸는지 알려주실수 있나요?..

devbelly 4년 전 0

devbelly 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말