냉방 시스템 [2021-하반기 오전 2번 문제]
문제 링크
삼성 코딩테스트 기출 문제: 냉방 시스템 | 코드트리
주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.
문제 설명
n*n 격자에 0-5 사이의 숫자가 있음. 0은 빈 공간, 1은 사무실, 2-5까지는 좌-상-우-하 방향의 에어컨이 있음.
에어컨은 삼각형 모양으로 퍼지는데, 벽이 있다면 가로막힘.
순서는 다음과 같음.
- 에어컨에서 바람이 붐.
- 시원한 공기가 섞임 - 시원함이 높은 곳에서 낮은 곳으로
시원함의 차이 / 4만큼 전파됨. - 외벽의 칸들의 시원함이 1씩 감소함.
해결 방법
탈출조건 체크모든 사무실이 해당 온도보다 같거나 높다면, 루프 탈출.
for (int i = 0;i < office.size();i++) {
if (arr[office[i].first][office[i].second] < k) return false;
}
return true;
시원한 바람 공기 섞기 + 외벽 감소시원함이 높은 곳에서 낮은 곳으로 시원함의 차이 / 4 만큼 전파시키고, 외벽의 경우 1씩 감소.
void air_mix() {
memset(tmp, 0, sizeof(tmp));
int nx, ny;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
for (int k = 0;k < 4;k++) {
if (wall[i][j][k]) continue;
nx = i + dx[k], ny = j + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[i][j] > arr[nx][ny]) {
tmp[i][j] -= (arr[i][j] - arr[nx][ny]) / 4;
tmp[nx][ny] += (arr[i][j] - arr[nx][ny]) / 4;
}
}
tmp[i][j] += arr[i][j];
}
}
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
arr[i][j] = tmp[i][j];
if (i == 0 || j == 0 || i == n - 1 || j == n - 1) {
if(arr[i][j] > 0) arr[i][j]--;
}
}
}
}
에어컨에서 바람 불게 하기.처음에는 queue로 풀었는데 조금 까다로워서 재귀로 바꿨음.방향을 기준으로 위, 앞, 아래를 갈 수 있는지 체크를 해줌.get_dir라는 함수를 통해 상대위치를 사용해서 방향을 체크하고, 해당 방향을 기준으로 벽을 체크하였음.해당 부분에서 시간을 되게 많이 잡아먹음. 실전에서는 길게 생각하고, 천천히 코드를 짜야 될 듯.
int get_dir(int cx, int cy, int nx, int ny) {
if (cy - ny == 1) return 0;
else if (cx - nx == 1) return 1;
else if (cy - ny == -1) return 2;
else if (cx - nx == -1) return 3;
else {
cout << cx << " " << cy << " " << nx << " " << ny << "!\\n";
cout << "error!";
exit(0);
}
}
void breeze(int x, int y, int dir, int temp) {
arr[x][y] += temp;
if (temp == 1) return;
int nx, ny;
// 1. 바로 앞
nx = x + dx[dir], ny = y + dy[dir];
if ((nx >= 0 && ny >= 0 && nx < n && ny < n) && wall[x][y][dir] == 0 && !visited[nx][ny]) {
visited[nx][ny] = 1;
breeze(nx, ny, dir, temp - 1);
}
int ntx, nty;
for (int d = -1;d <= 1;d+=2) {
if (dir == 1 || dir == 3) { // 좌, 우
ny = y + d;
if ((nx >= 0 && ny >= 0 && nx < n && ny < n) && wall[x][y][get_dir(x, y, x, ny)] == 0 && wall[x][ny][get_dir(x, ny, nx, ny)] == 0 && !visited[nx][ny]) {
visited[nx][ny] = 1;
breeze(nx, ny, dir, temp - 1);
}
}
else {
nx = x + d;
if ((nx >= 0 && ny >= 0 && nx < n && ny < n) && wall[x][y][get_dir(x, y, nx, y)] == 0 && wall[nx][y][get_dir(nx, y, nx, ny)] == 0 && !visited[nx][ny]) {
visited[nx][ny] = 1;
breeze(nx, ny, dir, temp - 1);
}
}
}
}
wall 배열 만들어주기문제에서는 상단부, 좌측부만 입력으로 보여주는데, 이런 경우에는 코드 작성 시 조금 까다로움. 메모리가 좀 더 차지하더라도 한 위치당 상하좌우를 표시해줌.
for (int i = 0;i < m;i++) {
cin >> a >> b >> c;
a--, b--;
if (c == 0) {
wall[a][b][1] = 1;
wall[a-1][b][3] = 1;
}
else {
wall[a][b][0] = 1;
wall[a][b-1][2] = 1;
}
}
전체 코드
#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <cstring>
using namespace std;
typedef struct {
int x, y, dir;
}_loc;
// 좌 상 우 하
int n, m, k;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };
vector<pair<int, int>> office;
vector<_loc> ac;
int wall[21][21][4];
int arr[21][21];
void input() {
cin >> n >> m >> k;
int t;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
cin >> t;
if (t == 1) {
office.push_back({ i,j });
}
else if (t >= 2 && t <= 5) {
_loc tmp;
tmp.x = i, tmp.y = j, tmp.dir = t - 2;
ac.push_back(tmp);
}
}
}
int a, b, c;
for (int i = 0;i < m;i++) {
cin >> a >> b >> c;
a--, b--;
if (c == 0) {
wall[a][b][1] = 1;
wall[a-1][b][3] = 1;
}
else {
wall[a][b][0] = 1;
wall[a][b-1][2] = 1;
}
}
}
int visited[21][21];
int get_dir(int cx, int cy, int nx, int ny) {
if (cy - ny == 1) return 0;
else if (cx - nx == 1) return 1;
else if (cy - ny == -1) return 2;
else if (cx - nx == -1) return 3;
else {
cout << cx << " " << cy << " " << nx << " " << ny << "!\\n";
cout << "error!";
exit(0);
}
}
void breeze(int x, int y, int dir, int temp) {
arr[x][y] += temp;
if (temp == 1) return;
int nx, ny;
// 1. 바로 앞
nx = x + dx[dir], ny = y + dy[dir];
if ((nx >= 0 && ny >= 0 && nx < n && ny < n) && wall[x][y][dir] == 0 && !visited[nx][ny]) {
visited[nx][ny] = 1;
breeze(nx, ny, dir, temp - 1);
}
int ntx, nty;
for (int d = -1;d <= 1;d+=2) {
if (dir == 1 || dir == 3) { // 좌, 우
ny = y + d;
if ((nx >= 0 && ny >= 0 && nx < n && ny < n) && wall[x][y][get_dir(x, y, x, ny)] == 0 && wall[x][ny][get_dir(x, ny, nx, ny)] == 0 && !visited[nx][ny]) {
visited[nx][ny] = 1;
breeze(nx, ny, dir, temp - 1);
}
}
else {
nx = x + d;
if ((nx >= 0 && ny >= 0 && nx < n && ny < n) && wall[x][y][get_dir(x, y, nx, y)] == 0 && wall[nx][y][get_dir(nx, y, nx, ny)] == 0 && !visited[nx][ny]) {
visited[nx][ny] = 1;
breeze(nx, ny, dir, temp - 1);
}
}
}
}
void select_ac(int idx) {
memset(visited, 0, sizeof(visited));
int x, y, dir;
x = ac[idx].x, y = ac[idx].y, dir = ac[idx].dir;
x += dx[dir], y += dy[dir];
visited[x][y] = 1;
breeze(x, y, dir, 5);
}
int tmp[21][21];
void air_mix() {
memset(tmp, 0, sizeof(tmp));
int nx, ny;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
for (int k = 0;k < 4;k++) {
if (wall[i][j][k]) continue;
nx = i + dx[k], ny = j + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[i][j] > arr[nx][ny]) {
tmp[i][j] -= (arr[i][j] - arr[nx][ny]) / 4;
tmp[nx][ny] += (arr[i][j] - arr[nx][ny]) / 4;
}
}
tmp[i][j] += arr[i][j];
}
}
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
arr[i][j] = tmp[i][j];
if (i == 0 || j == 0 || i == n - 1 || j == n - 1) {
if(arr[i][j] > 0) arr[i][j]--;
}
}
}
}
bool solve() {
for (int i = 0;i < ac.size();i++) {
select_ac(i);
}
air_mix();
for (int i = 0;i < office.size();i++) {
if (arr[office[i].first][office[i].second] < k) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("sample_input.txt", "r", stdin);
input();
int result;
for (result = 1;result <= 100;result++) {
if (solve()) break;
}
if (result == 101) result = -1;
cout << result;
}