글 읽기 - 시간초과 문제 질문드립니다

sta48 3년 전 0

예제 테케는 모두 정답으로 나옵니다

채점중 0%에서 걸려서 시간초과라고 나오는데

최대한 시간 복잡도 줄여보려고 노력했는데 잘 안되네요ㅜㅜ

아기상어가 물고기를 먹고 위치 이동할 때마다 bfs로 전체 dist배열을 갱신하는 작업이 불필요한 작업일까요?

메모이제이션으로 풀어야 하는 건가요?

채점번호 :

19705555

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <memory.h>
#include <algorithm>
//#include <filesystem>

using namespace std;

void bfs(int N, int start_x, int start_y, int s_size, int ate);
void find_next(int N, int start_x, int start_y, int s_size, int ate);
bool is_chk(const tuple<int, int, int>& a, const tuple<int, int, int>& b);


int map[21][21];
bool chk[21][21];
int dist[21][21];
int dirx[4] = { -1,0,1,0 };
int diry[4] = { 0,-1,0,1 };

int time_clock = 0;

queue<pair<int, int>> n_q;

int main(void) {

	//FILE* fin = fopen("input.txt", "r");
	//FILE* fout = fopen("output.txt", "w");

	int start_x;
	int start_y;
	int s_size = 2;
	int ate = 0;

	int N;
	scanf("%d", &N);
	//fscanf(fin, "%d", &N);

	if (N >= 2 && N <= 20) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				scanf("%d", &map[i][j]);
				//fscanf(fin, "%d", &map[i][j]);
				if (map[i][j] == 9) {
					start_x = i;
					start_y = j;
				}
			}
		}
	}
	
	while (1) {
		bfs(N, start_x, start_y, s_size, ate);
		find_next(N, start_x, start_y, s_size, ate);

		if (n_q.size() == 0)
			break;

		else {
			start_x = n_q.front().first;
			start_y = n_q.front().second;
			ate++;
			
			if (s_size == ate) {
				s_size++;
				ate = 0;
			}
			n_q.pop();
		}
	}

	printf("%d", time_clock);
	//fprintf(fout, "%d", time_clock);

	return 0;
}

void bfs(int N, int start_x, int start_y, int s_size, int ate) {
	queue<pair<int, int>> q;

	q.push(make_pair(start_x, start_y));
	chk[start_x][start_y] = true;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dirx[i];
			int ny = y + diry[i];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
				if (map[nx][ny] <= s_size && chk[nx][ny] == false) {
					dist[nx][ny] = dist[x][y] + 1;
					chk[nx][ny] = true;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}

}

void find_next(int N, int start_x, int start_y, int s_size, int ate) {
	vector<tuple<int, int, int>> v;

	int min_dist = 9999;
	for (int i = 0; i < N; i++) { // 1) 잡아먹을 수 있는 물고기 찾기 (행렬에서 열을 기준으로 행의 좌상우선탐색 가능하도록)
		for (int j = 0; j < N; j++) {
			if (map[j][i] != 0 && map[j][i] < s_size) {
				if (min_dist >= dist[j][i]) {
					min_dist = dist[j][i];
					v.push_back(make_tuple(j, i, dist[j][i]));
				}
			}
		}
	}

	if (v.size() == 0)
		return;

	if (v.size() == 1) {
		int nx = get<0>(v[0]);
		int ny = get<1>(v[0]);
		map[start_x][start_y] = 0;
		map[nx][ny] = 9;
		n_q.push(make_pair(nx, ny));
		time_clock += dist[nx][ny];
		
	}

	else if (v.size() > 1) {
		sort(v.begin(), v.end(), is_chk);  // 가장 가까운 것들 중 좌,상에 위치한 것들부터 먼저 먹도록
		int nx = get<0>(v[0]);
		int ny = get<1>(v[0]);
		map[start_x][start_y] = 0;
		map[nx][ny] = 9;
		n_q.push(make_pair(nx, ny));
		time_clock += dist[nx][ny];
	}

	memset(dist, 0, sizeof(dist));
	memset(chk, false, sizeof(chk));
}

bool is_chk(const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
	if (get<2>(a) == get<2>(b)) {  // 같은거리이면 행값을 비교해서 적은 녀석이 선택되도록(상단부터 선택되도록)
		return (get<0>(a) < get<0>(b));
	}
	else
		return (get<2>(a) < get<2>(b));
}

aftersnow 3년 전 1

find_next 함수에서 dist[j][i] == 0 경우도 예외처리를 해야합니다.

아기 상어의 현재 위치, 아기 상어보다 크기가 작은 물고기지만 큰 물고기 때문에 갈 수 없는 경우 dist[j][i] 가 0 입니다.

시간 초과가 나는 이유는 아기 상어의 크기가 9 이상이 됐을 때 자기 자신의 위치를 계속 n_q에 넣어서 그런 것 같아요.

그리고 is_chk 함수도 수정이 필요한 것 같습니다.

행 위치까지 같은 경우(get<0>(a) == get<0>(b) 왼쪽 열이 선택되어야 합니다.

sta48 3년 전 0

감사합니다
dist배열의 0일때 예외처리가 안되어서
불필요한 동작을 반복적으로 했기 때문에
시간초과였네요

is_chk함수는 수정했었는데
계속 시간초과나서 포기하고 있었는데..
다시 한번 감사합니다!

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

문제

문제

출처

ICPC

시간초과 문제 질문드립니다

sta48 3년 전 0

aftersnow 3년 전 1

sta48 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말