어제.. 부터 오늘까지(^^;;) 푼 문제는 BOJ 17144 미세먼지 안녕! 이다!
시뮬레이션 문제고 역시나 특별히 어려운 알고리즘이 쓰이진 않았지만 이것저것 신경써줘야 하는 부분이 많은, 집중력, 지구력이 필요한 문제였다!
BOJ 17144 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5이고 소수점은 버린다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.!
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
입출력
나의 풀이
이 문제는 크게 2부분 먼지 확신 + 공기청정기 가동 으로 나누어서 접근했다.
먼지 확산
먼지 확산 전에 2차원 배열 map에 공기 청정기 위치와 각 칸의 먼지양을 입력 받으면서 map과 동일한 크기를 갖는 2차원 배열 diffuse 를 완성하였다.
diffuse[i][j] 에는 map[i][j] 에서 주변으로 확산 될 수 있는 먼지량, map[i][j]/5 가 저장된다.
map[i][j] 에서 주변으로 먼지가 확산될 수 있으면 즉, diffuse[i][j] > 0 이면 해당 칸의 인접한 칸들을 탐색하며 (i,j)로 들어올 수 있는 먼지 확산량을 계산하고, 동시에 인접한 칸 수를 센다.
이후 map[i][j] = 자신이 가지고 있던 먼지를 확산 시키고 난 이후의 먼지량 + (i,j)로 확산되어 오는 먼지량 을 계산해주며 먼지 확산 과정을 구현한다.
먼지 확산 코드
// 1. 확산
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if(diffuse[i][j] >= 0){
int diffuseSum = 0, neighbor = 0;
//인접한 4방향으로부터 받는 먼지가 있는지, 이웃 수가 몇명인지 계산
for (int k = 0; k < 4; ++k) {
int nr = i + dy[k];
int nc = j + dx[k];
if (nr>=0 && nr<R && nc>=0 && nc<C && map[nr][nc] != -1){
diffuseSum += diffuse[nr][nc];
neighbor++;
}
}
// 이웃에게 확산되는 먼지 반영, 인접한 칸으로부터 받는 먼지 반영
if (diffuse[i][j] == 0){
map[i][j] += diffuseSum;
}else{
map[i][j] = map[i][j] - (diffuse[i][j] * neighbor) + diffuseSum;
}
}
}
}공기 청정기 가동
먼지가 확산되었으면 공기청정기가 가동될 차례이다.
처음엔 먼지 확산이 더 어려울거라 생각했는데 오히려 이 부분에서 시간이 많이 걸렸다!
현재 위치를 가리키는 좌표 값 location 을 기준으로 하여 location 이전 위치에서 밀려 들어오는 먼지를 옮겨준 뒤 locaiton 을 이동시킨다.
이 때 location 이 새로운 위치로 이동이 가능한지를 체크하는데 이부분이 어쩌면 핵심이라고 볼 수도 있겠다!
공기청정기가 공기를 순환시키는 방향을 보면 위쪽 영역과 아래쪽 영역의 순화 방향이 4가지 순서로 이루어져 있고
location이 파란색 동그라미 위치에 있을 때 방향 전환이 일어난다.
현재 이동 방향을 moveIndex 변수로 관리하고 i, j 가 moveIndex 에 따라 이동할 때 변화하는 값을 upperY[4] = {0, -1, 0, 1}, upperX[4] = {0, 1, 0, -1} (아래쪽 공기 청정기에도 동일한 방법으로 적용) 로 관리한다.
이동 중 파란 동그라미 영역에 위치할 때 moveIndex를 변경시키고 더이상 이동할 공간이 없거나 공기 청정기를 만났을 때에는 false 값을 반환하여 이동을 중단시킨다.
공기 청정기 가동 코드
// 정화 단계, 현재 location 기준으로 값을 옮기고 더 나아갈 수 있으면 반복
void clean(pair<int, int> start, bool isUpeer){
pair<int, int> location = start;
int temp1 = -1, temp2;
bool movable = true;
int moveIndex = 0;
while (movable){
if(temp1 == -1) temp1 = 0;
// location 위치에 새롭게 들어올 먼지 (temp1) 교체, location에 원래 있던 먼지량을 temp1에 다시
temp2 = map[location.first][location.second];
map[location.first][location.second] = temp1;
temp1 = temp2;
// movable 인지 판단
if (isUpeer){
movable = isMovable(location, moveIndex, true);
}else{
movable = isMovable(location, moveIndex, false);
}
}
}전체 코드
#include <iostream>
#include <vector>
// BOJ 17144 미세먼지 안녕!, simulation
using namespace std;
int R, C, T;
vector<vector<int>> map;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int upperY[4] = {0, -1, 0, 1};
int upperX[4] = {1, 0, -1, 0};
int bottomY[4] = {0, 1, 0, -1};
int bottomX[4] = {1, 0, -1, 0};
// 현재 location 좌표 기준으로 moveIndex 방향으로 이동할 수 있는지, 이동할 수 있다면 새로운 좌표로 location 변경
bool isMovable(pair<int, int> & location, int & index, bool isUpper){
int nr, nc;
if (isUpper){
nr = location.first + upperY[index];
nc = location.second + upperX[index];
if(nr>=0 && nr<R && nc>=0 && nc<C){
if (map[nr][nc] == -1) return false;
location.first = nr;
location.second = nc;
return true;
}else {
if (index < 3) {
index++;
nr = location.first + upperY[index];
nc = location.second + upperX[index];
if(nr>=0 && nr<R && nc>=0 && nc<C){
location.first = nr;
location.second = nc;
return true;
}else return false;
}
return false;
}
}else{
nr = location.first + bottomY[index];
nc = location.second + bottomX[index];
if(nr>=0 && nr<R && nc>=0 && nc<C){
if (map[nr][nc] == -1) return false;
location.first = nr;
location.second = nc;
return true;
}else {
if (index < 3) {
index++;
nr = location.first + bottomY[index];
nc = location.second + bottomX[index];
if(nr>=0 && nr<R && nc>=0 && nc<C){
location.first = nr;
location.second = nc;
return true;
}else return false;
}
return false;
}
}
}
// 정화 단계, 현재 location 기준으로 값을 옮기고 더 나아갈 수 있으면 반복
void clean(pair<int, int> start, bool isUpeer){
pair<int, int> location = start;
int temp1 = -1, temp2;
bool movable = true;
int moveIndex = 0;
while (movable){
if(temp1 == -1) temp1 = 0;
// location 위치에 새롭게 들어올 먼지 (temp1) 교체, location에 원래 있던 먼지량을 temp1에 다시
temp2 = map[location.first][location.second];
map[location.first][location.second] = temp1;
temp1 = temp2;
// movable 인지 판단
if (isUpeer){
movable = isMovable(location, moveIndex, true);
}else{
movable = isMovable(location, moveIndex, false);
}
}
}
int getLeftDust(vector<vector<int>> diffuse, pair<int, int> cleaner){
int totalDust;
while (T > 0){
T--;
totalDust = 0;
// 1. 확산
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if(diffuse[i][j] >= 0){
int diffuseSum = 0, neighbor = 0;
//인접한 4방향으로부터 받는 먼지가 있는지, 이웃 수가 몇명인지 계산
for (int k = 0; k < 4; ++k) {
int nr = i + dy[k];
int nc = j + dx[k];
if (nr>=0 && nr<R && nc>=0 && nc<C && map[nr][nc] != -1){
diffuseSum += diffuse[nr][nc];
neighbor++;
}
}
// 이웃에게 확산되는 먼지 반영, 인접한 칸으로부터 받는 먼지 반영
if (diffuse[i][j] == 0){
map[i][j] += diffuseSum;
}else{
map[i][j] = map[i][j] - (diffuse[i][j] * neighbor) + diffuseSum;
}
}
}
}
// 2. 정화
clean(make_pair(cleaner.first, 1), true);
clean(make_pair(cleaner.second, 1), false);
// 3. diffuse 배열 재계산, 전체 먼지량 계산
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (map[i][j] == -1){
diffuse[i][j] = -1;
} else{
totalDust += map[i][j];
if (map[i][j] > 0){
diffuse[i][j] = map[i][j]/5;
} else{
diffuse[i][j] = 0;
}
}
}
}
}
return totalDust;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>R>>C>>T;
map.assign(R, vector<int>(C, 0));
vector<vector<int>> diffuse(R, vector<int>(C, 0)); // 각 칸에서 확산될 수 있는 양 계산
pair<int, int> cleaner = make_pair(-1, -1); // 공기청정기 위치 (행)
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
cin>>map[i][j];
if (map[i][j] == -1){
if(cleaner.first == -1) {
cleaner.first = i;
}else{
cleaner.second = i;
}
diffuse[i][j] = -1;
}
if (map[i][j] > 0){
diffuse[i][j] = map[i][j]/5;
}
}
}
int left = getLeftDust(diffuse, cleaner);
cout<<left;
return 0;
}
아우.. 시뮬레이션은 오래 걸려서 싫어..