[도움 요청] 시간복잡도 계산 도움 요청

[INSEA-99]

📝 Question

백준 20057 마법사 상어와 토네이도

중앙에서 회오리 방향으로 회전하면서 이동한 칸에 있는 수를 룰에 맞추어 주변으로 뿌리는 문제입니다.

🤯 Problem

제 생각에는 연산이 최대 500 * 500 * 13 * 4라고 생각했는데 시간 초과가 납니다... 시간복잡도 계산이 잘못된 것 같아요!

🖥️ code

#include<iostream>
#include <cstring>
#include<limits.h>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

#define MAX (510)
#define MOD (1)
#define all(x) x.begin(), x.end()

// BFS 및 회오리 방향 이동에 사용됨. 상, 좌, 하, 우 방향
int dr[4] = {-1, 0, 1, 0};
int dc[4] = { 0, -1, 0, 1 };

int percentage[13] = { 0, 0, 7, 0, 7, 5, 10, 10, 2, 1, 0, 1, 2 };	// BFS 탐색시 탐색 순서에 따라 마주하게 될 percentage 배열 (BFS로 2번째로 탐색하는 노드는 7%에 해당됨)
int amount[13] = {0,};	// 모래 양에 percentage를 적용한 값을 저장할 배열

int N, R, C, D, ans;	// 격자 크기, 현재 행, 열, 방향, 격자 밖으로 나간 모래 양
int area[MAX][MAX], visit[MAX][MAX];	// 격자 모래 정보, BFS에 사용할 방문 확인 배열

void input();	// 입력 받기
void move(int n);	// 전체적인 프로그램을 담은 함수
void moveLine(int n);	// 한 줄 이동
void getAmount(int sand);	// amount 배열 업데이트 함수
void scatter();		// BFS를 통해 모래 뿌리기

int main() {
	ios::sync_with_stdio(0); cin.tie(NULL);

	input();
	move(1);
	cout << ans;
	return 0;
}

void input() {
	cin >> N;
	R = (N + 4) / 2;	// 초기 중앙 위치
	C = (N + 4) / 2;
	D = 1;	// 초기 방향 (좌)
	for (int r = 2; r < N + 2; ++r)
		for (int c = 2; c < N + 2; ++c) cin >> area[r][c];	// 모래 정보 저장

}

void move(int n) {	// 회오리 방향으로 하나씩 접근
	if (n == N) { moveLine(N - 1); return; } // 마지막 한 줄
	moveLine(n);	// 한 줄씩 이동
	moveLine(n);
	move(n + 1);
}

void moveLine(int n) {
	if (n == N) n--;
	for (int i = 0; i < n; ++i) {
		R += dr[D];		// 한 칸 이동
		C += dc[D];
		if (!area[R][C]) continue;	// 모래가 없으면 continue
		getAmount(area[R][C]);	// amount 업데이트
		scatter();	// 모래 뿌리기
		area[R][C] = 0;	// 모래 뿌리고 현재 위치 모래 없애기
	}
	D = (D + 1) % 4;
}
void scatter() {
	deque<pii> q = { pii(R,C) };	// BFS를 위한 deque
	memset(visit, 0, sizeof(visit));	// 방문 정보 초기화
	visit[R][C] = 1;
	
	int cnt = 1;	// 노드 방문 순서
	int depth = 2;	// 모래 뿌리는데 depth 2번이면 다 탐색됨
	int out = 0;	// 격자 밖으로 나간 모래 양
	while (!q.empty() && depth--) {
		int qsize = q.size();
		for (int s = 0; s < qsize; ++s) {
			int r = q.front().first;	// 현재 위치
			int c = q.front().second;
			q.pop_front();
			for (int i = D; i < D + 4; ++i) {
				int nr = r + dr[i % 4];		// 현재 위치 기반 다음 위치 후보
				int nc = c + dc[i % 4];
				if (visit[nr][nc]) continue;	// 이미 방문한 경우 continue
					visit[nr][nc] = 1;
				if (nr < 2 || nr >= N+2 || nc < 2 || nc >= N+2) out += amount[cnt];	// 격자 밖으로 나간 경우
				else area[nr][nc] += amount[cnt];	// 모래 뿌리기
				cnt++;
				if (cnt == 13) { ans+=out; return; } // 탐색 종료
				q.push_back(pii(nr, nc)); 
			}
		}
	}
}
void getAmount(int sand) {
	int total = sand;
	for (int i = 0; i < 13; ++i) {
		amount[i] = sand * percentage[i]/100;
		total -= amount[i];
	}
	amount[1] = total;
}

[minjae9610]

해당 코드에서 단순 시간복잡도를 계산하면 O(n^2)이 되지 않을까요?
move()와 moveLine()함수들의 2중반복이 가장 승수가 높아보이네요 :/

[INSEA-99]

해당 코드에서 단순 시간복잡도를 계산하면 O(n^2)이 되지 않을까요? move()와 moveLine()함수들의 2중반복이 가장 승수가 높아보이네요 :/

n의 최대값이 499인데 그럼 시간초과가 안날 것 같은데 발생하네요 ..

[minjae9610]

@INSEA-99 해결하셨을까요? 아직 못하셨다면 주말에 한번 체크해볼께요

[INSEA-99]

@minjae9610
저도 이후로 확인해보지 못했네요ㅠㅠ 그래주시면 정말 감사하죠 !

[minjae9610]

아무래도 문제의 시간이 빡빡하게 잡혀있는데 매번 BFS와 getAmount의 호출이 문제가 되는것 같네요 :(
해당 부분의 호출 횟수를 개선시키면 통과할 수 있을 것 같습니다!