[도움 요청] 시간복잡도 계산 도움 요청 #49
Description
📝 Question
중앙에서 회오리 방향으로 회전하면서 이동한 칸에 있는 수를 룰에 맞추어 주변으로 뿌리는 문제입니다.
🤯 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;
}