마법사 상어 시리즈를 또 한번 풀어보았다. 사실 이 문제는 항상 눈팅하면서 풀어야지 풀어야지 하다가 이제야 풀게 됐는데 문제의 난이도를 둘째 치고 정말 설명이랑 예시가 너무 헷갈렸다. 코딩 역량을 떠나서 만약 이 문제 자체를 한번 읽고 이해 했다면 그 사람은 정말 "신" 이다.
일단 문제를 푸는것보다 이해를 하는데 훨씬 더 많은 시간이 걸렸다. 격자를 이용해서 90도 회전을 하는 부분까지 이해했지만 문제는 얼음이 있는 칸 3개 또는 그 이상과 인접한 칸을 이해하는데 시간이 걸렸고, 여러가지 어지러운 설명과 예시였다.
이 문제는 전형적인 Matrix + 시뮬레이션 문제로 삼성에 기출 문제라고 들었는데 시뮬레이션 문제 중에서 그래도 난이도가 없는 문제는 아닌거같다. 일단 도형 회전에 대해서 꽤 많은 지식을 가지고 있어야 했고 또 회전된 도형을 원본에 넣는 그 과정을 잘 생각하는게 중요했다.
먼저 인풋을 해당 벡터 혹은 배열에 저장 시켜준다음에 차례대로 L 의 숫자를 읽어줬다.
가장 어려운 부분은 여기 있는 도형회전에서 부터 있었는데
나는 도형 회전과 원본에 주입 시켜주는 코드를 이렇게 적었다. 그런데 다른 사람들의 코드를 보니깐 x 와 y 의 좌표등을 사용해서 정말 깔끔하고 멋지게 주입 시켜줬어서 약간 민망한 코드이긴 하다. 먼저 x 와 y 의 범위를 실수하면 안되기에 꽤 조심해주면서 격자를 만드는 크기를 조정해주었다. 그리고 나서는 window 라는 임의에 격자를 만들어서 해당 범위만큼만 탐색해주었다. 그런데 조금 더 괜찮은 방법은 아예 Matrix 를 옮겨 담은 임시 메트릭스를 만들어서 둘을 조작하면은 좀 더 좋은 코드가 나왔을 수도 있었을거같다.
index_count 과 jndex_count 변수를 사용해서 내 윈도우에 인덱스를 원본에 맞는 범위로 잘 집어넣어주었다.
그 후에는 상하좌우로 탐색을 하면서 얼음이 있는 칸을 보면서 카운트가 3 이하인 얼음 칸은 숫자 1을 차감 시켜줘야하는데 꼭 모든 탐색이 끝난 후에 차감을 시켜줬어야지 답이 맞았다. 아마 이 부분에서 정말로 많은 사람들이 틀리지 않았을까 싶다.전체 탐색을 끝내고 나같은 경우 visited 에 표시를 해두었고 카운트가 3 미만인 장소에 얼음을 차감시켜주었다. 다만, 얼음이 계속 존재한다면 visited 를 true 로 바꿔주었다.
그 후에는 DFS 를 이용해서 visited 벡터를 탐색해줌으로서 서로 이어진 범위 안에서 얼마나 많은 조각들이 이어져있는지를 확인 해주었다. 범위를 구하는 탐색 코드같은 경우 나는 dfs 를 많이 사용하고 가장 깔끔하다고 생각한다.
이렇게 코드를 쓰면은 결국에 남은 전체 얼음에 종합된 숫자와, dfs 로 가장 큰 범위로 이어진 얼음들의 숫자를 구할수 있었다.
백준에 제출된 내 코드를 보면 무지성으로 많은 시간초과를 볼 수 있었는데 난 정말 왜 내가 시간 초과를 받지 하고 몇번을 다시 봤고 결국 고쳤던게 하나 있었다. 나는 2의 배수를 구하는 함수로 pow(2,N) 이라고 썼는데 이 함수를 dfs() 함수에서 계속 쓰다 보니 어이없게 시간 초과가 걸렸다. 알고보니 pow(2,N) 은 log(N) 의 시간이 걸리는 재귀 함수가 포함되어 있었고 이것을 dfs() 에서 계속 부르다보니 에러가 나왔다.
그래서 결국에는 int len 이라는 것을 만들어서 pow(2,N) 을 저장시켜서 같은 값을 계속 썼더니 시간 초과가 풀렸다. 참 어이없는 실수라서 버린 시간들이 너무 아깝지만 이제라도 깨달아서 다행이다.
#include <iostream>
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100010
using namespace std;
int N,Q;
vector<vector<int>> matrix;
int len;
int Qarr[1001];
vector<vector<bool>> visited;
vector<pair<int,int>> dir = {{-1,0},{1,0},{0,-1},{0,1}};
void Input(){
cin >> N >> Q;
vector<vector<int>> copyM(pow(2,N),vector<int>(pow(2,N),0));
vector<vector<bool>> copyV(pow(2,N),vector<bool>(pow(2,N),0));
for(int i = 0; i < pow(2,N); i++){
for(int j = 0; j < pow(2,N); j++){
cin >> copyM[i][j];
}
}
for(int i = 0; i < Q; i++){
cin >> Qarr[i];
}
matrix = copyM;
visited = copyV;
len = pow(2,N);
}
void make_window(int x, int y, int pow_L){
vector<vector<int>> window(pow_L, vector<int>(pow_L,0));
int index_count = 0;
int jndex_count = 0;
for(int i = x; i < x + pow_L; i++){ //격자 만들기
for(int j = y; j < y + pow_L; j++){
window[index_count][jndex_count++] = matrix[i][j];
}
index_count++;
jndex_count = 0;
}
//90도 회전
reverse(window.begin(),window.end());
for(int i = 0; i < window.size(); i++){
for(int j = i+1; j < window[i].size(); j++){
swap(window[i][j],window[j][i]);
}
}
index_count = 0;
jndex_count = 0;
//기존 Matrix에 회전된 윈도우 넣기
for(int i = x; i < x + pow_L; i++){
for(int j = y; j < y + pow_L; j++){
matrix[i][j] = window[index_count][jndex_count++];
}
index_count++;
jndex_count = 0;
}
}
void rotate(int L){
int pow_L = pow(2,L);
for(int i = 0; i < matrix.size(); i += pow_L){
for(int j = 0; j < matrix[i].size(); j += pow_L){
//cout << i << ' ' << j << endl;
make_window(i,j,pow_L);
}
}
}
void check(){
//상하 좌우 확인후에 cnt 를 올려준다
//cnt <= 3 인 경우 그 칸은 -- 를 해주고 0이 될경우 visited에 표시를 해두자
for(int x = 0; x < matrix.size(); x++){
for(int y = 0; y < matrix[x].size(); y++){
int cnt = 0;
if(matrix[x][y] <= 0){ //얼음이 없으면 상하좌우를 확인할 필요도 없다
visited[x][y] = true;
continue;
}
for(pair<int,int>& p: dir){
int nX = x + p.first;
int nY = y + p.second;
if(nX < 0 || nX >= len || nY < 0 || nY >= len || matrix[nX][nY] <= 0) continue;
cnt++;
}
//cout << cnt << ' ';
if(cnt < 3){
//matrix[x][y]--;
//if(matrix[x][y] <= 0) visited[x][y] = false;
visited[x][y] = true;
}
}
}
for(int i = 0; i < visited.size(); i++){
for(int j = 0; j < visited[i].size(); j++){
if(visited[i][j] == true){
matrix[i][j]--;
if(matrix[i][j] > 0) visited[i][j] = false;
}
}
}
}
int dfs(int i, int j){
if(i < 0 || i >= len || j < 0 || j >= len || visited[i][j]) return 0;
int cnt = 1;
visited[i][j] = true;
cnt += dfs(i+1,j);
cnt += dfs(i-1,j);
cnt += dfs(i,j+1);
cnt += dfs(i,j-1);
return cnt;
}
void reset(){
for(int i = 0; i < visited.size(); i++){
for(int j = 0; j < visited[i].size(); j++){
visited[i][j] = false;
}
}
}
void Solution(){
for(int i = 0; i < Q; i++){
if(Qarr[i] > 0)rotate(Qarr[i]); //L 방향에 대한 회전이 끝난 상태
reset();
check();
}
int sum = 0;
int cnt = 0;
for(int i = 0; i < matrix.size(); i++){
for(int j = 0; j < matrix[i].size(); j++){
if(matrix[i][j] > 0) sum += matrix[i][j];
if(!visited[i][j]) cnt = max(cnt,dfs(i,j));
}
}
cout << sum << endl;
cout << cnt;
}
void Solve(){
Input();
Solution();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("input.txt", "r", stdin);
Solve();
return 0;
}
배운점:
1. pow() 함수는 왠만하면 많이 부르지 말자
2. 도형의 회전
또 다른 답
개인적으로 이분 블로그가 도형을 회전하는데 있어서 되게 코드를 잘 썼다고 생각했다. 나도 앞으로 열심히 해야겠다.
