글 읽기 - 미쳐버리겠습니다. 도와주십시오. 도움!

indigo8006 3년 전 0

살려주십시오. 모든 게시판의 반례를 넣어봤지만 찾지 못했습니다.

10퍼 이하에서 틀렸습니다 뜨는것 같습니다ㅠㅠㅠㅠ

도와주십시오.. 코린이의 눈물ㅠㅠ

#include <stdio.h>
int N, M, max = 1, flag;
int map[1010][1010];
int chk[1010][1010];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
struct Mystruct {
	int x;
	int y;
	int d;
}q[1000002];
void bfs(int a, int b) {
	int in = -1, out = -1; // 초기화
	int x, y;
	q[++in].x = a;
	q[in].y = b;
	q[in].d = 1;
	chk[a][b] = 1;


	while (in != out) {
		out++;
		for (int i = 0; i < 4; i++) {
			x = q[out].x + dx[i];
			y = q[out].y + dy[i];
			if (x >= 0 && y >= 0 && x < N && y < M && map[x][y] == 0) {
				if (chk[x][y] == 0) { // 방문하지 않은 경우
					q[++in].x = x;
					q[in].y = y;
					q[in].d = q[out].d + 1;
					chk[x][y] = q[in].d;
				}
				else {
					if (chk[x][y] > q[out].d) { // 더 빨리 익는 경우
						q[++in].x = x;
						q[in].y = y;
						q[in].d = q[out].d + 1;
						chk[x][y] = q[in].d;
					}
				}
			}
		}
	}



}
int main() {
	scanf("%d %d", &M, &N);
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == -1)
			{
				cnt++;
				chk[i][j] = -1;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 1)
				bfs(i, j);
		}
	}

	for (int i = 0; i < N; i++) { // 최대값 찾기
		for (int j = 0; j < M; j++) {
			if (max < chk[i][j])
				max = chk[i][j];
				
		}
	}
	for (int i = 0; i < N; i++) { // 토마토가 못 익는경우
		for (int j = 0; j < M; j++) {
			if (chk[i][j] == 0)
				flag = 1;
		}
	}
	if (cnt == N * M) // 토마토가 아에 없을때
	{
		flag = 1;
	}
	if (flag == 0)
		printf("%d", max - 1);
	else
		printf("-1");
}

pichulia 3년 전 1

토마토가 다음과같이 ㄹ자 모양으로 배치된 경우

한번 들어간 토마토가 여러번 등장할 수 있기 때문에 시간초과 + 큐 메모리 폭발 현상이 일어납니다.

8
1 1 1 1 1 1
0 0 0 0 0 0
1 1 1 1 1 0
0 0 0 0 0 0
1 1 1 1 1 1
0 0 0 0 0 0
1 1 1 1 1 0
0 0 0 0 0 0

hs9200 3년 전 0

일단은 저는 시간초과 코드가 났지만 저가 아는데 까지 알려드리겟습니다.

시간초과 난점:

34~36번째 줄의 for문으로 값이 1인 지점을 일일히 찾아서 그때그때 bfs를 돌리므로 시간이 많이 걸리게 됩니다.

19~21번째 줄의 for문에서 값이 1인 지점을 전부 찾아놓고 bfs는 한번만 돌리시면 됩니다.

저의 코드에서 이렇게 수정만 하시면 맞을 겁니다.

참고로 이미 익은 토마토를 찾으면 2라고 표시를 해놉니다.

그러면 다시 bfs가 돌지 않습니다.

(미리 저가 코드를 짯으므로 이점은 수정 안 해도 됩니다.

시간초과만 고치시면 됩니다.)

어차피 저도 조금 이따가 풀거예요ㅎㅎ

#include <stdio.h>
#include <algorithm>
#include <queue>
#define M 1000//배열 크기
#define INF 599999999//다이내믹 최소값 구해야 하기 때문
using namespace std;
queue <int> q;
int a[M + 1][M + 1];//배열
int d[M + 1][M + 1];//다이내믹 배열
int dy[4] = { 0,1,0,-1 };//4방향 데이터
int dx[4] = { 1,0,-1,0 };//4방향 데이터
int ty, tx, y, x;//bfs에 필요한 변수
int maxa, n, m;//가로세로길이, 가장 큰 값
int main(void)
{
	int i, j;
	scanf("%d %d", &m, &n);//배열 크기(가로를 먼저 입력 받아야 함)
	int sy, sx;//찾은 지점이 1이면 queue에 넣는 형태로
	for (i = 1; i <= n; i++)//for문 시작
	{
		for (j = 1; j <= m; j++)//for문 시작 2
		{
			scanf("%d", &a[i][j]);//이건 배열 입력 받는것(토마토에서 1,0,-1 입력 받는것)
			if (a[i][j] != -1)//a[i][j]가 토마토가 없는 지점이 아니면
			{
				d[i][j] = INF;//가장 빨리 토마토가 익는 시간을 구해야 하므로 최솟값이기 때문에
			}
			else//토마토가 없으면
			{
				d[i][j] = -1;//아예 다이내믹에 포함 x(그러니까 최솟값이 항상 변하지 않는다(-1보다 작은 거리는 없으므로))
			}
		}
	}
	for (sy = 1; sy <= n; sy++)//for문으로 값이 1인 지점을 찾는다
	{
		for (sx = 1; sx <= m; sx++)//for문으로 값이 1인 지점을 찾는다 2
		{
			if (a[sy][sx] == 1)//만약 토마토가 익었으면
			{
				q.push(sy);//queue에 집어 넣고
				q.push(sx);//queue에 집어 넣고 2
				d[sy][sx] = 0;//처음부터 익었으니까
				a[sy][sx] = 2;//이미 다녀왔다고 visit
				while (!q.empty())
				{
					y = q.front(); q.pop();//queue를 꺼낸다
					x = q.front(); q.pop();//queue를 꺼낸다2
					for (i = 0; i <= 3; i++)//4방향이니까 for문 돌리고
					{
						ty = y + dy[i];//목표 y좌표 구한다
						tx = x + dx[i];//목표 x좌표 구한다
						if (ty >= 1 && ty <= n && tx >= 1 && tx <= m && a[ty][tx] != -1 && a[ty][tx] != 1 && d[ty][tx] > d[y][x] + 1)
						//이건 배열 밖을 벗어나면 안되고, 토마토가 없으면 안되고, 익은 토마토면(다녀오지 않은) 안되고(
                        //나중에 다녀와야 하니까) 거리가 더 짧아야 하니까
                        {
							d[ty][tx] = d[y][x] + 1;//다이내믹
							q.push(ty);//queue에 집어 넣고 3
							q.push(tx);//queue에 집어 넣고 4
							a[ty][tx] = 2;//이미 다녀왔다고 visit
						}
					}
				}
			}
		}
	}
	maxa = -1;
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			if (maxa < d[i][j])
			{
				maxa = d[i][j];
			}
		}
	}
    //가장 오래 걸리는 토마토(모든 토마토가 다 익는 시점)
	if (maxa == INF)//안 익은토마토가 있으니까
	{
		printf("-1");
	}
	else if (maxa == 0)//토마토가 처음부터 모두 익었을 때
	{
		printf("0");
	}
	else//일반의 경우
	{
		printf("%d", maxa);
	}
	return 0;//끝
}

hs9200 3년 전 0

참고로 구조체 쓸 필요가 없습니다.

indigo8006 3년 전 0

감사합니다 여러분ㅠㅠㅠㅠㅠ다시 짜보겟습니다

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

문제

문제

출처

ICPC

미쳐버리겠습니다. 도와주십시오. 도움!

indigo8006 3년 전 0

pichulia 3년 전 1

hs9200 3년 전 0

hs9200 3년 전 0

indigo8006 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말