[17144]미세먼지 안녕! - c++

문제 설명

https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

아이디어

1. 미세먼지를 확산시킨다

2. 공기청정기가 돌아간다

3. T번만큼 반복한다

 

일단 공기청정기를 반시계, 시계 방향으로 돌리는 법을 생각해야 했다.

 

공기청정기 돌리기

공기청정기의 머리 쪽은 반시계 방향, 몸통 쪽은 시계방향이다. 이렇게 둘로 나눠서 구현했다.

 

벽을 만날 때까지 반복해야 하니 방향이 필요하다 어느 방향으로 벽을 만날 때까지 나아갈 것인지

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

북 -> 동 -> 남 -> 서 순으로 정했다.

 

그럼 이제 어떻게 옮겨 줘야 할까?

나는 처음에 공기청정기가 가는 방향 대로 바꿔 주려고 하였다. 예를 들면 아래 그림을 보자

이렇게 하려면 다음값을 저장하고 전값을 다음 값에 넣어준 다음 전값을 저장하는 변수에 아까 넣어준 값을 넣고 이러쿵저러쿵... 해서 반복한다

너무 복잡할고 변수가 잠깐 사용할 변수가 많이 생길 것 같아 이 아이디어는 버렸다.

 

두 번째 아이디어는

반대로 가는 것이다. 이렇게 말하면 어려울 테니 그림을 보자

이렇게 끝나는 시점부터 시작하면 값을 저장할 변수를 따로 만들지 않아도 덮어 씌우면 되기 때문에 간편할 거라 생각하였다.

 

이제 구현을 해보면

↓반시계 방향으로 도는 로직이다.

int x = robot[0] == 1? robot[0] : robot[0] - 1, y = robot[0] == 1? 2: 1;
    for(int dir = 0; dir < 4; ++dir){
      int nx = x, ny = y;
      while(!OOB(x + dx[dir], y + dy[dir], robot[0], 1)){
        nx += dx[dir]; ny += dy[dir];
        board[x][y] = board[nx][ny];
        if(board[nx][ny] == -1)board[x][y]=0;
        x = nx; y = ny;
      }
    }

북 -> 동 -> 남 -> 서 순으로 순회한다.

 

↓시계방향

x = robot[1] == R ? robot[1] : robot[1] + 1, y = robot[1] == R ? 2 : 1;
    for(int dir = 6; dir > 2; --dir){
      int nx = x, ny = y;
      while(!OOB(x + dx[dir%4], y + dy[dir%4], R, robot[1])){
        nx += dx[dir%4]; ny += dy[dir%4];
        board[x][y] = board[nx][ny];
        if(board[nx][ny] == -1)board[x][y]=0;
        x = nx; y = ny;
      }
    }

남 -> 동 -> 북 -> 서 순으로 순회 한다 (dir을 어떻게 했는지 주의 깊게 보자!)

 

 

int x = robot[0] == 1? robot[0] : robot[0] - 1, y = robot[0] == 1? 2: 1; // 반시계 방향 코드에서..
x = robot[1] == R ? robot[1] : robot[1] + 1, y = robot[1] == R ? 2 : 1; //시계 방향 코드에서...

robot 배열이 궁금할 수도 있다, 이건 로봇의 머리, 몸통의 행값을 저장한 변수이다.

바로 위의 로직이 왜 필요한 걸까? 왜 삼항연산자로 표현했을 까? 그림을 보자

로봇의 머리가 위에 붙어 있다면

만약 머리가 위에 붙어 있지 않고 떨어져 있다면

왜 이렇게 해주었는지 알겠는가?

공기청정기는 -1로 표현하는데 공기청정기가 돌아가며 값을 덮어 씌우면서 공기청정기까지 덮어 씌워질 수 있기 때문에 한 칸 위에서부터 시작하는 것이다.

지금 이해 못 해도 상관없다 로직을 차근차근 보면서 이랬구나 하고 알면 된다!

 

미세먼지 확산

이제 미세먼지를 확산 시켜 보자 문제를 보면 

이런 식으로 확산 됨을 알 수 있고 미세먼지끼리 겹치면 각자 양의 합을 구하면 된다.

그렇기 때문에 현재 자기 자신의 양이 얼마 인지 입력받을 때 알려줘야 한다.

이건 바로 코드를 보자

먼지의 위치를 저장할 큐를 만들어 줬다.

while(!dust.empty()){
      int x, y, amount;
      tie(x, y, amount) = dust.front(); dust.pop();
      int nxtAmount = amount / 5;
      int cnt = 0;
      for(int dir = 0; dir < 4; ++dir){
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if(OOB(nx, ny, R, 1)) continue;
        if(board[nx][ny] == -1) continue;
        cnt++;
        board[nx][ny] += nxtAmount;
      }
      board[x][y] -= amount;
      board[x][y] += amount -(amount/5) * cnt;
    }

 

어려운 부분이 없을 것이라 생각된다.

---

CODE

#include <bits/stdc++.h>

#define X first
#define Y second

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int R, C, k;
int board[52][52];

int robot[2];
queue<tuple<int, int, int>> dust;

//방향
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

bool OOB(int x, int y, int a, int b){
  return x < b || x > a || y < 1 || y > C;
}

int main(){
  init();
  cin >> R >> C >> k;
  int cur = 0;
  
  //입력 받기
  for(int i =1; i <= R; ++i){
    for(int j =1; j <= C; ++j){
      cin >> board[i][j];
      
      // 먼지라면 먼지큐에 저장
      if(board[i][j] > 0)
        dust.push({i, j, board[i][j]});
        
      // 공기청정기라면 robot에 저장
      else if(board[i][j] == -1)
        robot[cur++] = i;
    }
  }

//반복
  for(int u = 0; u < k; ++u){
  
  	//먼지 확산
    while(!dust.empty()){
      int x, y, amount;
      tie(x, y, amount) = dust.front(); dust.pop();
      int nxtAmount = amount / 5;
      int cnt = 0;
      for(int dir = 0; dir < 4; ++dir){
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if(OOB(nx, ny, R, 1)) continue;
        if(board[nx][ny] == -1) continue;
        cnt++;
        board[nx][ny] += nxtAmount;
      }
      board[x][y] -= amount;
      board[x][y] += amount -(amount/5) * cnt;
    }
    
    //반시계 방향으로
    int x = robot[0] == 1? robot[0] : robot[0] - 1, y = robot[0] == 1? 2: 1;
    for(int dir = 0; dir < 4; ++dir){
      int nx = x, ny = y;
      while(!OOB(x + dx[dir], y + dy[dir], robot[0], 1)){
        nx += dx[dir]; ny += dy[dir];
        board[x][y] = board[nx][ny];
        if(board[nx][ny] == -1)board[x][y]=0;
        x = nx; y = ny;
      }
    }
    
    //시계 방향으로
    x = robot[1] == R ? robot[1] : robot[1] + 1, y = robot[1] == R ? 2 : 1;
    for(int dir = 6; dir > 2; --dir){
      int nx = x, ny = y;
      while(!OOB(x + dx[dir%4], y + dy[dir%4], R, robot[1])){
        nx += dx[dir%4]; ny += dy[dir%4];
        board[x][y] = board[nx][ny];
        if(board[nx][ny] == -1)board[x][y]=0;
        x = nx; y = ny;
      }
    }
    
    //다시 방에 있는 먼지를 조사하여 먼지 큐에 넣는다! 먼지의 양까지 모두 (tuple)
    for(int i = 1; i <= R; ++i)
      for(int j =1; j <= C; ++j)
        if(board[i][j] > 0)
          dust.push({i, j, board[i][j]});
  }

  // 마지막 방안의 먼지를 모두 더해준다. ans가 2부터 시작하는 이유는 공기 청정기 -1개 있기 때문이다.
  int ans = 2;
  for(int i =1; i <= R; ++i)
    for(int j = 1; j <= C; ++j)
      ans += board[i][j];
  cout << ans;
  return 0;
}

---

문제를 풀며

사실 비효율 적인 부분이 많은 것 같다. 이렇게 문제를 맞췄다고 끝내는 것이 아니라 다른 사람은 어떻게 풀었나 조금 더 공부해봐야겠다. 나에게 필요한 건 얻어간다는 마인드로 공부하자.