문제 이해 단계
https://www.acmicpc.net/problem/17144
문제가 복잡하게 써져 있는데,
최대한 간략하게 요약하자면 RxC 맵에 숫자 정보들이 나와있다.
0은 빈 곳, -1은 공기 청정기, 1이상의 수는 미세먼지의 양이다.
미세먼지는 1초당 상하좌우로 자신의 미세먼지 양 /5 만큼 퍼지고
(자기 자신의 미세먼지 - 미세먼지/5 확산한 방향 개수)로
그 자리의 미세먼지 양을 수정한다.
미세먼지가 확산될 때 공기청정기 쪽으로는 확산될 수 없다.
그리고 공기청정기가 두대가 설치되어 있는데,
공기 청정기는 무조건 1행만 존재하고 위아래 두 개로 무조건 붙어있다.
공기 청정기의 위 칸은 반시계 방향으로, 아래칸은 시계 방향으로 움직인다.
미세먼지가 확산된 이후, 위에 그려진 경로에 따라 미세먼지를 한 칸씩 이동시킨다.
공기 청정기에 들어간 미세먼지는 무조건 정화되어 0이 된다.
이런 규칙을 따를 때 T초 이후의 미세먼지의 총합을 구하는 문제
문제 접근 단계
문제의 유형부터 생각해 보자.
일단 여러 가지 조건이 많고, 2차원 맵이 주어졌다.
여러 가지 조건이 주어진 것 자체가 구현문제일 확률이 높다.
생각할 건 많이 없으나 구현을 해보라는 뜻일 것이다.
그리고 미세먼지의 확산이 상하좌우로 된다는 것은 BFS가 떠오른다.
미세먼지의 확산 부분에서는 BFS의 구현이라고 할 수 있다.
BFS 하는 중에 값을 확인해서 문제에서 제시한 연산을 하면 될 것 같다.
이제 공기청정기의 회전에 관한 문제에 대해 생각해 보자.
먼지를 시계 / 반시계 방향으로 한 칸씩 옮긴다는 말은, 배열을 회전시킨다는 말과 같다.
그래서 해당 부분은 2차원 배열을 회전시킬 수 있는지에 대해 묻는 것 같다.
요약하자면
1. BFS를 통해 구현해라
2. 2차원 함수를 시계/반시계 방향으로 회전시켜라
이 2가지를 묻는 문제 같다.
값 계산 시 유의할 점
이에 따라 1번부터 구현을 해 보다 보면 값을 계산할 때 문제가 생긴다.
문제에서는 분명 미세먼지의 확산은 동시에 일어난다고 했다.
그런데 BFS는 순서라는 것이 존재한다.
그래서 순서에 따라 값이 달라질 수도 있다는 소리이다.
이 점을 어떻게 해결할까?
나는 정답을 담을 2차원 배열을 만들어서, 정답 값만 거기에 저장해 두는 방법을 사용했다.
그렇게 하면 원본 값은 바뀌지 않으면서 정답 값을 알 수 있다.
그 후 BFS가 종료되면 map에 정답 값을 넣어서 동기화시킨다.
이제 문제가 되는 부분들은 다 해결한 것 같으니, 이제 아래에서 코드로 살펴보자.
나머지 부분은 그냥 코드로 보는 게 훨씬 편하다.
문제 구현 단계
// x,y 좌표를 나타내는 구조체
struct Point{
int x;
int y;
};
int R,C; // 행,렬
int map[51][51];
vector<Point> dust; // 미세먼지 위치 배열
Point machine[2]; // 공기 정청기 위치 배열
void bfs(){
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int cmap[51][51] = {0,}; // 값을 담을 배열
// 미세먼지의 개수만큼 반복
for(int i = 0; i < dust.size(); i++){
int x = dust[i].x;
int y = dust[i].y;
int val = map[x][y];
int count = 0; // 몇개를 확산했는지 세기
for(int j = 0; j < 4; j++){
int nx = x + dx[j];
int ny = y + dy[j];
// 공기 청정기와의 충돌 체크와 범위 체크
if(nx > R || nx < 1 || ny > C || ny < 1
|| map[nx][ny] == -1) continue;
cmap[nx][ny] += val/5; // 값 계산
count++;
}
val = val - (val/5) * count; // 값 계산
cmap[x][y] += val;
}
// 배열에 담아뒀던 값을 map에 넣음(동기화)
for(int i = 1; i <= R; i++){
for(int j = 1; j <= C; j++)
if(cmap[i][j] > 0) map[i][j] = cmap[i][j];
}
}미세먼지를 확산시키고 값을 계산하는 BFS함수이다.
좌표값을 직관적으로 보기 위해 Point라는 구조체를 새로 만들었다.
아까 말했듯 값을 담아둘 cmap이라는 2차원 배열을 map의 배열만큼 만들어둔다.
이후, 미세먼지의 정보를 담고 있는 dust 벡터의 개수만큼 확산을 반복한다.
이때 R와 C의 범위, 공기 청정기와 접촉하는지에 대한 범위를 확인하여
그 안에 있을 때만 연산을 진행해 준다.
그리고 연산에 확산된 방향의 개수도 중요하기 때문에
count라는 변수를 만들었다.
미세먼지 개수만큼 반복을 하고 나면,
모든 탐색이 끝난 것으로 판단하고 cmap에 있던 값을 모두 map에 담는다.
이게 미세먼지 확산의 끝이다.
미세먼지의 확산이 끝났기 때문에 이제 공기청정기를 통해 회전시켜야 한다.
void operating(){
// 위쪽 방향(반시계 방향이니까 시계 방향)
int dx1[] = {-1,0,1,0};
int dy1[] = {0,1,0,-1};
int k = 0; // 방향
// 위쪽 공기 청정기
int x = machine[0].x;
int y = machine[0].y;
while(k < 4){
int nx = x + dx1[k];
int ny = y + dy1[k];
if(nx == machine[0].x && ny == machine[0].y){
/*
돌고 돌아서 다시 공기 청정기로 오면 종료
이때 이 값을 가져오려는 위치는 0을 가져야함
공기 청정기를 지나면 먼지가 정화되기 때문
*/
map[x][y] = 0;
break;
}
// 범위 체크 -> 최대범위 = 공기청정기가 있는 곳
if(1 <= nx && nx <= machine[0].x
&& 1 <= ny && ny <= C){
map[x][y] = map[nx][ny];
x = nx;
y = ny;
}
else k++; // 범위를 벗어나면 방향 바꿈
}
map[machine[0].x][machine[0].y+1] = 0; // 혹시 몰라 한번 더 해줌
map[machine[0].x][machine[0].y] = -1; // 공기 청정기 위치에 -1을 넣어줌
// 아래족 방향(시계방향이니까 반시계 방향)
int dx2[] = {1,0,-1,0};
int dy2[] = {0,1,0,-1};
k = 0;
x = machine[1].x;
y = machine[1].y;
while(k < 4){
int nx = x + dx2[k];
int ny = y + dy2[k];
if(nx == machine[1].x && ny == machine[1].y){
map[x][y] = 0;
break;
}
if(machine[1].x <= nx && nx <= R
&& 1 <= ny && ny <= C){
map[x][y] = map[nx][ny];
x = nx;
y = ny;
}
else k++;
}
map[machine[1].x][machine[1].y+1] = 0;
map[machine[1].x][machine[1].y] = -1;
}공기청정기를 통해 회전시키는 함수이다.
위아래가 비슷한 구조이기 때문에 하나만 설명하겠다.
먼저 dx1 []와 dy1 []은 시계방향으로 돌도록 설계했다.
그 이유는 반시계로 돌아야 하기 때문에
배열 상으로 보면 현재 위치에 반시계에 있는 값이 위치해야 하기 때문이다.
k는 방향을 나타낸다.
그래서 while(k < 4)는 360도까지만 돌리는 것이다.
종료 시점은 다시 원래의 공기 청정기의 위치로 돌아올 때 끝낸다.
이때 이 값을 호출한 위치는 0을 반환받는다.
왜냐하면 공기청정기에서 꺼낸 값이기 때문에 무조건 0이 나와야 하기 때문이다.
그 밑부터는 간단하다.
범위를 벗어나기 전까지는 설정해 둔 k방향인 한 방향으로 쭉 가다가,
범위를 벗어나면 k++로 방향을 바뀐 뒤 다시 그쪽으로 쭉 간다.
밑에 있는 시계로 돌리는 과정도 똑같기 때문에 생략하겠다.
이제 아래에 전체 코드를 올리고 마무리하겠다.
#include <iostream>
#include <vector>
using namespace std;
// x,y 좌표를 나타내는 구조체
struct Point{
int x;
int y;
};
int R,C; // 행,렬
int map[51][51];
vector<Point> dust; // 미세먼지 위치 배열
Point machine[2]; // 공기 정청기 위치 배열
void bfs(){
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int cmap[51][51] = {0,}; // 값을 담을 배열
// 미세먼지의 개수만큼 반복
for(int i = 0; i < dust.size(); i++){
int x = dust[i].x;
int y = dust[i].y;
int val = map[x][y];
int count = 0; // 몇개를 확산했는지 세기
for(int j = 0; j < 4; j++){
int nx = x + dx[j];
int ny = y + dy[j];
// 공기 청정기와의 충돌 체크와 범위 체크
if(nx > R || nx < 1 || ny > C || ny < 1
|| map[nx][ny] == -1) continue;
cmap[nx][ny] += val/5; // 값 계산
count++;
}
val = val - (val/5) * count; // 값 계산
cmap[x][y] += val;
}
// 배열에 담아뒀던 값을 map에 넣음(동기화)
for(int i = 1; i <= R; i++){
for(int j = 1; j <= C; j++)
if(cmap[i][j] > 0) map[i][j] = cmap[i][j];
}
}
void operating(){
// 위쪽 방향(반시계 방향이니까 시계 방향)
int dx1[] = {-1,0,1,0};
int dy1[] = {0,1,0,-1};
int k = 0; // 방향
// 위쪽 공기 청정기
int x = machine[0].x;
int y = machine[0].y;
while(k < 4){
int nx = x + dx1[k];
int ny = y + dy1[k];
if(nx == machine[0].x && ny == machine[0].y){
/*
돌고 돌아서 다시 공기 청정기로 오면 종료
이때 이 값을 가져오려는 위치는 0을 가져야함
공기 청정기를 지나면 먼지가 정화되기 때문
*/
map[x][y] = 0;
break;
}
// 범위 체크 -> 최대범위 = 공기청정기가 있는 곳
if(1 <= nx && nx <= machine[0].x
&& 1 <= ny && ny <= C){
map[x][y] = map[nx][ny];
x = nx;
y = ny;
}
else k++; // 범위를 벗어나면 방향 바꿈
}
map[machine[0].x][machine[0].y+1] = 0; // 혹시 몰라 한번 더 해줌
map[machine[0].x][machine[0].y] = -1; // 공기 청정기 위치에 -1을 넣어줌
// 아래족 방향(시계방향이니까 반시계 방향)
int dx2[] = {1,0,-1,0};
int dy2[] = {0,1,0,-1};
k = 0;
x = machine[1].x;
y = machine[1].y;
while(k < 4){
int nx = x + dx2[k];
int ny = y + dy2[k];
if(nx == machine[1].x && ny == machine[1].y){
map[x][y] = 0;
break;
}
if(machine[1].x <= nx && nx <= R
&& 1 <= ny && ny <= C){
map[x][y] = map[nx][ny];
x = nx;
y = ny;
}
else k++;
}
map[machine[1].x][machine[1].y+1] = 0;
map[machine[1].x][machine[1].y] = -1;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T;
cin >> R >> C >> T;
int layer = 0;
for(int i = 1; i <= R; i++){
for(int j = 1; j <= C; j++){
cin >> map[i][j];
if(map[i][j] == -1){
machine[layer] = {i,j};
layer++;
}
}
}
while(T--){
for(int i = 1; i <= R; i++)
for(int j = 1; j <= C; j++){
if(map[i][j] > 0) dust.push_back({i,j});
}
bfs();
operating();
dust.clear();
}
int ans = 0;
for(int i = 1; i <= R; i++){
for(int j = 1; j <= C; j++){
if(map[i][j] != -1) ans += map[i][j];
}
}
cout << ans;
}시행착오
문제를 푸는 아이디어 자체는 익숙했고
구현 자체는 어렵지 않았던 문제.
오래 걸렸던 것은 동시에 확산된다는 포인트를 놓쳐서
또 다른 배열을 만들어 담아준다는 생각을 못했다.
이전에 배열 돌리기와 BFS를 그래도
야무지게 해 놔서 도움이 됐던 것 같다.