문제 소개
문제 링크 : https://www.acmicpc.net/problem/23289
삼성 SW 역량 테스트 기출문제집에 있던 구현 문제다.
문제 분석
문제를 읽어보면 설명이 상당히 긴데, 이 중에서 구현의 핵심이 되는 부분들을 정리하면 다음과 같다.
온풍기 동작
1. 온풍기는 지정된 방향으로 초기 온도가 5인 바람을 1회 불어 방안의 온도를 올리는데,
바람은 진행방향과 그 양측 대각선으로 진행하며, 1칸 진행시 마다 1도씩 온도가 떨어진다.
2. 바람이 불어가는 방향에 벽이 있으면 바람은 해당 방향으로 진행하지 못한다.온도 조절
1. 온도 조절은 모든 온풍기가 바람을 분 후 모든 칸에서 동시에 진행된다.
2. 온도는 높은 곳에서 낮은 곳으로 ⌊(두 칸의 온도차)/4⌋ 만큼 조절된다.
높은 곳의 온도는 해당 온도만큼 낮아지고, 낮은 곳의 온도는 해당 온도만큼 높아진다.이렇게 적고보니 별게 아닌 것 같다.
이제 차근차근 구현해 보자.
구현
이 문제에 있어 가장 중요한 벽, 온풍기 동작, 온도 조절에 대해 세부적으로 구현한 후, 전체 코드를 작성하였다.
벽
벽이 있으면 바람이 통과하지 못하고, 온도 교환도 일어나지 않는다.
그렇기에 이 벽을 어떻게 구현할지 생각해야 하는데, 그냥 간단하게 생각하기로 했다.
4차원 배열을 만들어서 (현재 행 위치, 현재 열 위치)와 (다음 행 위치, 다음 열 위치) 사이에 벽의 존재 유무를 확인할 수 있도록 구현하였다.
vector<vector<vector<vector<bool>>>> wall_grid;
for(int i = 0; i < K; ++i)
{
int row, col, t;
cin>>row>>col>>t;
row--; col--;
Point next = {row - !t, col + t};
if(next.chkRange())
{
//(row, col) <-> (next.row, next.col)
wall_grid[row][col][next.row][next.col] = 1;
wall_grid[next.row][next.col][row][col] = 1;
}
}온풍기 동작
우선, 모든 온풍기가 각각 독립적으로 작동하기에 각각의 온풍기들이 방 안의 온도에 미치는 영향을 별도로 시뮬레이션 한 뒤, 모든 결과를 개별적으로 반영하는 것이 좋다고 생각했다.
여기에 더해, 온풍기에서 나온 각각의 바람이 독립적으로 불어나가기에 바람이 불어나가는 과정을 BFS를 사용해 구현해야할 것인데, 같은 칸에 두번 이상 바람이 불면 안되기에 이를 감지해줄 배열이 필요한데, 각각의 온풍기에 대해 시뮬레이션을 함으로써 방의 온도 상태를 나타내는 2차원 배열 하나로 모두 해결이 가능해진다.
vector<vector<int>> blow(circulator &cir,
const vector<vector<vector<vector<bool>>>> &wall_grid)
{
vector<vector<int>> result_grid(R, vector<int>(C, 0));
queue<pair<int, Point>> next_q;
Point cur = cir.nextPoint();
if(cur.chkRange() &&
!wall_grid[cir.point.row][cir.point.col][cur.row][cur.col])
next_q.push(make_pair(5,cur));
while(!next_q.empty())
{
cur = next_q.front().second;
int cnt = next_q.front().first;
next_q.pop();
if(cur.chkRange() && result_grid[cur.row][cur.col] == 0)
{
Point next = {cur.row + Dir[cir.dir_ind][0],
cur.col + Dir[cir.dir_ind][1]};
int vertical_dir = (cir.dir_ind >= 2 ? 0 : 2);
result_grid[cur.row][cur.col] = cnt;
if(cnt > 1)
{
if(next.chkRange() && !wall_grid[cur.row][cur.col][next.row][next.col])
next_q.push(make_pair(cnt - 1, next));
for(int i = 0; i < 2; ++i)
{
Point ver_next = {cur.row + Dir[vertical_dir + i][0],
cur.col + Dir[vertical_dir + i][1]};
Point t_next = {next.row + Dir[vertical_dir + i][0],
next.col + Dir[vertical_dir + i][1]};
if(t_next.chkRange()
&& ver_next.chkRange()
&& !wall_grid[cur.row][cur.col][ver_next.row][ver_next.col]
&& !wall_grid[ver_next.row][ver_next.col][t_next.row][t_next.col])
next_q.push(make_pair(cnt-1,t_next));
}
}
}
}
return result_grid;
}온도 조절
온도 조절은 인접한 두 칸 사이에서 한번만 일어나야한다.
이를 위해 어떠한 칸의 좌표 (row, col)에 대해 (row+1,col)과 (row,col+1)의 온도 조절만 수행하여 중복되는 온도 조절이 없도록 해준다.
그리고 온도 조절은 모든 칸에서 동시에 일어나야하기 때문에, 각 칸의 온도 참조는 온도 조절이 되기 전의 배열을 참조하고, 별도의 계산용 배열에 계산 결과를 따로 저장한 후 계산용 배열의 결과값을 본래의 배열에 반영하도록 해준다.
vector<vector<int>> adjust_temp(const vector<vector<int>> &temp_grid,
const vector<vector<vector<vector<bool>>>> &wall_grid)
{
vector<vector<int>> oper_grid(R, vector<int>(C, 0));
for(int row = 0; row < R; ++row)
{
for(int col = 0; col < C; ++col)
{
Point next;
for(int dir_ind = 0; dir_ind < 4; dir_ind += 3)
{
next = {row + Dir[dir_ind][0], col + Dir[dir_ind][1]};
if(next.chkRange()
&& !wall_grid[row][col][next.row][next.col])
{
int cur_temp = temp_grid[row][col],
next_temp = temp_grid[next.row][next.col];
oper_grid[row][col] += floor((next_temp - cur_temp) / 4);
oper_grid[next.row][next.col] += floor((cur_temp - next_temp) / 4);
}
}
}
}
return oper_grid;
}전체 코드
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int R, C, K;
const int Dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
struct Point {
int row;
int col;
bool chkRange(void) {
return row >= 0 && row < R && col >= 0 && col < C;
}
};
struct circulator {
Point point;
int dir_ind;
int nextRow(void) {return point.row + Dir[dir_ind][0];}
int nextCol(void) {return point.col + Dir[dir_ind][1];}
Point nextPoint(void) {return {point.row + Dir[dir_ind][0], point.col + Dir[dir_ind][1]};}
};
vector<vector<int>> blow(circulator &cir, const vector<vector<vector<vector<bool>>>> &wall_grid)
{
vector<vector<int>> result_grid(R, vector<int>(C, 0));
queue<pair<int, Point>> next_q;
Point cur = cir.nextPoint();
if(cur.chkRange() && !wall_grid[cir.point.row][cir.point.col][cur.row][cur.col])
next_q.push(make_pair(5,cur));
while(!next_q.empty())
{
cur = next_q.front().second;
int cnt = next_q.front().first;
next_q.pop();
if(cur.chkRange() && result_grid[cur.row][cur.col] == 0)
{
Point next = {cur.row + Dir[cir.dir_ind][0], cur.col + Dir[cir.dir_ind][1]};
int vertical_dir = (cir.dir_ind >= 2 ? 0 : 2);
result_grid[cur.row][cur.col] = cnt;
if(cnt > 1)
{
if(next.chkRange() && !wall_grid[cur.row][cur.col][next.row][next.col])
next_q.push(make_pair(cnt - 1, next));
for(int i = 0; i < 2; ++i)
{
Point ver_next = {cur.row + Dir[vertical_dir + i][0], cur.col + Dir[vertical_dir + i][1]};
Point t_next = {next.row + Dir[vertical_dir + i][0],next.col + Dir[vertical_dir + i][1]};
if(t_next.chkRange() && ver_next.chkRange() && !wall_grid[cur.row][cur.col][ver_next.row][ver_next.col] &&
!wall_grid[ver_next.row][ver_next.col][t_next.row][t_next.col])
next_q.push(make_pair(cnt-1,t_next));
}
}
}
}
return result_grid;
}
vector<vector<int>> adjust_temp(const vector<vector<int>> &temp_grid, const vector<vector<vector<vector<bool>>>> &wall_grid)
{
vector<vector<int>> oper_grid(R, vector<int>(C, 0));
for(int row = 0; row < R; ++row)
{
for(int col = 0; col < C; ++col)
{
Point next;
for(int dir_ind = 0; dir_ind < 4; dir_ind += 3)
{
next = {row + Dir[dir_ind][0], col + Dir[dir_ind][1]};
if(next.chkRange() && !wall_grid[row][col][next.row][next.col])
{
int cur_temp = temp_grid[row][col], next_temp = temp_grid[next.row][next.col];
oper_grid[row][col] += floor((next_temp - cur_temp) / 4);
oper_grid[next.row][next.col] += floor((cur_temp - next_temp) / 4);
}
}
}
}
return oper_grid;
}
void reflection_temp (vector<vector<int>> &temp_grid, const vector<vector<int>> &calc_grid)
{
for(int row = 0; row < R; ++row)
for(int col = 0; col < C; ++col)
temp_grid[row][col] += calc_grid[row][col];
}
void decrese_edge_temp(vector<vector<int>> &temp_grid)
{
for(int row = 0; row < R; ++row)
{
temp_grid[row][0] = (temp_grid[row][0] == 0 ? 0 : temp_grid[row][0] - 1);
temp_grid[row][C-1] = (temp_grid[row][C-1] == 0 ? 0 : temp_grid[row][C-1] - 1);
}
for(int col = 1; col < C-1; ++col)
{
temp_grid[0][col] = (temp_grid[0][col] == 0 ? 0 : temp_grid[0][col] - 1);
temp_grid[R-1][col] = (temp_grid[R-1][col] == 0 ? 0 : temp_grid[R-1][col] - 1);
}
}
bool check_minimum_temp(const vector<vector<int>> &temp_grid, const vector<Point> &toCheck_v)
{
for(int i=0; i < toCheck_v.size(); ++i)
if(temp_grid[toCheck_v[i].row][toCheck_v[i].col] < K)
return 0;
return 1;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int chocolate_cnt = 0;
vector<circulator> cir_v;
vector<Point> toCheck_v;
vector<vector<int>> temp_grid;
vector<vector<vector<vector<bool>>>> wall_grid;
cin>>R>>C>>K;
temp_grid.assign(R, vector<int>(C, 0));
wall_grid.assign(R, vector<vector<vector<bool>>>(C, vector<vector<bool>>(R, vector<bool>(C,0))));
for(int row = 0; row < R; ++row)
for(int col = 0; col < C; ++col)
{
int temp;
cin>>temp;
if(temp == 5)
toCheck_v.push_back({row,col});
else if(temp != 0)
cir_v.push_back({{row,col},temp-1});
}
int K;
cin>>K;
for(int i = 0; i < K; ++i)
{
int row, col, t;
cin>>row>>col>>t;
row--; col--;
Point next = {row - !t, col + t};
if(next.chkRange())
{
wall_grid[row][col][next.row][next.col] = 1;
wall_grid[next.row][next.col][row][col] = 1;
}
}
bool flag = 1;
while(flag && chocolate_cnt <= 100)
{
for(int i = 0; i < cir_v.size(); ++i)
{
vector<vector<int>> calc_grid = blow(cir_v[i], wall_grid);
reflection_temp(temp_grid, calc_grid);
}
vector<vector<int>> oper_grid = adjust_temp(temp_grid, wall_grid);
reflection_temp(temp_grid, oper_grid);
decrese_edge_temp(temp_grid);
chocolate_cnt++;
flag = !check_minimum_temp(temp_grid, toCheck_v);
}
cout<<chocolate_cnt;
return 0;
}
제출결과
총평 및 여담
이런 구현문제에 대한 경험이 부족하다 보니, 처음 문제에 나열된 조건들을 보면 막막함이 먼저 들이닥치는 경우가 많은데, 이 문제도 그랬다.
그래도 이제 어느정도 해결책을 찾아서 우선 조건들을 나열하고, 주요한 요소들을 차근차근 구현해 나아가다 보니 문제를 풀긴 했다.
다만, 코드가 길어지니 가독성이 상당히 처참하다. 처참한 가독성 때문에 조건문을 제대로 확인하지 못해 OutOfBound나 Double Free or Corruption 같은 오류도 마주하게 되었다. 최적화도 더 이상 진행하기 어려웠던건 덤. 다른 사람들의 코드 읽기를 습관화 하면서 가독성 있는 코드에 대해 더 고심해 보기로 했다.
재잘재잘