글 읽기 - 고수님들 시간초과 해결법 좀 알려주세요!

math_rabbit_1028 4년 전 0

시간 초과가 납니다. 시간을 효과적으로 줄일 수 있는 방법을 좀 알려주세요.

#include "pch.h"
#include <iostream>
#include <queue>
using namespace std;
int n, m, h, map[110][110][110], ch[110][110][110], dis[110][110][110], res = -2147000000;
int dx[6] = { 0, 0, 0, 0, 1, -1 }, dy[6] = { -1, 0, 1, 0, 0, 0 }, 
dz[6] = { 0, 1, 0, -1, 0, 0 };
struct tomato {     //큐에 사용하기 위한 구조체
	int x, y, z;
	tomato(int tx, int ty, int tz) {
		x = tx;
		y = ty;
		z = tz;
	}
};
queue<tomato> Q;

bool end() {        //토마토가 다 익었는지를 보기 위한 함수
	bool f = true;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= m; k++)
				if (map[i][j][k] == 0) f = false;
	return f;
}

int main() {
	int f = 0;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> h;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= m; k++)
				dis[i][j][k] = 2147000000;
	for (int i = 1; i <= h; i++) 
		for (int j = 1; j <= n; j++) 
			for (int k = 1; k <= m; k++) 
				cin >> map[i][j][k];
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= m; k++) {
				if (map[i][j][k] == 1) {
					ch[i][j][k] = 1;
					dis[i][j][k] = 0;
					Q.push(tomato(i, j, k))
				}
			}
		}
	}
	while (!Q.empty()) {
		if (end()) {
			f = 1;
			break;
		}
		tomato t = Q.front();
		Q.pop();
		for (int i = 0; i < 6; i++) {
			int x = t.x + dx[i], y = t.y + dy[i], z = t.z + dz[i];
			if (map[x][y][z] != -1 && ch[x][y][z] == 0 && 0 < x && x <= h && 0 < y && y <= n && 0 < z && z <= m) {
				map[x][y][z] = 1;
				ch[x][y][z] = 1;
				if (dis[x][y][z] > dis[t.x][t.y][t.z] + 1)
					dis[x][y][z] = dis[t.x][t.y][t.z] + 1;
				Q.push(tomato(x, y, z));
			}
		}
	}
	if (f == 1) {
		for (int i = 1; i <= h; i++)
			for (int j = 1; j <= n; j++)
				for (int k = 1; k <= m; k++)
					if (res < dis[i][j][k]) res = dis[i][j][k];
		cout << res << '\n';
	}
	else cout << "-1\n";
	return 0;
}

djm03178 4년 전 0

end라는 함수는 필요 없습니다. 큐가 비어서 루프를 자연스럽게 탈출하게 되는 순간이 곧 탐색이 끝난 순간입니다.

math_rabbit_1028 4년 전 0

이렇게 코드를 바꿨는데 틀렸다고 하네요...

#include <iostream>
#include <queue>
using namespace std;
int n, m, h, map[110][110][110], ch[110][110][110], dis[110][110][110], res = -2147000000;
int dx[6] = { 0, 0, 0, 0, 1, -1 }, dy[6] = { -1, 0, 1, 0, 0, 0 }, 
dz[6] = { 0, 1, 0, -1, 0, 0 };
struct tomato {
	int x, y, z;
	tomato(int tx, int ty, int tz) {
		x = tx;
		y = ty;
		z = tz;
	}
};
queue<tomato> Q;

int main() {
	int f = 0;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> h;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= m; k++)
				dis[i][j][k] = 2147000000;
	for (int i = 1; i <= h; i++) 
		for (int j = 1; j <= n; j++) 
			for (int k = 1; k <= m; k++) 
				cin >> map[i][j][k];
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= m; k++) {
				if (map[i][j][k] == 1) {
					ch[i][j][k] = 1;
					dis[i][j][k] = 0;
					Q.push(tomato(i, j, k));
				}
			}
		}
	}
	while (!Q.empty()) {
		tomato t = Q.front();
		Q.pop();
		for (int i = 0; i < 6; i++) {
			int x = t.x + dx[i], y = t.y + dy[i], z = t.z + dz[i];
			if (map[x][y][z] != -1 && ch[x][y][z] == 0 && 0 < x && x <= h && 0 < y && y <= n && 0 < z && z <= m) {
				map[x][y][z] = 1;
				ch[x][y][z] = 1;
				if (dis[x][y][z] > dis[t.x][t.y][t.z] + 1)
					dis[x][y][z] = dis[t.x][t.y][t.z] + 1;
				Q.push(tomato(x, y, z));
			}
		}
	}
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= m; k++)
				if (map[i][j][k] == 0) f = 1;
	if (f == 0) {
		for (int i = 1; i <= h; i++)
			for (int j = 1; j <= n; j++)
				for (int k = 1; k <= m; k++)
					if (res < dis[i][j][k]) res = dis[i][j][k];
		cout << res << '\n';
	}
	else cout << "-1\n";
	return 0;
}

djm03178 4년 전 0

첫 줄의 입력의 순서는 m n h인데 n m h로 받고 계시네요. 첫 번째로 주어지는 수가 가로니까 가장 안쪽 루프에 들어가야 하는데 중간 루프에 있습니다.

math_rabbit_1028 4년 전 0

아 감사합니다. 이 부분이 좀 이상하긴 했었는데...

앞으로 코딩 공부 많이 해야 겠습니다.

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

문제

문제

출처

ICPC

고수님들 시간초과 해결법 좀 알려주세요!

math_rabbit_1028 4년 전 0

djm03178 4년 전 0

math_rabbit_1028 4년 전 0

djm03178 4년 전 0

math_rabbit_1028 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말