728x90
반응형
https://www.acmicpc.net/problem/20058
20058번: 마법사 상어와 파이어스톰
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ20058_1
//
// Created by Hwayeon on 2021/10/17.
//
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
int N, Q;
int A[65][65] = {0, };
int visit[65][65] = {0, };
int cmd[1001] = {0, };
int NN;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
vector<pair<int, int>> loc;
vector<int> temp;
int big_group = 0;
int total_ice = 0;
void remove_ice(){
int nx, ny, cnt;
loc.clear();
for(int y=0; y<NN; y++){
for(int x=0; x<NN; x++){
if(A[y][x] == 0) continue;
cnt = 0;
for(int d=0; d<4; d++){
nx = x + dx[d];
ny = y + dy[d];
if(nx<0 || nx>=NN || ny<0 || ny>=NN) continue;
if(A[ny][nx] > 0) cnt++;
}
if(cnt < 3) loc.push_back({x, y});
}
}
for(int i=0; i<loc.size(); i++){
A[loc[i].second][loc[i].first]--;
}
}
void play_firestorm(){
int L, LL;
for(int q=0; q<Q; q++){
L = cmd[q];
LL = pow(2, L);
for(int l=0; l<NN; l+=LL){
for(int m=0; m<NN; m+=LL){
temp.clear();
for(int y=l; y<l+LL; y++){
for(int x=m; x<m+LL; x++){
temp.push_back(A[y][x]);
}
}
for(int x=m; x<m+LL; x++){
for(int y=l+LL-1; y>=l; y--){
A[y][x] = temp.back();
temp.pop_back();
}
}
}
}
remove_ice();
}
}
int get_ice(){
int cnt = 0;
for(int y=0; y<NN; y++){
for(int x=0; x<NN; x++){
cnt += A[y][x];
}
}
return cnt;
}
void get_big_group(int sx, int sy){
int cnt = 1;
visit[sy][sx] = 1;
queue<pair<int, int>> q;
q.push({sx, sy});
while(!q.empty()){
int now_x = q.front().first;
int now_y = q.front().second;
q.pop();
for(int d=0; d<4; d++){
int nx = now_x + dx[d];
int ny = now_y + dy[d];
if(nx<0 || nx>=NN || ny<0 || ny>=NN) continue;
if(visit[ny][nx]) continue;
if(A[ny][nx]==0) continue;
visit[ny][nx] = 1;
cnt ++;
q.push({nx, ny});
}
}
if(cnt > big_group) big_group = cnt;
}
int main(int argc, const char * argv[]) {
cin >> N >> Q;
NN = pow(2, N);
for(int y=0; y<NN; y++){
for(int x=0; x<NN; x++){
cin >> A[y][x];
}
}
for(int q=0; q<Q; q++){
cin >> cmd[q];
}
play_firestorm();
total_ice = get_ice();
if(total_ice == 0){
cout << 0 << endl;
cout << 0 << endl;
return 0;
}
for(int y=0; y<NN; y++){
for(int x=0; x<NN; x++){
if(A[y][x] > 0 && !visit[y][x]){
get_big_group(x, y);
}
}
}
cout << total_ice << endl;
cout << big_group << endl;
return 0;
}풀이 과정
풀이 시간 1시간 16분
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
int N, Q;
int A[65][65] = {0, };
int visit[65][65] = {0, };
int cmd[1001] = {0, };
//NN = 2^N, 격자의 행, 열 길이
int NN;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
//얼음의 양을 줄여야하는 위치를 담는 벡터
vector<pair<int, int>> loc;
//부분 격자를 회전할 때 쓸 벡터
vector<int> temp;
int big_group = 0;
int total_ice = 0;
void remove_ice(){
int nx, ny, cnt;
loc.clear();
for(int y=0; y<NN; y++){
for(int x=0; x<NN; x++){
//이미 얼음이 없는 경우, 무시한다
if(A[y][x] == 0) continue;
//얼음이 있는 인접한 칸의 개수
cnt = 0;
for(int d=0; d<4; d++){
nx = x + dx[d];
ny = y + dy[d];
//격자의 범위를 벗어난 경우, 무시한다
if(nx<0 || nx>=NN || ny<0 || ny>=NN) continue;
//인접한 위치에 얼음이 있는 경우, 카운팅
if(A[ny][nx] > 0) cnt++;
}
//얼음이 있는 인접한 위치가 3곳 미만인 경우, 해당 위치의 얼음이 줄어들어야 하므로, loc에 위치 추가
if(cnt < 3) loc.push_back({x, y});
}
}
//loc의 위치들의 얼음을 1 줄인다
for(int i=0; i<loc.size(); i++){
A[loc[i].second][loc[i].first]--;
}
}
void play_firestorm(){
int L, LL;
for(int q=0; q<Q; q++){
//1. 격자 회전 -> O(2^(2N))
//단계 L, 부분 격자의 길이 LL
L = cmd[q];
LL = pow(2, L);
for(int l=0; l<NN; l+=LL){
for(int m=0; m<NN; m+=LL){
temp.clear();
//1-1. 부분격자 회전
//부분격자에 담긴 얼음들을 순차적으로 temp에 넣는다
for(int y=l; y<l+LL; y++){
for(int x=m; x<m+LL; x++){
temp.push_back(A[y][x]);
}
}
//temp에 담긴 역 순서대로 90도 회전한 격자의 위치에 넣어준다
for(int x=m; x<m+LL; x++){
for(int y=l+LL-1; y>=l; y--){
A[y][x] = temp.back();
temp.pop_back();
}
}
}
}
//2. 얼음의 양 줄이기 -> O(2^(2N))
remove_ice();
}
}
int get_ice(){
int cnt = 0;
for(int y=0; y<NN; y++){
for(int x=0; x<NN; x++){
cnt += A[y][x];
}
}
return cnt;
}
void get_big_group(int sx, int sy){
int cnt = 1;
visit[sy][sx] = 1;
queue<pair<int, int>> q;
q.push({sx, sy});
while(!q.empty()){
int now_x = q.front().first;
int now_y = q.front().second;
q.pop();
//인접 위치 탐색
for(int d=0; d<4; d++){
int nx = now_x + dx[d];
int ny = now_y + dy[d];
//범위를 벗어난 경우, 무시한다
if(nx<0 || nx>=NN || ny<0 || ny>=NN) continue;
//이미 방문한 칸이라면, 무시한다
if(visit[ny][nx]) continue;
//얼음이 없는 칸이라면, 무시한다
if(A[ny][nx]==0) continue;
//얼음이 있는 칸인 경우, 방문 처리 후 카운팅
visit[ny][nx] = 1;
cnt ++;
q.push({nx, ny});
}
}
//가장 큰 그룹인 경우, big_group 갱신
if(cnt > big_group) big_group = cnt;
}
int main(int argc, const char * argv[]) {
cin >> N >> Q;
NN = pow(2, N);
for(int y=0; y<NN; y++){
for(int x=0; x<NN; x++){
cin >> A[y][x];
}
}
for(int q=0; q<Q; q++){
cin >> cmd[q];
}
//파이어스톰 시전
play_firestorm();
//남은 얼음의 양 구하기 -> O(2^(2N))
total_ice = get_ice();
//얼음의 양이 0인 경우,
if(total_ice == 0){
cout << 0 << endl;
cout << 0 << endl;
return 0;
}
//가장 큰 그룹 구하기 -> O(2^(2N))
for(int y=0; y<NN; y++){
for(int x=0; x<NN; x++){
//얼음이 있고, 이전에 방문하지 않은 위치라면 해당 위치를 시작으로 bfs 탐색 시작
if(A[y][x] > 0 && !visit[y][x]){
get_big_group(x, y);
}
}
}
cout << total_ice << endl;
cout << big_group << endl;
return 0;
}
//시간복잡도 = O(Q*2^(2N)) -> O(n), 공간복잡도 = O(2^(2N)) -> O(1)이전 풀이
풀이 시간 1시간 55분
문제에 나와있는 설명 그대로 구현만 하면 되는 시뮬레이션 문제이다.
문제자체를 이해하는데는 쉬웠지만, 나는 이렇게 회전 구현에 시간이 많이 걸린다,,(머릿속으로 굴리는 시간이 좀 걸려서ㅠ)
방법은 그냥 차근차근 회전이 잘 적용되었는지 디버깅하면서 확인하며 스탭스탭 나아가는 것 뿐이다.
이런 문제도 반복적으로 풀다보면 내 머리가 빠르게 굴러갈 거라 믿는다,,
나는 회전을 구현할 때, 저번에 컨베이어 벨트 위의 로봇 문제를 풀듯이 바깥쪽부터 안쪽으로 적용했다.
즉, N=2라면, 2^N = 4, 한 변의 길이가 4인 가장 바깥쪽 둘레를 회전시키고, 그 안쪽인 한 변의 길이가 2인 둘레를 회전시켰다.
이런식으로 N=1이 되는 순간까지 바깥쪽부터 안쪽으로 회전을 시켜서 문제를 풀 수 있었다.
#include <iostream>
#include <queue>
#include <math.h>
using namespace std;
//N이 최대 6이므로, 얼음판은 최대 2^6x2^6
int board[64][64] = {0, };
int visit[64][64] = {0, };
int N, Q;
//얼음판의 가로, 세로 길이
int max_rc;
//마법사 상어가 파이어스톰을 시전한 단계를 순서대로 담을 큐
queue<int> q;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
//가장 큰 덩어리가 차지하는 칸 수
int max_hunk = 0;
void rotate(int sx, int sy, int rc){
vector<int> temp;
//격자의 시작 위치
int nx = sx;
int ny = sy;
//격자의 길이
int nrc = rc;
//격자의 바깥쪽부터 안쪽으로 차례대로 회전시킨다 -> 최악의 경우 nrc = 64일 때, 32번 반복 => O(1)
while(nrc>=2){
//1. temp 담기 - 해당 격자의 가장 왼쪽 사이드에 있는 값들을 temp에 담는다
temp.clear();
for(int d=nrc-2; d>=0; d--){
temp.push_back(board[ny+d][nx]);
}
//2. 회전
for(int d=0; d<nrc; d++){
board[ny+d][nx] = board[ny+nrc-1][nx+d];
}
for(int d=0; d<nrc-1; d++){
board[ny+nrc-1][nx+nrc-1-d] = board[ny+d][nx+nrc-1];
}
for(int d=nrc-1; d>=1; d--){
board[ny+d][nx+nrc-1] = board[ny][nx+d];
}
//temp에 담긴 값을 가장 위쪽 사이드에 담는다
for(int i=1; i<=temp.size(); i++){
board[ny][nx+i] = temp[i-1];
}
//다음 안쪽을 회전시키기 위해 nrc의 길이를 2만큼 줄이고, 다음 안쪽의 시작 위치를 조정한다
nrc -= 2;
nx += 1;
ny += 1;
}
}
void reduce_ice(){
//얼음 양을 줄여야하는 위치를 담을 벡터
vector<pair<int, int>> spots;
//전체 격자를 탐색하여 얼음 양을 줄여야하는 위치를 찾는다 -> T(2^(2N)*4) = O(16384)
for(int y=0; y<max_rc; y++){
for(int x=0; x<max_rc; x++){
if(board[y][x]<=0) continue;
int cnt = 0;
for(int d=0; d<4; d++){
int nx = x+dx[d];
int ny = y+dy[d];
if(nx<0 || nx>=max_rc || ny<0 || ny>=max_rc) continue;
if(board[ny][nx] > 0) cnt++;
}
//인접한 위치에 얼음이 있는 곳이 3군데 미만인 경우, 해당 위치의 얼음 양을 줄여야하므로 spots 벡터에 해당 위치를 push한다
if(cnt<3) spots.push_back({x, y});
}
}
//spots 벡터에 담겨있는 위치들의 얼음 양을 1씩 줄인다 -> O(2^(2N))
for(int i=0; i<spots.size(); i++){
int x = spots[i].first;
int y = spots[i].second;
board[y][x] --;
}
}
void firestorm(){
//큐에 담긴 단계들을 모두 시전한다 -> O(Q*2^(2N))
while(!q.empty()){
int n = q.front();
int rc = pow(2, n);
q.pop();
//격자를 2^n x 2^n으로 나눈다
for(int sy=0; sy<max_rc; sy+=rc){
for(int sx=0; sx<max_rc; sx+=rc){
//해당 격자를 시계방향으로 90도 회전시킨다
rotate(sx, sy, rc);
}
}
//얼음이 줄어든다
reduce_ice();
}
}
void bfs(int sx, int sy){
//탐색 시작 위치인 (sx, sy)를 큐에 담고 방문 처리한다
queue<pair<int, int>> queue;
queue.push({sx, sy});
visit[sy][sx] = 1;
//현재 시작 위치에 얼음이 있으므로 cnt = 1로 시작
int cnt = 1;
//얼음 덩어리 탐색
while(!queue.empty()){
int now_x = queue.front().first;
int now_y = queue.front().second;
queue.pop();
//인접한 4방향 탐색
for(int i=0; i<4; i++){
int nx = now_x + dx[i];
int ny = now_y + dy[i];
//격자 범위를 벗어나면, 무시한다
if(nx<0 || nx>=max_rc || ny<0 || ny>=max_rc) continue;
//이전에 방문한 위치라면, 무시한다
if(visit[ny][nx]) continue;
//인접 위치에 얼음이 없다면, 무시한다
if(board[ny][nx] <= 0) continue;
//얼음이 있는 인접 위치이므로 방문 처리하고 cnt 카운팅한다
queue.push({nx, ny});
visit[ny][nx] = 1;
cnt++;
}
}
//해당 덩어리의 칸의 개수가 max_hunk보다 많다면, max_hunk를 갱신한다
if(cnt > max_hunk) max_hunk = cnt;
}
int main(int argc, const char * argv[]) {
cin >> N >> Q;
max_rc = pow(2, N);
for(int i=0; i<max_rc; i++){
for(int j=0; j<max_rc; j++){
cin >> board[i][j];
}
}
//마법사 상어가 시전할 단계들을 차례대로 큐에 담는다
for(int i=0; i<Q; i++){
int qq;
cin >> qq;
q.push(qq);
}
//파이어스톰 시전
firestorm();
//남아있는 얼음 양과 가장 큰 덩어리가 차지하는 칸의 개수 구하기 -> O(2^(2N)*(V+E)) = O(2^(4N))
int remain_ice = 0;
for(int y=0; y<max_rc; y++){
for(int x=0; x<max_rc; x++){
//얼음 양 카운팅
remain_ice += board[y][x];
//이전에 방문하지 않은 위치이고 얼음이 있다면, 해당 위치를 시작으로 BFS 탐색을 시작한다.
if(board[y][x] > 0 && !visit[y][x]) bfs(x, y);
}
}
cout << remain_ice << endl;
cout << max_hunk << endl;
return 0;
}
//시간복잡도 = O(2^(4N)), 공간복잡도 = O(2^(2N))
728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 3686 성냥개비 Python 3 (0) | 2021.10.02 |
|---|---|
| 백준 20057 마법사 상어와 토네이도 C++ (0) | 2021.09.16 |
| 백준 19238 스타트 택시 C++ (0) | 2021.09.15 |
| 백준 14716 현수막 C++ (0) | 2021.08.31 |
| 백준 1303 전쟁 - 전투 C++ (0) | 2021.08.30 |