글 읽기 - 시간초과 도와주실수 있으신가요?

isvara 3년 전 0

첫번째 bfs는 각 얼음이 언제 녹는지 계산하는 코드이고 두번째 bfs는

한 L위치에서 bfs로 돌리면서 가장 작은 day를 visited에 업데이트하면서 답을 구하는 코드입니다.

시간초과 나는 이유가 궁금합니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<set>
#include<map>
#include<queue>
#define debug cout
using namespace std;

const int max_n = 1501;
const int INF = 987654321;
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };

char b[max_n][max_n];
int days[max_n][max_n];
int visited[max_n][max_n];
int R, C;
int sr=-1, sc=-1;
int tr, tc;

bool near(int r, int c) {
	for (int i = 0; i < 4; i++) {
		int nr = r + dr[i];
		int nc = c + dc[i];
		if (nr < 0 || nc < 0 || nr >= R || nc >= C)continue;
		if (b[nr][nc] != 'X')
			return true;
	}
	return false;
}
 
void solve() {
	queue<pair<int, int>>q;
	queue<pair<pair<int, int>, int>>q2;

	for (int i = 0; i < R; i++) 
		for (int j = 0; j < C; j++) 
			if (b[i][j] == 'X' && near(i, j)) {
				q.push({ i,j });
				days[i][j] = 1;
			}
	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (nr < 0 || nc < 0 || nr >= R || nc >= C  || b[nr][nc]!='X' || days[nr][nc])continue;

			q.push({ nr,nc });
			days[nr][nc] = days[r][c] + 1;
		}
	}
	
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			visited[i][j] = INF;


	q2.push({ {sr,sc},0 });
	visited[sr][sc] = 0;
	int ans = INF;
	while (!q2.empty()) {
		int r = q2.front().first.first;
		int c = q2.front().first.second;
		int cost = q2.front().second;
		q2.pop();

		if (r == tr && c == tc) {
			ans = min(ans, cost);
			continue;
		}

		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (nr < 0 || nc < 0 || nr >= R || nc >= C)continue;
			if (visited[nr][nc] <= max(cost, days[nr][nc]))continue;

			if (b[nr][nc] == '.') {
				visited[nr][nc] = cost;
				q2.push({ {nr,nc},cost });
			}
			else {
				visited[nr][nc] = max(days[nr][nc], cost);
				q2.push({ {nr,nc},visited[nr][nc] });
			}
		}
	}
	cout << ans;
}
void input() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> R >> C;
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++){
			cin >> b[i][j];
			if (b[i][j] == 'L') {
				if (sr == -1 && sc == -1) sr = i, sc = j;
				else tr = i, tc = j;
			}
		}
}
int main() {
	input();
	solve();
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 도와주실수 있으신가요?

isvara 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말