예제 4번까지는 맞는데 복잡한 5번부터 틀려서 오류를 수정할 수 없다...
풀어본 삼성 기출 중 나무재테크 이후 가장 까다로운 문제 중 하나인 것 같다;ㅎ
문제
유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)의 온도를 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
구사과의 성능 테스트는 다음과 같은 작업이 순차적으로 이루어지며, 가장 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 의미한다.
- 집에 있는 모든 온풍기에서 바람이 한 번 나옴
- 온도가 조절됨
- 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
- 초콜릿을 하나 먹는다.
- 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.
집에 있는 모든 온풍기에서 바람이 한 번 나오는 과정을 설명하면 다음과 같다.
<그림 1>
<그림 1>은 크기가 7×8인 집에 온풍기가 (3, 1)에 설치되어 있는 상황이다. 온풍기는 바람이 나오는 방향이 있는데, 그 방향은 오른쪽, 왼쪽, 위, 아래 중 하나이다. 온풍기에서 따뜻한 바람이 한 번 나오면, 다음과 같은 영역의 온도가 칸에 적힌 값만큼 증가하게 된다. 아래 그림은 오른쪽 방향으로 바람이 나온 예시이며, 온풍기에서 바람이 나오는 방향에 따라 <그림 2>를 회전시켜서 해당하는 방향으로 바람이 나왔을 때 증가하는 온도를 구할 수 있다.
<그림 2>
온풍기에서 바람이 한 번 나왔을 때, 온풍기의 바람이 나오는 방향에 있는 칸은 항상 온도가 5도 올라간다. 그 다음 이 바람은 계속 다른 칸으로 이동해 다른 칸의 온도를 위의 그림과 같이 상승시키게 된다. 어떤 칸 (x, y)에 온풍기 바람이 도착해 온도가 k (> 1)만큼 상승했다면, (x-1, y+1), (x, y+1), (x+1, y+1)의 온도도 k-1만큼 상승하게 된다. 이때 그 칸이 존재하지 않는다면, 바람은 이동하지 않는다. 온풍기에서 바람이 한 번 나왔을 때, 어떤 칸에 같은 온풍기에서 나온 바람이 여러 번 도착한다고 해도 온도는 여러번 상승하지 않는다.
<그림 1>의 상태에서 온풍기 바람이 한 번 불었다면, 증가하는 온도의 양은 <그림 3>과 같다.
<그림 3>
일부 칸과 칸 사이에는 벽이 있어 온풍기 바람이 지나갈 수 없다. 바람이 오른쪽으로 불었을 때 어떤 칸 (x, y)에서 (x-1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x-1, y) 사이에 벽이 없어야 하고, (x-1, y)와 (x-1, y+1) 사이에도 벽이 없어야 한다. (x, y)에서 (x, y+1)로 바람이 이동할 수 있으려면 (x, y)와 (x, y+1) 사이에 벽이 없어야 한다. 마지막으로 (x, y)에서 (x+1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x+1, y), (x+1, y)와 (x+1, y+1) 사이에 벽이 없어야 한다.
예를 들어, (3, 4)와 (3, 5) 사이에 벽이 있는 경우 온풍기에서 바람이 한 번 나왔을 때 온도는 <그림 4>와 같이 상승한다. 벽은 빨간색으로 표시했다.
<그림 4>
(3, 5)는 (3, 4), (2, 4), (4, 4)에서 바람이 이동할 수 없기 때문에, 온도가 상승하지 않는다.
만약 바람의 방향이 왼쪽인 온풍기가 (4, 7)에 있고, (3, 4)와 (3, 5) 사이에 벽, (2, 5)와 (3, 5) 사이에 벽이 있는 경우라면 온풍기에서 바람이 한 번 나왔을 때 <그림 5>와 같이 온도가 상승한다. <그림 6>은 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, (4, 4)와 (4, 5) 사이, (4, 4)와 (5, 4) 사이, (4, 6)과 (5, 6) 사이에 벽이 있는 경우이다.
| <그림 5> | <그림 6> |
구사과의 집에는 온풍기가 2대 이상 있을 수도 있다. 이 경우 각각의 온풍기에 의해서 상승한 온도를 모두 합한 값이 해당 칸의 상승한 온도이다.
예를 들어, <그림 7>은 <그림 6>과 같은 벽을 가지고 있는 집에서 바람이 방향이 위인 온풍기가 (7, 5)에 있는 경우이고, <그림 8>는 <그림 6>과 같은 벽을 가지고 있는 집에서 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, 바람의 방향이 위인 온풍기가 (7, 5)에 있는 경우이다. <그림 8>는 같은 벽을 가지고 있는 집에서 <그림 6>의 온풍기와 <그림 7>의 온풍기가 동시에 설치된 상황이기 때문에, 각 칸의 상승한 온도는 두 그림의 값을 더한 값과 같다. 온풍기가 있는 칸도 다른 온풍기에 의해 온도가 상승할 수 있기 때문에, <그림 8>에서 온풍기의 위치는 표시하지 않았다.
| <그림 7> | <그림 8> |
온도가 조절되는 과정은 다음과 같다.
모든 인접한 칸에 대해서, 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이)/4⌋만큼 온도가 조절된다. 온도가 높은 칸은 이 값만큼 온도가 감소하고, 낮은 칸은 온도가 상승한다. 인접한 두 칸 사이에 벽이 있는 경우에는 온도가 조절되지 않는다. 이 과정은 모든 칸에 대해서 동시에 발생한다.
다음은 온도 조절의 예시이다.
(1, 1)에서 (1, 2)와 (1, 3)으로 공기가 섞인다.
(2, 2)와 (3, 2) 사이에 벽이 있기 때문에, (3, 2)는 온도가 그대로 유지된다.
모든 칸에 대해서 동시에 온도의 조절이 발생한다.
가장 바깥쪽 칸은 1행, R행, 1열, C열에 있는 칸이다. 예를 들어, <그림 9>와 같은 경우 가장 바깥쪽 칸의 온도가 1씩 감소하면 <그림 10>과 같이 된다. 온도가 0인 칸은 온도가 감소하지 않는다.
| <그림 9> | <그림 10> |
방의 크기와 방에 설치된 온풍기의 정보, 벽의 위치와 조사하려고 하는 칸의 위치가 주어진다. 구사과가 먹은 초콜릿의 개수를 출력한다.
https://www.acmicpc.net/problem/23289
23289번: 온풍기 안녕!
유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기
www.acmicpc.net
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int R, C, K, W;
int choco = 0;
//1:→,2:←, 3:↑, 4:↓
int y[] = { 0,0,0,-1,1};
int x[] = { 0,1,-1,0,0};
//x,y,t t=0: (x-1,y)|(x,y), t=1: (x,y)|(x,y+1)
//(y, x), wall's direction
vector<pair<pair<int, int>, int>> wall;
bool checkWall(int cwy, int cwx, int cwd) {
bool wallcheck = false;
for (int i = 0; i < wall.size(); i++) {
if (wall[i].second == cwd && wall[i].first.first == cwy && wall[i].first.second == cwx) {
wallcheck = true;
break;
}
else continue;
}
return wallcheck;
}
int main() {
cin >> R >> C >> K;
vector<vector<int> > input(R, vector<int>(C, 0));
vector<vector<int> > room(R, vector<int>(C, 0));
//hit air blower ((y,x),dir) 1:→,2:←, 3:↑, 4:↓
vector<pair<pair<int, int>, int> > blower;
vector<pair<int, int> > check;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> input[i][j];
if (input[i][j] == 5) check.push_back(make_pair(i, j));
else if (input[i][j] >= 1 && input[i][j] < 5) blower.push_back(make_pair(make_pair(i, j), input[i][j]));
}
}
cin >> W;
for (int i = 0; i < W; i++) {
int wy, wx, wt;
cin >> wy >> wx >> wt;
if (wt == 0) {
wall.push_back(make_pair(make_pair(wy-1, wx-1), 4));
if(wy - 2 >= 0) wall.push_back(make_pair(make_pair(wy-2, wx-1), 3));
}
else if (wt == 1) {
wall.push_back(make_pair(make_pair(wy-1, wx-1), 2));
if (wx < C) wall.push_back(make_pair(make_pair(wy-1, wx), 1));
}
}
/*
cout << "wall : " << endl;
for (int i = 0; i < wall.size(); i++) {
cout << wall[i].first.first << ", " << wall[i].first.second <<" "<<wall[i].second<<endl;
}*/
bool stop = true;
while (stop) {
for (int i = 0; i < blower.size(); i++) {
int dir = blower[i].second;
int by = blower[i].first.first, bx = blower[i].first.second;
vector<pair<int, int>> next;
next.push_back(make_pair(y[dir], x[dir]));
if (y[dir] == 0) {
next.push_back(make_pair(-1, x[dir]));
next.push_back(make_pair(1, x[dir]));
}
else {
next.push_back(make_pair(y[dir], -1));
next.push_back(make_pair(y[dir], 1));
}
queue<pair<int, int>> q;
int visit[20][21] = { 0, };
int temp = 5;
q.push(make_pair(by + y[dir], bx + x[dir]));
visit[by + y[dir]][bx + x[dir]] = 1;
room[by + y[dir]][bx + x[dir]] += temp--;
int qsize = q.size();
int popcnt = 0;
while (!q.empty() && temp != 0) {
if (popcnt == qsize) {
qsize = q.size();
popcnt = 0;
temp--;
}
int sy = q.front().first, sx = q.front().second;
//cout << "sy,sx : " << sy << ", " << sx << " qsize : " << q.size()<<endl;
q.pop(), popcnt++;
for (int j = 0; j < 3; j++) {
int ny = sy + next[j].first, nx = sx + next[j].second;
//cout << "ny,nx : " << ny << ", " << nx << endl;
if (checkWall(ny, nx, dir)) continue;;
if (ny >= R || ny < 0 || nx >= C || nx < 0 || visit[ny][nx] == 1) continue;
room[ny][nx] += temp;
q.push(make_pair(ny, nx));
visit[ny][nx] = 1;
}
}
}
vector<vector<int> > tmp;
tmp = room;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
for (int k = 1; k <= 4; k++) {
int cy = i + y[k], cx = j + x[k];
if (cy >= R || cy < 0 || cx >= C || cx < 0) continue;
int diff = room[i][j] - room[cy][cx];
if (diff > 0 && !checkWall(cy, cx, k)) {
//cout << "mv : " << i << ", " << j << " -> " << cy << ", " << cx << "k : " << k << endl;
tmp[cy][cx] += diff / 4;
tmp[i][j] -= diff / 4;
}
}
}
}
for (int i = 1; i < C - 1; i++) {
if (tmp[0][i] != 0) tmp[0][i]--;
if (tmp[R - 1][i] != 0) tmp[R - 1][i]--;
}
for (int i = 1; i < R - 1; i++) {
if (tmp[i][0] != 0) tmp[i][0]--;
if (tmp[i][C - 1] != 0) tmp[i][C - 1]--;
}
if (tmp[0][0] != 0) tmp[0][0]--;
if (tmp[0][C - 1] != 0) tmp[0][C - 1]--;
if (tmp[R - 1][0] != 0) tmp[R - 1][0]--;
if (tmp[R - 1][C - 1] != 0) tmp[R - 1][C - 1]--;
choco++;
room = tmp;
/*
for (int a = 0; a < R; a++) {
for (int b = 0; b < C; b++)
cout << tmp[a][b] << " ";
cout << endl;
}cout << endl;
*/
for (int i = 0; i < check.size(); i++) {
if (room[check[i].first][check[i].second] < K) break;
else {
stop = false;
break;
}
}
}
cout << choco << endl;
return 0;
}'Coding Test' 카테고리의 다른 글
| [백준]17837 새로운 게임2 (0) | 2022.04.28 |
|---|---|
| [백준]20055 컨베이어 벨트 위의 로봇(57%시간초과) (0) | 2022.04.26 |
| [카카오]Lv2 땅따먹기 C++ (재귀,DP) (0) | 2022.04.23 |
| [카카오]Lv2 영어 끝말잇기 C++ (0) | 2022.04.23 |
| [카카오]Lv2 삼각 달팽이 C++ (0) | 2022.04.23 |