알고리즘 문제
[백준] 17144번 미세먼지 안녕!
feelcoding
2020. 1. 28. 02:44
728x90
삼성 SW 역량 테스트 기출 문제인 17144번 문제
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼
www.acmicpc.net
#include <iostream>
#include <tuple>
using namespace std;
int main() {
int r, c, t;
cin >> r >> c >> t;
int** room = new int*[r];
int** copyRoom = new int*[r];
int** spreadRoom = new int*[r];
for (int i = 0; i < r; i++) {
room[i] = new int[c];
copyRoom[i] = new int[c];
spreadRoom[i] = new int[c];
}
pair<int, int> purifier[2];
int index = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> room[i][j];
if (room[i][j] == -1) {
purifier[index] = make_pair(i, j);
index++;
}
}
}
for (int time = 0; time < t; time++) {
if (time != 0) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
room[i][j] = spreadRoom[i][j];
}
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
copyRoom[i][j] = room[i][j] / 5;
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
spreadRoom[i][j] = 0;
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
int count = 0;
if (i - 1 >= 0 && !(i - 1 == purifier[0].first && j == purifier[0].second) && !(i - 1 == purifier[1].first && j == purifier[1].second)) {
spreadRoom[i - 1][j] += copyRoom[i][j];
count++;
}
if (i + 1 < r && !(i + 1 == purifier[0].first && j == purifier[0].second) && !(i + 1 == purifier[1].first && j == purifier[1].second)) {
spreadRoom[i + 1][j] += copyRoom[i][j];
count++;
}
if (j - 1 >= 0 && !(i == purifier[0].first && j - 1 == purifier[0].second) && !(i == purifier[1].first && j - 1 == purifier[1].second)) {
spreadRoom[i][j - 1] += copyRoom[i][j];
count++;
}
if (j + 1 < c && !(i == purifier[0].first && j + 1 == purifier[0].second) && !(i == purifier[1].first && j + 1 == purifier[1].second)) {
spreadRoom[i][j + 1] += copyRoom[i][j];
count++;
}
spreadRoom[i][j] += room[i][j] - count * copyRoom[i][j];
}
}
int direction = 0; //위는 0, 오른쪽은 1, 아래는 2, 왼쪽은 3
int row = purifier[0].first - 1;
int col = purifier[0].second;
while (true) {
if (direction == 0) { //위쪽 방향일 때
if (row - 1 >= 0) {
spreadRoom[row][col] = spreadRoom[row - 1][col];
row--;
}
else
direction = 1;
}
if (direction == 1) { //오른쪽 방향일 때
if (col + 1 < c) {
spreadRoom[row][col] = spreadRoom[row][col + 1];
col++;
}
else
direction = 2;
}
if (direction == 2) { //아래 방향일 때
if (row + 1 <= purifier[0].first) {
spreadRoom[row][col] = spreadRoom[row + 1][col];
row++;
}
else direction = 3;
}
if (direction == 3) {
if (col - 1 >= 0) {
if (spreadRoom[row][col - 1] == -1) {
spreadRoom[row][col] = 0;
col--;
direction = 0;
break;
}
else spreadRoom[row][col] = spreadRoom[row][col - 1];
col--;
}
}
}
direction = 0;
row = purifier[1].first + 1;
col = purifier[1].second;
while (true) {
if (direction == 0) { //아래쪽 방향일 때
if (row + 1 < r) {
spreadRoom[row][col] = spreadRoom[row + 1][col];
row++;
}
else
direction = 1;
}
if (direction == 1) { //오른쪽 방향일 때
if (col + 1 < c) {
spreadRoom[row][col] = spreadRoom[row][col + 1];
col++;
}
else
direction = 2;
}
if (direction == 2) { //위쪽 방향일 때
if (row - 1 >= purifier[1].first) {
spreadRoom[row][col] = spreadRoom[row - 1][col];
row--;
}
else direction = 3;
}
if (direction == 3) { //왼쪽 방향일 때
if (col - 1 >= 0) {
if (spreadRoom[row][col - 1] == -1) {
spreadRoom[row][col] = 0;
col--;
direction = 0;
break;
}
else spreadRoom[row][col] = spreadRoom[row][col - 1];
col--;
}
}
}
}
int sum = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
sum += spreadRoom[i][j];
}
}
cout << sum + 2 << endl;
return 0;
}728x90