11월의 첫날!
여러모로 새롭게 시작하는 마음이다,,
오늘 네이버 웹툰 면접 탈락 메일을 받았다,, 1달 가까이 기다리면서 떨어질 것 같았지만 막상 진짜 떨어지니 슬픈 기분은 어쩔 수가 없다 ㅎ,,
아직 하반기 완전히 끝난게 아니기에 오늘부터는 알고리즘은 하나씩만 하고 비교적 소홀했던 CS 와 iOS 위주의 흐름으로 공부해 볼 생각이다.
오늘 풀어본 문제는 BOJ 21610 마법사 상어와 비바라기 문제이다. 역시나 내가 약한 시뮬레이션 문제이어서 풀어보았고 다행히 저번 유사한 문제를 풀 때 보다는 발전이 있었던 것 같다!
BOJ 21610 마법사 상어와 비바라기
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.
격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.
비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.
- 모든 구름이 di 방향으로 si칸 이동한다.
- 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
- 구름이 모두 사라진다.
- 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
- 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
- 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
- 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.
입출력
[입력]
첫째 줄에 N, M이 주어진다.
둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.
다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.
[출력]
첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.
[제한]
- 2 ≤ N ≤ 50
- 1 ≤ M ≤ 100
- 0 ≤ A[r][c] ≤ 100
- 1 ≤ di ≤ 8
- 1 ≤ si ≤ 50
나의 풀이
특별한 방법이라기 보단 꼼꼼하게 필요한 조건을 확인하고 수행하면 되는 문제이다. 간단해 보일 수 있고 간단한 문제이지만 실수가 잦은 난 이런 유형에 참 약하다.
문제 해결의 과정을 단계별로 나누어 보자면 구름 이동 -> 물복사버그 마법 -> 새로운 구름 생성 총 세 단계로 나누어져 있다.
구름 이동
먼저 구름을 이동시킨다. 나는 매번 모든 좌표를 확인하는 과정이 싫어 이전 구름의 위치를 따로 vector<pair<int,int>> cloud 배열에 저장해 두었다.
M 번의 이동 별로 이동 방향과 속도가 주어지는데 이 방향과 속동에 따라 구름이 이동하게 될 새로운 좌표를 구하는 과정에 주의해야 한다.
제한 사항을 보면 si 값은 최대 50까지 이므로 N 을 훌쩍 넘을 수 있다. 1행과 N 행이, 1열과 N 열이 연결되어 있기 때문에 si 값은 결국 mod 연산을 적용한 si % N 값과 동일하다는 것을 기억해야 한다!
mod 연산을 거친 si 값 만큼 di 방향으로 이동시킬 칸 수를 각각 두 변수 row_move, col_move 에 저장하고, 현재의 위치 cloud[i] 에 두 값을 각각 더해 격자 내에서 순환하도록 연산을 거쳤다.
나는 수학적으로 규칙을 찾는 특별한 묘안을 몰라 그냥 경우별로 그려보며 그 연산을 찾았는데 row_move, col_move 값을 더한 좌표가 격자 위치를 벗어나는 경우가 있기 때문에 먼저 row_move, col_move 에 각각 N을 더해주고, 이전 좌표에 더한 다음 mod 연산을 거쳐주면 순환하는 격자내에서의 올바른 이동 위치를 구할 수 있었다.
이렇게 새로운 구름의 위치를 구해 배열 new_cloud 에 저장하고 구름 위치의 바구니에 물을 1 증가시킨다. 또 N*N 배열의 isCloud 에 새로운 구름의 위치를 기록한다.
물복사버그
물복사버그는 간단하다.
new_cloud 에 담긴 새로운 구름의 위치 별로 대각선 방향으로 한칸 떨어진 칸 중 물이 존재하는 바구니의 수를 세고, 그 수 만큼 해당 칸의 바구니 물 양을 증가 시킨다. 대각선 방향이기 때문에 총 8개의 방향 중에서 홀수 index만 골라 격자 경계 안쪽의 칸만 확인해주면 된다.
새로운 구름 생성
이후에는 구름 이동시 새로운 구름의 위치를 체크 해 놓았던 N*N 크기의 격자 배열 isCloud 에 따라 구름이 아닌 위치의 바구니 속 물의 양이 2 보다 크다면 물의 양을 2 줄이고 해당 위치에 새로운 구름을 생성한다.
새로운 구름의 위치는 이전에 사용하던 배열 cloud 를 초기화 시키고 추가해 다음 이동때 사용할 수 있도록 한다!
코드
#include <iostream>
#include <vector>
// boj 21610 마법사 상어와 비바라기, 시뮬레이션, 골드 5
using namespace std;
int N, M;
vector<vector<int>> map;
vector<pair<int, int>> moving;
int dy[8] = {0,-1,-1,-1,0,1,1,1};
int dx[8] = {-1,-1,0,1,1,1,0,-1};
int moveCloud(){
int left = 0;
int order = 0;
vector<pair<int, int>> cloud;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i>=N-2 && i<= N-1 && j>=0 && j<=1) {
cloud.push_back({i, j});
};
}
}
while (order<M){
// 구름 이동, 비 1씩 내림
int dir = moving[order].first-1, speed = moving[order].second;
vector<pair<int, int>> new_cloud;
int row_move = dy[dir] * (speed%N);
int col_move = dx[dir] * (speed%N);
vector<vector<bool>> isCloud(N, vector<bool>(N, false));
for (int i = 0; i < cloud.size(); ++i) {
int nr = (cloud[i].first + row_move+N) % N;
int nc = (cloud[i].second + col_move+N) % N;
map[nr][nc] += 1;
isCloud[nr][nc] = true;
new_cloud.push_back({nr, nc});
}
// 물복사버그
for (int i = 0; i < new_cloud.size(); ++i) {
int count = 0;
for (int j = 1; j <8 ; j+=2) {
int nr = new_cloud[i].first + dy[j];
int nc = new_cloud[i].second + dx[j];
if (nr<0 || nr>=N || nc<0 || nc>=N) continue;
if (map[nr][nc]>0) count++;
}
map[new_cloud[i].first][new_cloud[i].second] += count;
}
new_cloud.clear();
cloud.clear();
// 새로운 구름 생성하기
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!isCloud[i][j] && map[i][j]>=2){
cloud.push_back({i,j});
map[i][j] -= 2;
}
if (order==M-1) left += map[i][j];
}
}
order++;
}
return left;
}
int main() {
cin>>N>>M;
map.assign(N, vector<int>(N));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin>>map[i][j];
}
}
moving.assign(M,{0,0});
for (int i = 0; i < M; ++i) {
cin>>moving[i].first>>moving[i].second;
}
int answer = moveCloud();
cout<<answer;
return 0;
}