문제
유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 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) 사이에 벽이 있는 경우이다.
예를 들어, <그림 7>은 <그림 6>과 같은 벽을 가지고 있는 집에서 바람이 방향이 위인 온풍기가 (7, 5)에 있는 경우이고, <그림 8>는 <그림 6>과 같은 벽을 가지고 있는 집에서 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, 바람의 방향이 위인 온풍기가 (7, 5)에 있는 경우이다. <그림 8>는 같은 벽을 가지고 있는 집에서 <그림 6>의 온풍기와 <그림 7>의 온풍기가 동시에 설치된 상황이기 때문에, 각 칸의 상승한 온도는 두 그림의 값을 더한 값과 같다. 온풍기가 있는 칸도 다른 온풍기에 의해 온도가 상승할 수 있기 때문에, <그림 8>에서 온풍기의 위치는 표시하지 않았다.구사과의 집에는 온풍기가 2대 이상 있을 수도 있다. 이 경우 각각의 온풍기에 의해서 상승한 온도를 모두 합한 값이 해당 칸의 상승한 온도이다.
모든 인접한 칸에 대해서, 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이)/4⌋만큼 온도가 조절된다. 온도가 높은 칸은 이 값만큼 온도가 감소하고, 낮은 칸은 온도가 상승한다. 인접한 두 칸 사이에 벽이 있는 경우에는 온도가 조절되지 않는다. 이 과정은 모든 칸에 대해서 동시에 발생한다.온도가 조절되는 과정은 다음과 같다.
가장 바깥쪽 칸은 1행, R행, 1열, C열에 있는 칸이다. 예를 들어, <그림 9>와 같은 경우 가장 바깥쪽 칸의 온도가 1씩 감소하면 <그림 10>과 같이 된다. 온도가 0인 칸은 온도가 감소하지 않는다.
방의 크기와 방에 설치된 온풍기의 정보, 벽의 위치와 조사하려고 하는 칸의 위치가 주어진다. 구사과가 먹은 초콜릿의 개수를 출력한다.
입력
첫째 줄에 세 정수 R, C, K가 주어진다. 둘째 줄부터 R개의 줄에 방의 정보가 주어진다. i번째 줄의 j번째 정수는 (i, j)의 정보를 의미하며 다음 중 하나이다.
- 0: 빈 칸
- 1: 방향이 오른쪽인 온풍기가 있음
- 2: 방향이 왼쪽인 온풍기가 있음
- 3: 방향이 위인 온풍기가 있음
- 4: 방향이 아래인 온풍기가 있음
- 5: 온도를 조사해야 하는 칸
다음 줄에는 벽의 개수 W가 주어진다. 다음 W개의 줄에는 벽의 정보가 주어지며, 이 정보는 세 정수 x, y, t로 이루어져 있다. t가 0인 경우 (x, y)와 (x-1, y) 사이에 벽이 있는 것이고, 1인 경우에는 (x, y)와 (x, y+1) 사이에 벽이 있는 것이다.
출력
구사과가 먹는 초콜릿의 개수를 출력한다. 만약, 먹는 초콜릿의 개수가 100을 넘어가면 101을 출력한다.
제한
- 2 ≤ R, C ≤ 20
- 1 ≤ K ≤ 1,000
- 온풍기는 하나 이상 있고, 온도를 조사해야 하는 칸도 하나 이상 있다.
- 0 ≤ W ≤ R×C
- 1 < x ≤ R, 1 ≤ y ≤ C (t = 0)
- 1 ≤ x ≤ R, 1 ≤ y < C (t = 1)
- 온풍기가 있는 칸과 바람이 나오는 방향에 있는 칸 사이에는 벽이 없다.
- 온풍기의 바람이 나오는 방향에 있는 칸은 항상 존재한다.
- 같은 벽이 두 번 이상 주어지는 경우는 없다.
구현해야할 조건
정말정말 구현하기 까다롭고, 한번 놓치기 시작하면 함정으로 빠질 수 있는 문제이다. 다음에 확실히 정리해서 올리도록 하게씁니다!
code
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#define MAX 21
using namespace std;
typedef struct{
int y;
int x;
int dir;
}Heater;
typedef struct{
int y;
int x;
int temper;
}moving;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,-1,1}; // right, left, up, down
int r,c,k,w;
int board[MAX][MAX];
int temperBoard[MAX][MAX];
int tempBoard[MAX][MAX];
bool visited[MAX][MAX];
int wall[MAX][MAX][2];
vector<pair<int,int> > temperature;
vector<Heater> heaters;
void print()
{
cout << endl;
cout << endl;
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
cout << temperBoard[i][j] << " ";
}
cout << endl;
}
}
void move(int y, int x, int dir, int num)
{
memset(visited,false,sizeof(visited));
queue<moving> q;
q.push({y,x,num});
if(dir == 1 || dir == 2) // right, left
{
while(!q.empty())
{
int y = q.front().y;
int x = q.front().x;
int t = q.front().temper;
q.pop();
if(t == 0)
continue;
int ny = y + dy[dir];
int nx = x + dx[dir];
if(0 <= nx && nx < c && 0 <= ny && ny < r )
{
if(wall[y][x][1] != 1 && dir == 1 && !visited[ny][nx]) // right
{
visited[ny][nx] = true;
temperBoard[ny][nx] += t;
q.push({ny,nx,t-1});
}
else if(wall[ny][nx][1] != 1 && dir == 2 && !visited[ny][nx]) // left
{
visited[ny][nx] = true;
temperBoard[ny][nx] += t;
q.push({ny,nx,t-1});
}
}
for(int i = 3; i < 5; i++)
{
int ny = y + dy[i];
int nx = x + dx[i]; // 위, 아래 이동
if(!(0 <= nx && nx < c && 0 <= ny && ny < r))
continue;
if(wall[y][x][0] == 2 && i == 3)
continue;
if(wall[ny][nx][0] == 2 && i == 4)
continue;
int nny = ny + dy[dir];
int nnx = nx + dx[dir]; // 본방향대로 이동
if(!visited[nny][nnx] && wall[ny][nx][1] != 1 && dir == 1)
{
visited[nny][nnx] = true;
temperBoard[nny][nnx] += t;
q.push({nny,nnx,t-1});
}
else if(!visited[nny][nnx] && wall[nny][nnx][1] != 1 && dir == 2)
{
visited[nny][nnx] = true;
temperBoard[nny][nnx] += t;
q.push({nny,nnx,t-1});
}
}
}
}
else // 3 : up, 4 : down
{
while(!q.empty())
{
int y = q.front().y;
int x = q.front().x;
int t = q.front().temper;
q.pop();
if(t == 0)
continue;
int ny = y + dy[dir];
int nx = x + dx[dir];
// 내려가려고 할 때
if(0 <= nx && nx < c && 0 <= ny && ny < r)
{
if(wall[ny][nx][0] != 2 && !visited[ny][nx] && dir == 4)
{
visited[ny][nx] = true;
temperBoard[ny][nx] += t;
q.push({ny,nx,t-1});
} // down
else if(wall[y][x][0] != 2 && !visited[ny][nx] && dir == 3)
{
visited[ny][nx] = true;
temperBoard[ny][nx] += t;
q.push({ny,nx,t-1});
} // up
}
for(int i = 1; i <= 2; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(wall[y][x][1] == 1 && i == 1)
continue;
if(wall[ny][nx][1] == 1 && i == 2)
continue;
if(!(0 <= nx && nx < c && 0 <= ny && ny < r))
continue;
int nny = ny + dy[dir];
int nnx = nx + dx[dir];
if(!visited[nny][nnx] && wall[nny][nnx][0] != 2 && dir == 4)
{
visited[nny][nnx] = true;
temperBoard[nny][nnx] += t;
q.push({nny,nnx,t-1});
} // down
else if(!visited[nny][nnx] && wall[ny][nx][0] != 2 && dir == 3)
{
//cout << ny << " " << nx << endl;
visited[nny][nnx] = true;
temperBoard[nny][nnx] += t;
q.push({nny,nnx,t-1});
} // up
}
}
}
}
//두칸의 온도의 차이 / 4이다
void BFS(int y, int x)
{
queue<pair<int,int> > q;
q.push({y,x});
while(!q.empty())
{
vector<int> v;
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i = 1; i <= 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(0 <= nx && nx < c && 0 <= ny && ny < r)
{
if(temperBoard[y][x] > temperBoard[ny][nx])
{
if(i == 1 && wall[y][x][1] == 1) //right
continue;
if(i == 2 && wall[ny][nx][1] == 1) // left
continue;
if(i == 3 && wall[y][x][0] == 2) // up
continue;
if(i == 4 && wall[ny][nx][0] == 2) // down
continue;
int num = (temperBoard[y][x] - temperBoard[ny][nx])/4;
if(num == 0)
continue;
tempBoard[ny][nx] += num;
v.push_back(num);
}
}
}
for(int i = 0; i < v.size(); i++)
{
tempBoard[y][x] -= v[i];
}
}
}
int main()
{
cin >> r >> c >> k;
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
cin >> board[i][j];
if(1 <= board[i][j] && board[i][j] <= 4)
{
heaters.push_back({i,j,board[i][j]}); // y,x,dir
}
else if(board[i][j] == 5)
{
temperature.push_back({i,j}); // y,x
}
}
}
cin >> w;
for(int i = 0; i < w; i++)
{
int y,x,t;
cin >> y >> x >> t;
if(t == 0) // 위쪽
{
wall[y-1][x-1][0] = 2;
}
else // 우측
{
wall[y-1][x-1][1] = 1;
}
}
int chocolate = 0;
//1. 집에있는 모든 온풍기에서 바람이 한 번 나옴
for(int i = 0; i < heaters.size(); i++)
{
int y = heaters[i].y;
int x = heaters[i].x;
int dir = heaters[i].dir;
int ny = y + dy[dir];
int nx = x + dx[dir];
temperBoard[ny][nx] += 5;
move(ny,nx,dir,4);
}
int temp[MAX][MAX];
memset(temp,0,sizeof(temp));
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
temp[i][j] = temperBoard[i][j];
}
}
while(chocolate <= 100)
{
// 2. 온도가 조절됨
memset(tempBoard,0,sizeof(tempBoard));
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
if(temperBoard[i][j]==0)
continue;
BFS(i,j);
}
}
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
temperBoard[i][j] += tempBoard[i][j];
}
}
//3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
if(i ==0 || j == 0 || i == r-1 || j == c-1)
{
if(temperBoard[i][j] == 0)
continue;
temperBoard[i][j] -= 1;
}
}
}
//4.초콜릿을 하나 먹는다.
chocolate++;
//5. 모든 칸이 k 이상이 되었는지 검사.
int cnt = 0;
int size = temperature.size();
for(int i = 0; i < temperature.size(); i++)
{
if(temperBoard[temperature[i].first][temperature[i].second] >= k)
cnt++;
}
// 5-1) 모든 칸의 온도가 k이상이면 테스트를 중단하고, 아니면 1부터 다시 시작
if(cnt == size)
break;
// 1. 바람이 다시 분다.
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
temperBoard[i][j] += temp[i][j];
}
}
}
if(chocolate > 100)
cout << 101;
else
cout << chocolate;
return 0;
}'PS > Samsung' 카테고리의 다른 글
| [백준/c++] 20057 마법사 상어와 토네이도 (0) | 2022.04.06 |
|---|---|
| [백준/c++] 23288 주사위 굴리기2 (0) | 2022.02.24 |
| [백준/c++] 21611 마법사 상어와 블리자드 (0) | 2022.02.23 |
| [백준/c++] 21610 마법사 상어와 비바라기 (0) | 2022.02.22 |
| [백준/c++] 20056 마법사 상어와 파이어볼 (0) | 2022.02.20 |
