[백준] 17144 미세먼지 안녕!
업데이트:
삼성 기출 백준 17144 미세먼지 안녕! 풀이입니다.
삼성 기출 문제 치곤 조금 쉬운감이 없잖아 있는거 같다!! 물론 문제를 꼼꼼히 잘 읽고 잔실수를 안한다는 가정하에….
처음에 문제를 읽었을 때 들었던 의문은 미세먼지가 안사라진다는건가? 라는 의문이였지만 이것도 문제를 읽어보니 공기청정기가 밀어낸다는 의미였다. 추가로 그럼 1일경우는 어떻게 되는거지 라고 생각을 했더니 소수점 아래는 날라가기 때문에 미세먼지가 증발한다는 의미였다.
-> 문제 이해도가 너무 낮은 것 같다.. ㅠ 문제를 꼼꼼히 읽자
아무튼 문제를 이해한 뒤 조건대로 확산과 바람 이동 함수를 구현하였다. diffusion은 그냥 말그대로 확산만 시키면 된다는 생각에 굉장히 빨리 만들었다. -> 이게 화근이였다.
이후 공기청정기 바람을 이동시키는 함수를 구현한 뒤 예제 입력을 넣었는데 값이 이상하다! 그래서 확인해봤더니 확산에 문제가 있다는 것을 발견했다.
문제로 돌아와서 다시 읽어 보니 다음과 같은 문장을 내가 놓쳤다는 것을 알 수 있었다.
확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
아차 싶어서 확산 함수로 다시 돌아와서 임시 템프 배열을 만들어준 뒤 각 좌표 위치별로 += 되는 값들을 저장해뒀다. 그 뒤 map에 반영시켰다.
이러고 돌렸더니 또 값이 이상하다
그래서 다시 확인해봤더니 확산 시킨 뒤 tmp함수를 업데이트를 안한 것이다. 왜냐면 tmp는 확산된 map이랑 같은 값을 가지고 있어야 하기 때문이다. 그래서 입력 부분에서 저장시켰던 부분을 빼고 돌렸더니
그래도 큰 어려움을 준 문제는 아니였다!
코드는 (https://github.com/JooYoung1121/CodingTest_Algorithm) 여기에도 업로드 되있습니다!
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define MAX 51
typedef pair<int, int> p;
int R, C, T;
p Air[2]; // 공기청정기 위치
int map[MAX][MAX]; // 먼지 맵
int tmp[MAX][MAX];
int dx[4] = {-1,0,1,0}; // Up Right Down Left
int dy[4] = {0,1,0,-1};
void Copy_map() {
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
map[i][j] = tmp[i][j];
}
}
}
void Copy_tmp() { // 확산 시키고 tmp도 업데이트 해야 한다는 사실을 까먹음
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
tmp[i][j] = map[i][j];
}
}
}
void diffusion() { // 미세먼지 확산 -> 동시에 확산!!!!!!!!!!
int ttmp[MAX][MAX] = {0,};
for (int x = 1; x <= R; x++) {
for (int y = 1; y <= C; y++) {
if (map[x][y] == -1) continue;
if (map[x][y] != 0) {
int div_dust = map[x][y] / 5; // 확산될 먼지 양
int cnt = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx <= 0 || nx > R || ny <= 0 || ny > C)continue;
if ((nx == Air[0].first && ny == Air[0].second) || (nx == Air[1].first && ny == Air[1].second)) continue;
ttmp[nx][ny] += div_dust;
//map[nx][ny] += div_dust; // 동시에 확산이라는걸 ....못봤다
cnt++;
}
ttmp[x][y] -= (div_dust * cnt);
//map[x][y] -= (div_dust * cnt);
}
}
}
for (int x = 1; x <= R; x++) {
for (int y = 1; y <= C; y++) {
if (map[x][y] == -1)continue;
map[x][y] += ttmp[x][y];
}
}
}
void Move_wind(int x,int y,int air_num) {
int dir = 1; // Right
int cur_x = x;
int cur_y = y;
if (air_num == 0) {
while (1) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (ny > C) { // 벽에 부딪힐 경우
dir = 0;
nx = x + dx[dir];
ny = y + dy[dir];
}
else if (nx <= 0) {
dir = 3;
nx = x + dx[dir];
ny = y + dy[dir];
}
else if (ny <= 0) {
dir = 2;
nx = x + dx[dir];
ny = y + dy[dir];
}
if (nx == cur_x && ny == cur_y)break;
if (map[x][y] == -1)
tmp[nx][ny] = 0;
else
tmp[nx][ny] = map[x][y];
x = nx;
y = ny;
}
}
else {
while (1) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (ny > C) {
dir = 2;
nx = x + dx[dir];
ny = y + dy[dir];
}
else if (nx > R) {
dir = 3;
nx = x + dx[dir];
ny = y + dy[dir];
}
else if (ny <= 0) {
dir = 0;
nx = x + dx[dir];
ny = y + dy[dir];
}
if (nx == cur_x && ny == cur_y)break;
if (map[x][y] == -1)
tmp[nx][ny] = 0;
else
tmp[nx][ny] = map[x][y];
x = nx;
y = ny;
}
}
}
void Wind() { // 공기청정기 이동
for (int i = 0; i < 2; i++) {
Move_wind(Air[i].first, Air[i].second, i);
}
Copy_map();
}
int Sum() {
int result = 0;
for (int x = 1; x <= R; x++) {
for (int y = 1; y <= C; y++) {
if(map[x][y] != -1)
result += map[x][y];
}
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
cin >> R >> C >> T;
int idx = 0;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
cin >> map[i][j];
//tmp[i][j] = map[i][j]; 이 부분이 필요가 없었다 결국은
if (map[i][j] == -1)
Air[idx++] = { i,j };
}
}
while (T--) {
diffusion();
Copy_tmp();
Wind();
}
cout << Sum();
return 0;
}
오늘의 교훈
- 문제를 잘읽자
- 잔 실수는 그만하자
- 디버깅은 꼼꼼히
- 함수 활용을 잘하자
- 코드 리팩토링!
소스코드
이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이
댓글남기기