[C++] 23289 : 온풍기 안녕!

백준에서 가장 인기 있는 문제집은 삼성 SW 역량 테스트 A형 문제집이다.
https://www.acmicpc.net/workbook/view/1152

이 중에서 어려운 문제에 속하는 "온풍기 안녕!"을 풀어보자.

알고리즘 분류

• 너비 우선 탐색 (BFS)

 

문제설명

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

while loop을 돌며 다음 단계를 거친다.

1. 바람 나옴
2. 온도 조절
3. 가장자리 온도 1 감소
4. 초콜릿 먹기
5. 온도 검사

이 각각의 부분을 함수로 구현하면 된다.

 

문제접근

1. 바람 나오는거 구현하기

바람은 세 방향으로 퍼지는데, 그림으로 표현하면 다음과 같다. 우선 동쪽으로 바람을 쏘는 온풍기를 나타내면 다음과 같다. 문제와 다르게, y를 아래방향, x를 오른쪽 방향으로수정했다.

우선 (y,x)에서 오른쪽으로 방향을 쏘면, (y, x+1) 에 5에 해당하는 바람이 도달하고 (여기에 도달하는 것은 문제에서 보장되어있다.) 이후 3방향으로 북 -> 동, 동, 남->동 방향으로 "벽이 없다면" 도달할 수 있으며, 이때 바람은 4이다. 이런 식으로 바람이 0이 되면 종료한다.

그럼 나머지 3방향을 그림으로 나타내면 다음과 같다.

이 방향을 나타내면 코드로 나타내자. 헷갈리니깐 enum을 써서 나타내보면,

// 동 서 북 남
typedef enum _DIRECTION
{
  EAST = 0,
  WEST,
  NORTH,
  SOUTH
} DIRECTION;

// EAST 0, WEST 1, NORTH 2, SOUTH 3
// 온풍기 방향 dir에 대해 바람이 퍼지는 방향들.
// 예를 들어 east 일 경우 north->east 로 북동쪽 좌표로 간다.
vector<vector<int>> dirs[4] = {
    {{NORTH, EAST}, {EAST}, {SOUTH, EAST}},
    {{SOUTH, WEST}, {WEST}, {NORTH, WEST}},
    {{WEST, NORTH}, {NORTH}, {EAST, NORTH}},
    {{EAST, SOUTH}, {SOUTH}, {WEST, SOUTH}}
};

이렇게 하면 동->서->북->남 direction에 대해 갈 수 있는 루트가 3가지가 있고, 각각의 루트로 사선, 직선, 사선 방향으로 이동할 수 있을지를 결정하면 된다. 

예를 들어 dirs[0][0] = {NORTH, EAST} 이다. 이는 현재 좌표 y,x 에서 북쪽으로 이동했다가 동쪽으로 이동해서 (y-1, x+1)에 도달할 수 있냐? 를 나타낸다.

그러면 이와 연계해서 "벽" 정보도 전처리가 필요하다. 문제에서 제시하는 벽 정보는 그대로 사용하기 매우 어렵게 되어 있다.

이를 본인이 설계한 알고리즘에 "맞게" 전처리하는것이 중요하다! 나는 (y,x) 에서 (dir) 방향으로 나아가는 과정에서 벽이 있는지를 알고 싶기 때문에 다음과 같이 전처리해주면 된다.

(y,x,0)이 들어오면 위에 좌표 사이에 벽이 생긴 것이다. 이는 아래에서 위로 갈 수 없다는 것이며, 또한 위에서 아래로 갈 수 없다는 것이기에 벽 좌표를 두 개 만들어야 한다. (y,x,1)인 경우도 마찬가지다. enum을 쓰면 헷갈리지 않게 전처리 가능하다.

  cin >> w;
  for (int i = 0; i < w; i++) {
    int y, x, t;
    cin >> y >> x >> t;
    y--; // 0부터 시작하도록 전처리
    x--;
    // (y,x 에서 dir 방향에 벽이 있는가?)
    // 동 서 북 남
    if (t == 0) {
      Walls[y - 1][x][SOUTH] = 1; 
      Walls[y][x][NORTH] = 1;
    }
    if (t == 1) {
      Walls[y][x][EAST] = 1;
      Walls[y][x + 1][WEST] = 1;
    }
  }

이제 이를 이용해서 bfs 함수를 구현할 때, 해당 경로로 갈 수 있는지를 파악해야 한다. 따라서 bfs()안에 함수를 하나 더 만들어서 갈 수 있다면 visited에 표시해주기로 하자. queue는 전역 변수로 설정해준다.

void bfs(Machine m)
{
  memset(visited, 0, sizeof(visited));

  int y = m.y + dy[m.dir];
  int x = m.x + dx[m.dir];
  int dir = m.dir;
  q.push({y, x});
  visited[y][x] = 5;
  
  while (q.size())
  {
    pii here = q.front(); q.pop();
    int y = here.first;
    int x = here.second;
    if (visited[y][x] == 1) continue;
    for (int i = 0; i < 3; i++)
    {
      next_move(y, x, dirs[dir][i], visited[y][x]);
    }
  }
}

bool is_out(int y, int x)
{
  return (y < 0 || y >= r || x < 0 || x >= c);
}

void next_move(int y, int x, vector<int> v, int power)
{
  for (int dir : v)
  {
    //cout << y << " : " << x << " : " << dir << endl;
    int ny = y + dy[dir];
    int nx = x + dx[dir];
    if (is_out(ny, nx) || visited[ny][nx]) return;
    if (Walls[y][x][dir]) return;
    //cout << " 성공 " << endl;
    y = ny;
    x = nx;
  }
  //cout << y << " : " << x << " 에 " << power -1 << " 쓰다. " << endl;
  visited[y][x] = power - 1;
  q.push({y, x});
  return;
}

2. 온도 조절

온도 조절을 위해서는 temp 배열을 만들어서 온도 조절 량을 표시해 준 후, 한꺼번에 더해줘야 한다. 간단하게 표현 가능하다.

3. 가장자리 빼기

이것도 간단하게 끝 좌표면 1씩 빼주면 된다.

4. 초콜릿 먹기

1 더해주고, 100 보다 커지면 break한다.

5. 온도 감지하기

온도 감지해주고 다 K 이상이면 true 리턴한다.

그냥 1번 함수만 잘 구현하는게 문제의 핵심이다.

전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}

// 동 서 북 남
typedef enum _DIRECTION
{
  EAST = 0,
  WEST,
  NORTH,
  SOUTH
} DIRECTION;

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

// dir할 때 -1 해서 저장할 것
typedef struct _Machine
{
  int y, x, dir;
} Machine; 

vector<Machine> machine;

int r, c, k; // y, x, test k
int land_temp[24][24]; // 현재 land의 temp
int temp_will_add[24][24]; // temp 더하는 용도
int visited[24][24]; // 각각의 machine마다 살포하는 용도
int Walls[24][24][4]; // y, x 에서 dir 방향으로 벽 있음?

// EAST 0, WEST 1, NORTH 2, SOUTH 3
// 온풍기 방향 dir에 대해 바람이 퍼지는 방향들.
// 예를 들어 east 일 경우 north->east 로 북동쪽 좌표로 간다.
vector<vector<int>> dirs[4] = {
    {{NORTH, EAST}, {EAST}, {SOUTH, EAST}},
    {{SOUTH, WEST}, {WEST}, {NORTH, WEST}},
    {{WEST, NORTH}, {NORTH}, {EAST, NORTH}},
    {{EAST, SOUTH}, {SOUTH}, {WEST, SOUTH}}
};

vector<pii> to_search;
int w;
int choco;
queue<pii> q;

void init()
{
  cin >> r >> c >> k;
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      int num;
      cin >> num;
      if (num >= 1 && num <= 4) {
        machine.push_back({i, j, num - 1});
      } else if (num == 5) {
        to_search.push_back({i, j});
      }
    }
  }

  cin >> w;
  for (int i = 0; i < w; i++) {
    int y, x, t;
    cin >> y >> x >> t;
    y--; // 0부터 시작하도록 전처리
    x--;
    // (y,x 에서 dir 방향에 벽이 있는가?)
    // 동 서 북 남
    if (t == 0) {
      Walls[y - 1][x][SOUTH] = 1; 
      Walls[y][x][NORTH] = 1;
    }
    if (t == 1) {
      Walls[y][x][EAST] = 1;
      Walls[y][x + 1][WEST] = 1;
    }
  }
}

bool is_out(int y, int x)
{
  return (y < 0 || y >= r || x < 0 || x >= c);
}

void next_move(int y, int x, vector<int> v, int power)
{
  for (int dir : v)
  {
    //cout << y << " : " << x << " : " << dir << endl;
    int ny = y + dy[dir];
    int nx = x + dx[dir];
    if (is_out(ny, nx) || visited[ny][nx]) return;
    if (Walls[y][x][dir]) return;
    //cout << " 성공 " << endl;
    y = ny;
    x = nx;
  }
  //cout << y << " : " << x << " 에 " << power -1 << " 쓰다. " << endl;
  visited[y][x] = power - 1;
  q.push({y, x});
  return;
}

void bfs(Machine m)
{
  memset(visited, 0, sizeof(visited));

  int y = m.y + dy[m.dir];
  int x = m.x + dx[m.dir];
  int dir = m.dir;
  q.push({y, x});
  visited[y][x] = 5;
  
  while (q.size())
  {
    pii here = q.front(); q.pop();
    int y = here.first;
    int x = here.second;
    if (visited[y][x] == 1) continue;
    for (int i = 0; i < 3; i++)
    {
      next_move(y, x, dirs[dir][i], visited[y][x]);
    }
  }
}

void add_land()
{
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      land_temp[i][j] += visited[i][j];
    }
  }
}

void temp_control()
{
  memset(temp_will_add, 0, sizeof(temp_will_add));
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      for (int dir = 0; dir < 4; dir++)
      {
        if (Walls[i][j][dir]) continue;
        int ny = i + dy[dir];
        int nx = j + dx[dir];
        if (is_out(ny, nx)) continue;
        if (land_temp[i][j] > land_temp[ny][nx])
        {
          temp_will_add[i][j] -= (land_temp[i][j] - land_temp[ny][nx]) / 4;
          temp_will_add[ny][nx] += (land_temp[i][j] - land_temp[ny][nx]) / 4;
        }
      }
    }
  }

  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      land_temp[i][j] += temp_will_add[i][j];
    }
  }
}

void reduce_around()
{
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      if (land_temp[i][j] == 0) continue;
      if (!i || !j || i == r - 1 || j == c - 1) land_temp[i][j]--;
    }
  }
}

bool test_temp()
{
  for (auto a : to_search)
  {
    if (land_temp[a.first][a.second] < k)
    {
      return false;
    }
  }
  return true;
}

void printV()
{
  cout << "bfs gogo" << endl;
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      cout << visited[i][j] << ' ';
    }
    cout << endl;
  }
}

void printL() {
  cout << "temp" << endl;
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      cout << land_temp[i][j] << ' ';
    }
    cout << endl;
  }
}

int main()
{
  init();

  while(1)
  {
    for (Machine m : machine)
    {
      bfs(m);
      //printV();
      add_land();
    }
    temp_control();
    reduce_around();
    //printL();
    choco++;
    if (choco > 100) break;
    if (test_temp()) break;
  }

  cout << choco << endl;
  return 0;
}

디버깅 코드도 살려 놓았으니 print하면서 파악하면 된다.

구현 양은 많긴 한데, 이 문제의 핵심은 Raw Data를 편리하게 전처리하는 Idea라고 생각한다. 전처리 안하고 주어진 대로로만 구현한다면 구현이 복잡한 건 둘째치고, 실수 확률이 기하급수적으로 올라가므로 이를 염두하자.