글 읽기 - 시간 초과 문제

wngywo12 5년 전 0

안녕하세요. 시간초과 관련하여 질문 드립니다.

아래의 소스코드에서 표시한 부분에서 처음 진입할 때 visit을 1로 바꾸지 않으면 시간초과가 나는데 이유가 뭔지 알고 싶습니다.

혼자 고민해봤는데 잘 모르겠네요...

#include"stdafx.h"
#include <iostream>
#include <queue>
#include <cstring>
#include <time.h>
using namespace std;

int N;
int map[21][21];
int visit[21][21];
int cur_size = 2;
int cnt_feed;//먹은 물고기의 수
int dr[4] = { -1, 0,0,1 };
int dc[4] = { 0,-1,1,0 };
int sum_of_time;
int cur_row, cur_col;
int target_row, target_col;
int moving_time;

int bfs(int _row, int _col, int* _next_row, int* _next_col) {
	int q_size, i, j;
	int next_r, next_c;
	int find = 0;
	int distance = 0;
	int min_row = N;
	int min_col = N;
	queue<pair<int, int>> q;
	pair<int, int> tmp;
	int r, c;
	tmp.first = _row;
	tmp.second = _col;
	/*************************************************/
	//이부분입니다!!!!!!
    //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	visit[_row][_col] = 1;
	//visit[_row][_col]=1; << 이 연산을 해주지 않으면 시간 초과가 뜹니다.
	/*************************************************/
	q.push(tmp);
	while (!q.empty()) {
		q_size = q.size();
		for (i = 0; i < q_size; i++) {
			r = q.front().first;
			c = q.front().second;
			for (j = 0; j < 4; j++) {
				next_r = r + dr[j];
				next_c = c + dc[j];
				if (next_r > 0 && next_r <= N && next_c > 0 && next_c <= N) {
					if (map[next_r][next_c] <= cur_size && visit[next_r][next_c] == 0) {
						tmp.first = next_r;
						tmp.second = next_c;
						visit[next_r][next_c] = 1;
						q.push(tmp);
						if (map[next_r][next_c] < cur_size && map[next_r][next_c] != 0)find++;
					}
				}
			}
			q.pop();
		}
		distance++;
		if (find != 0) {
			//탐색을 종료하고 조건에 맞는 위치를 찾아 줘야한다
			while (find>0) {
				r = q.front().first;
				c = q.front().second;
				if (map[r][c] < cur_size &&map[r][c] != 0) {
					find--;
					if (r < min_row) {
						min_row = r;
						min_col = c;
					}
					else if (r == min_row) {
						if (c < min_col) {
							min_row = r;
							min_col = c;
						}
					}
				}
				q.pop();
			}
			*_next_row = min_row;
			*_next_col = min_col;
			return distance;
		}
	}
	return -1;
}
bool check(int _row, int _col) {
	int i, j;
	int next_row, next_col;
	int distance;
	//인접한 물고기가 있는지 체크
	for (i = 0; i < 4; i++) {
		next_row = _row + dr[i];
		next_col = _col + dc[i];
		if (next_row > 0 && next_row <= N && next_col > 0 && next_col <= N) {
			if (map[next_row][next_col] < cur_size && map[next_row][next_col] != 0) {
				moving_time = 1;
				target_row = next_row;
				target_col = next_col;
				return true;
			}
		}
	}
	//멀리 떨어진 물고기가 있는지 체크
	memset(visit, 0, sizeof(visit));
	distance = bfs(_row, _col, &next_row, &next_col);
	if (distance > 0) {
		target_row = next_row;
		target_col = next_col;
		moving_time = distance;
		return true;
	}
	return false;


}
void move(int _target_row, int _target_col) {
	map[cur_row][cur_col] = 0;
	map[_target_row][_target_col] = 9;
	cur_row = _target_row;
	cur_col = _target_col;
	sum_of_time += moving_time;
}
void eat(int _row, int _col) {
	cnt_feed++;
	if (cnt_feed == cur_size) {
		cur_size++;
		cnt_feed = 0;
	}
}
int main()
{
	int i, j;
	cin >> N;
	sum_of_time = 0;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				cur_row = i;
				cur_col = j;
				cnt_feed = 0;
			}
		}
	}

	while (1) {
		if (check(cur_row, cur_col)) {
			move(target_row, target_col);
			eat(cur_row, cur_col);
		}
		else {
			break;
		}
	}
	printf("%d\n", sum_of_time);
	return 0;
}

SORINAMU 5년 전 0

시작 위치는 이미 방문됐지만, 방문처리를 안하면 그 주위에 있던 값들은 방문되지 않았다고 생각하고 값을 또 삽입하고 무의미한 일을 반복합니다.

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

문제

문제

출처

ICPC

시간 초과 문제

wngywo12 5년 전 0

SORINAMU 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말