[백준 23289번] 온풍기 안녕!

문제 링크: https://www.acmicpc.net/problem/23289

23289번: 온풍기 안녕!

<문제 풀이> BFS, 시뮬레이션

 

0. 입력

온도, 온풍기, 조사하는 칸을 각각 2차원 배열로 표현했습니다.

int temperature[21][21];
int heater[21][21];
int inspection[21][21];

(a, b)와 (c, d) 사이에 벽이 있다는 것을 표현하기 위해서 다음과 같이 4차원 배열을 만들었습니다.

bool wall[21][21][21][21]; //wall[a][b][c][d] : (a,b)에서 (c,d) 방향으로 바람을 막는 벽이 존재하면 true

wall[a][b][c][d]가 참이면 (a, b)에서 (c, d) 방향으로 바람을 막는 벽이 존재합니다.

wall[c][d][a][b]가 참이면 (c, d)에서 (a, b) 방향으로 바람을 막는 벽이 존재합니다.

위 두 가지를 표현함으로써 (a,b)와 (c, d) 사이에 벽을 만들 수 있습니다.

 

int w; cin >> w;
	for (int i = 0; i < w; i++) {
		int x, y, t; cin >> x >> y >> t;
		if (t == 0) {
			wall[x][y][x - 1][y] = true;
			wall[x - 1][y][x][y] = true;
		}
		else {
			wall[x][y][x][y + 1] = true;
			wall[x][y + 1][x][y] = true;
		}
	}

 

 

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴

 

오른쪽으로 바람이 불 때 각 칸에 있는 바람은 오른쪽 위, 오른쪽, 오른쪽 아래 방향으로 한 칸 이동하게 됩니다.

이때 현재 칸과 이동하려는 칸 사이에 벽이 존재한다면 이동할 수 없습니다.

이동할 수 있다면 다음 칸으로 이동하면 되는 데, 다음 칸의 온도 값은 (현재 칸의 온도 값 - 1)이 됩니다.

 

(x, y)에서 오른쪽인 (x, y + 1)으로 바람이 이동할 수 있는지는 판단하는 방법은 wall[x][y][x][y+1]의 값이 true인지만 확인하면 알 수 있습니다

그러나 (x, y)에서 오른쪽 위인 (x -1, y 1), 오른쪽 아래인 (x + 1, y + 1)으로 바람이 이동할 수 있는지 판별하는 것은 두 좌표만 가지고는 알 수 없습니다.

 

이 부분은 대각선 방향으로 바로 이동하는 것이 아닌 좌표를 하나 경유해서 이동하면 쉽게 해결할 수 있습니다.

 

아래 그림을 보면

 

 

(x, y)에서 오른쪽 위로 가기 위해서 (x - 1, y)를 경유하고, 오른쪽 아래로 가기 위해서 (x + 1, y)를 경유합니다.

 

대각선 방향인 오른쪽 위로 가기 위해서 아래 두 가지를 체크해보면 됩니다.

 

1) (x, y)와 (x - 1, y) 사이에 벽이 있는가? => wall[x][y][x-1][y]

2) (x - 1, y)와 (x -1, y + 1) 사이에  벽이 있는가? => wall[x-1][y][x-1][y+1]

 

(x -1, y)와 (x - 1, y + 1) 사이에 벽이 있기 때문에 결과적으로 오른쪽 위로 갈 수 없습니다.

 

추가적으로 현재 좌표의 온도가 2 이상일 경우에만 바람이 이동하도록 하면 됩니다. 현재 좌표의 온도가 1이라면 다음 좌표부터는 온도가 0 이하가 되기 때문이 이동할 필요가 없습니다.

 

위 내용들을 바탕으로 오른쪽 세 방향으로 이동하는 BFS를 구현하면 됩니다.

바람의 온도는 5부터 시작하고 온풍기 하나가 만든 온도는 임시 배열에 저장했다가 마지막에 원본 온도 배열에 누적하면 됩니다.

 

아래는 오른쪽 방향을 구현한 코드이고 왼쪽, 아래쪽, 위쪽 방향도 오른쪽 방향 구현과 같은 식으로 하면 됩니다.

 

// 1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
bool check(int cx, int cy, int nx, int ny) {
	return !(nx < 1 || ny < 1 || nx>R || ny > C || wall[cx][cy][nx][ny]);
}

void rightHeat(int x, int y) {
	queue<pair<int, int > >Q;
	int temp[21][21];
	fill(&temp[0][0], &temp[20][21], 0);

	Q.push({ x, y + 1 });
	temp[x][y + 1] = 5;
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		// (x,y)에서 위 칸을 경유해서 오른쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
		if (check(cur.X, cur.Y, cur.X - 1, cur.Y) && check(cur.X - 1, cur.Y, cur.X - 1, cur.Y + 1) && temp[cur.X][cur.Y] >= 2) {
			Q.push({ cur.X - 1, cur.Y + 1 }); // 바람을 다음 칸으로 이동
			temp[cur.X - 1][cur.Y + 1] = temp[cur.X][cur.Y] - 1;
		}
		// (x, y)에서 오른쪽으로 갈 수 있으면서 (x,y)에 온도가 2 이상이면
		if (check(cur.X, cur.Y, cur.X, cur.Y + 1) && temp[cur.X][cur.Y] >= 2) {
			Q.push({ cur.X, cur.Y + 1 }); // 바람을 다음 칸으로 이동
			temp[cur.X][cur.Y + 1] = temp[cur.X][cur.Y] - 1;
		}
		// (x, y)에서 아래 칸을 경유해서 오른쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
		if (check(cur.X, cur.Y, cur.X + 1, cur.Y) && check(cur.X + 1, cur.Y, cur.X + 1, cur.Y + 1) && temp[cur.X][cur.Y] >= 2) {
			Q.push({ cur.X + 1, cur.Y + 1 }); // 바람을 다음 칸으로 이동
			temp[cur.X + 1][cur.Y + 1] = temp[cur.X][cur.Y] - 1;
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			temperature[i][j] += temp[i][j];
		}
	}

}


void heat() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (heater[i][j]) {
				if (heater[i][j] == RIGHT) {
					rightHeat(i, j);
				}
				else if (heater[i][j] == LEFT) {
					leftHeat(i, j);
				}
				else if (heater[i][j] == UP) {
					upHeat(i, j);

				}
				else if (heater[i][j] == DOWN) {
					downHeat(i, j);
				}
			}
		}
	}
}

 

2. 온도가 조절됨

 

온도 조절은 단순히 각 칸에 대해서 남, 동 방향으로 온도를 조절하면 됩니다. 동, 서, 남, 북을 모두 하지 않는 이유는 한 번 조절한 두 칸 사이에는 온도를 다시 조절하면 안 되기 때문입니다. 남, 동 방향으로만 온도 조절하면 중복 없이 인접한 칸에 대해서 온도 조절을 할 수 있습니다.

 

한 가지 주의할 점은 온도는 동시에 조절되기 때문에 임시 변수에 저장해 두었다가 실제 배열에 반영해야 합니다.

 

// 2. 온도가 조절됨
void adjust() {
	int temp[21][21];
	fill(&temp[0][0], &temp[20][21], 0);
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			for (int dir = 0; dir < 2; dir++) { //온도 조절은 남, 동 방향으로만 하면 됨(한 번 조절한 두 칸 사이에는 다시 조절하면 안 되기 때문)
				int nx = i + adjustDx[dir];
				int ny = j + adjustDy[dir];
				if (nx < 1 || ny < 1 || nx > R || ny > C) continue;
				if (wall[i][j][nx][ny] || wall[nx][ny][i][j]) continue; // 두 좌표 사이에 벽이 있으면 온도를 조절하지 않는다.
				int L = abs(temperature[i][j] - temperature[nx][ny]);
				if (temperature[i][j] > temperature[nx][ny]) {
					temp[i][j] -= L / 4;
					temp[nx][ny] += L / 4;
				}
				else if (temperature[i][j] < temperature[nx][ny]) {
					temp[i][j] += L / 4;
					temp[nx][ny] -= L / 4;
				}
			}
		}
	}
	//온도는 동시에 조절되기 때문에 임시 변수에 저장해두었다가 실제 배열에 반영해야함.
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			temperature[i][j] += temp[i][j];
			if (temperature[i][j] < 0) temperature[i][j] = 0;
		}
	}
}

 

3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소

 

모든 칸을 순회하면서 각 좌표가 2 <=i <=R-1 and 2 <= j <= C - 1이면 무시하고 그렇지 않으면 온도를 1 감소시키면 됩니다. 

 

// 3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
void decreseBorderTemperature() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (i >= 2 && i <= R - 1 && j >= 2 && j <= C - 1) continue; // 안쪽 칸이면 무시
			if (temperature[i][j]) temperature[i][j]--;
		}
	}
}

 

4. 초콜릿을 하나 먹는다.

 

// 4. 초콜릿을 하나 먹는다.
void eat() {
	chocolate++;
}

 

5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K 이상이면 테스트 중단, 아니면 1부터 다시 시작

 

// 5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K 이상이면 테스트 중단, 아니면 1부터 다시 시작
bool stop() {
	if (chocolate > 100) return true; // 초콜릿을 101개 이상 먹었으면 테스트 종료
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (inspection[i][j] && temperature[i][j] < K) return false;
		}
	}
	return true;
}

 

 

6. solve 함수

void solve() {
	input();
	do {
		heat(); // 1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
		adjust(); // 2. 온도가 조절됨
		decreseBorderTemperature(); // 3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
		eat(); // 4. 초콜릿을 하나 먹는다.
	} while (!stop()); // 5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.
	cout << chocolate;

}

 

 

<전체 C++소스코드>

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
#define X first
#define Y second
 
#define RIGHT 1
#define LEFT 2
#define UP 3
#define DOWN 4
 
int R, C, K;
 
int temperature[21][21]; // 온도를 표현하는 배열
int heater[21][21]; // 온풍기를 표현하는 배열
bool inspection[21][21]; // 온도를 조사해야 하는 칸이면 true
int chocolate = 0;
bool wall[21][21][21][21]; //wall[a][b][c][d] : (a,b)에서 (c,d) 방향으로 바람을 막는 벽이 존재하면 true
const int dx[5] = { 0, 0, 0, -1, 1 };
const int dy[5] = { 0, 1, -1, 0, 0 };
const int adjustDx[2] = {1, 0}; // 온도 조절은 남, 동 방향으로만 하면 된다.
const int adjustDy[2] = {0, 1};
void input() {
    cin >> R >> C >> K;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            int value; cin >> value;
            if (value == 5) inspection[i][j] = true;
            else if (value == 0)temperature[i][j] = 0;
            else heater[i][j] = value;
 
        }
    }
    int w; cin >> w;
    for (int i = 0; i < w; i++) {
        int x, y, t; cin >> x >> y >> t;
        if (t == 0) {
            wall[x][y][x - 1][y] = true;
            wall[x - 1][y][x][y] = true;
        }
        else {
            wall[x][y][x][y + 1] = true;
            wall[x][y + 1][x][y] = true;
        }
    }
}
 
// 1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
bool check(int cx, int cy, int nx, int ny) {
    return !(nx < 1 || ny < 1 || nx>R || ny > C || wall[cx][cy][nx][ny]);
}
 
void rightHeat(int x, int y) {
    queue<pair<int, int > >Q;
    int temp[21][21];
    fill(&temp[0][0], &temp[20][21], 0);
 
    Q.push({ x, y + 1 });
    temp[x][y + 1] = 5;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        // (x,y)에서 위 칸을 경유해서 오른쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X - 1, cur.Y) && check(cur.X - 1, cur.Y, cur.X - 1, cur.Y + 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X - 1, cur.Y + 1 }); // 바람을 다음 칸으로 이동
            temp[cur.X - 1][cur.Y + 1] = temp[cur.X][cur.Y] - 1;
        }
        // (x, y)에서 오른쪽으로 갈 수 있으면서 (x,y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X, cur.Y + 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X, cur.Y + 1 }); // 바람을 다음 칸으로 이동
            temp[cur.X][cur.Y + 1] = temp[cur.X][cur.Y] - 1;
        }
        // (x, y)에서 아래 칸을 경유해서 오른쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X + 1, cur.Y) && check(cur.X + 1, cur.Y, cur.X + 1, cur.Y + 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X + 1, cur.Y + 1 }); // 바람을 다음 칸으로 이동
            temp[cur.X + 1][cur.Y + 1] = temp[cur.X][cur.Y] - 1;
        }
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            temperature[i][j] += temp[i][j];
        }
    }
 
}
void leftHeat(int x, int y) {
    queue<pair<int, int > >Q;
    int temp[21][21];
    fill(&temp[0][0], &temp[20][21], 0);
 
    Q.push({ x, y - 1 });
    temp[x][y - 1] = 5;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        // (x,y)에서 위 칸을 경유해서 왼쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X - 1, cur.Y) && check(cur.X - 1, cur.Y, cur.X - 1, cur.Y - 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X - 1, cur.Y - 1 });
            temp[cur.X - 1][cur.Y - 1] = temp[cur.X][cur.Y] - 1;
        }
        // (x, y)에서 왼쪽으로 갈 수 있으면서 (x,y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X, cur.Y - 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X, cur.Y - 1 });
            temp[cur.X][cur.Y - 1] = temp[cur.X][cur.Y] - 1;
        }
        // (x,y)에서 아래 칸을 경유해서 왼쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X + 1, cur.Y) && check(cur.X + 1, cur.Y, cur.X + 1, cur.Y - 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X + 1, cur.Y - 1 });
            temp[cur.X + 1][cur.Y - 1] = temp[cur.X][cur.Y] - 1;
        }
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            temperature[i][j] += temp[i][j];
        }
    }
}
void upHeat(int x, int y) {
    queue<pair<int, int > >Q;
    int temp[21][21];
    fill(&temp[0][0], &temp[20][21], 0);
    Q.push({ x - 1, y });
    temp[x - 1][y] = 5;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        // (x,y)에서 왼쪽 칸을 경유해서 위쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X, cur.Y - 1) && check(cur.X, cur.Y - 1, cur.X - 1, cur.Y - 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X - 1, cur.Y - 1 });
            temp[cur.X - 1][cur.Y - 1] = temp[cur.X][cur.Y] - 1;
        }
        // (x, y)에서 위쪽으로 갈 수 있으면서 (x,y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X - 1, cur.Y) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X - 1, cur.Y });
            temp[cur.X - 1][cur.Y] = temp[cur.X][cur.Y] - 1;
        }
        // (x,y)에서 오른쪽 칸을 경유해서 위쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X, cur.Y + 1) && check(cur.X, cur.Y + 1, cur.X - 1, cur.Y + 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X - 1, cur.Y + 1 });
            temp[cur.X - 1][cur.Y + 1] = temp[cur.X][cur.Y] - 1;
        }
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            temperature[i][j] += temp[i][j];
        }
    }
}
void downHeat(int x, int y) {
    queue<pair<int, int > >Q;
    int temp[21][21];
    fill(&temp[0][0], &temp[20][21], 0);
 
    Q.push({ x + 1, y });
    temp[x + 1][y] = 5;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        // (x,y)에서 왼쪽 칸을 경유해서 아래쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X, cur.Y - 1) && check(cur.X, cur.Y - 1, cur.X + 1, cur.Y - 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X + 1, cur.Y - 1 });
            temp[cur.X + 1][cur.Y - 1] = temp[cur.X][cur.Y] - 1;
        }
        // (x, y)에서 아래쪽으로 갈 수 있으면서 (x,y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X + 1, cur.Y) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X + 1, cur.Y });
            temp[cur.X + 1][cur.Y] = temp[cur.X][cur.Y] - 1;
        }
        // (x,y)에서 오른쪽 칸을 경유해서 아래쪽으로 갈 수 있고 (x, y)에 온도가 2 이상이면
        if (check(cur.X, cur.Y, cur.X, cur.Y + 1) && check(cur.X, cur.Y + 1, cur.X + 1, cur.Y + 1) && temp[cur.X][cur.Y] >= 2) {
            Q.push({ cur.X + 1, cur.Y + 1 });
            temp[cur.X + 1][cur.Y + 1] = temp[cur.X][cur.Y] - 1;
        }
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            temperature[i][j] += temp[i][j];
        }
    }
}
void heat() {
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (heater[i][j]) {
                if (heater[i][j] == RIGHT) {
                    rightHeat(i, j);
                }
                else if (heater[i][j] == LEFT) {
                    leftHeat(i, j);
                }
                else if (heater[i][j] == UP) {
                    upHeat(i, j);
 
                }
                else if (heater[i][j] == DOWN) {
                    downHeat(i, j);
                }
            }
        }
    }
}
 
 
// 2. 온도가 조절됨
void adjust() {
    int temp[21][21];
    fill(&temp[0][0], &temp[20][21], 0);
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            for (int dir = 0; dir < 2; dir++) { //온도 조절은 남, 동 방향으로만 하면 됨(한 번 조절한 두 칸 사이에는 다시 조절하면 안 되기 때문)
                int nx = i + adjustDx[dir];
                int ny = j + adjustDy[dir];
                if (nx < 1 || ny < 1 || nx > R || ny > C) continue;
                if (wall[i][j][nx][ny] || wall[nx][ny][i][j]) continue; // 두 좌표 사이에 벽이 있으면 온도를 조절하지 않는다.
                int L = abs(temperature[i][j] - temperature[nx][ny]);
                if (temperature[i][j] > temperature[nx][ny]) {
                    temp[i][j] -= L / 4;
                    temp[nx][ny] += L / 4;
                }
                else if (temperature[i][j] < temperature[nx][ny]) {
                    temp[i][j] += L / 4;
                    temp[nx][ny] -= L / 4;
                }
            }
        }
    }
    //온도는 동시에 조절되기 때문에 임시 변수에 저장해두었다가 실제 배열에 반영해야함.
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            temperature[i][j] += temp[i][j];
            if (temperature[i][j] < 0) temperature[i][j] = 0;
        }
    }
}
 
// 3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
void decreseBorderTemperature() {
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (i >= 2 && i <= R - 1 && j >= 2 && j <= C - 1) continue; // 안쪽 칸이면 무시
            if (temperature[i][j]) temperature[i][j]--;
        }
    }
}
 
// 4. 초콜릿을 하나 먹는다.
void eat() {
    chocolate++;
}
 
 
 
// 5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K 이상이면 테스트 중단, 아니면 1부터 다시 시작
bool stop() {
    if (chocolate > 100) return true; // 초콜릿을 101개 이상 먹었으면 테스트 종료
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (inspection[i][j] && temperature[i][j] < K) return false;
        }
    }
    return true;
}
 
void solve() {
    input();
    do {
        heat(); // 1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
        adjust(); // 2. 온도가 조절됨
        decreseBorderTemperature(); // 3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
        eat(); // 4. 초콜릿을 하나 먹는다.
    } while (!stop()); // 5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.
    cout << chocolate;
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    solve();
 
    return 0;
}