BOJ_23289_온풍기 안녕!
1회 순환까지 절차가 많은 구현 문제
구상 자체는 어렵지 않았으나 문제가 길다보니 입력 받는 좌표값을 -1 배열에 맞게 해주지 않았다든가 조건을 하나 빼먹었다든가 하는 디테일에 시간을 뺏겼다
구현을 풀 때 거의 매번 발생하는 문제이기 때문에 항상 리마인드 하고 문제에 임하자!
풀이
1회 순환은 크게 5단계로 나뉜다
- 집에 있는 모든 온풍기에서 바람이 한 번 나옴
- 온도가 조절됨
- 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
- 초콜릿을 하나 먹는다.
- 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.
문제가 복잡해지는 이유는 벽이 존재하기 때문인데, 한 칸을 모두 차지하는 단순한 벽이 아니라 y,x 와 y+1, x 사이에 존재하는 벽이기 때문이다
벽이 존재하는 칸에는 바람이 갈 수 없다. 또한 바람이 대각선으로 퍼지는 과정에서 한 칸에 ㄱ자 형태의 벽이 설치되어 있다면 직접적으로 벽이 막는 칸 뿐만 아니라 간접적으로 막히는 칸에도 바람이 가지 않는다
![[upload.acmicpc 1.avif]]
그렇기 때문에 1번 조건을 구현할 때 Queue를 사용해야 한다. 직선, 대각선, 반대쪽 대각선 3개의 조건을 탐색해 지나갈 수 있는 칸만 queue에 넣어준다. queue에는 {y, x, 다음 탐색 칸에 더해줄 온도} 를 넣었다. 너비 우선 탐색을 하기 때문에 온도를 배열에 가져가야 depth마다 5, 4, 3, 2, 1로 줄어드는 온도를 넣어줄 수 있다
이와는 반대로 온도를 조절할 때는 모든 칸을 탐색해야 하기 때문에 배열을 사용한다
여기서 두 칸 사이가 벽으로 막혀있다면 온도 조절을 할 수 없다
벽에는 4개의 방향이 있기 때문에 R x C 크기의 칸마다 네 방향을 탐색해야 한다. 처음에 문제를 풀 때는 벽이 모든 칸에 있는 것도 아닌데 너무 큰 배열을 쓰는 건 아닌가 싶어서 Map에 key는 방향, value는 벽 리스트를 넣어서 사용했는데 다 풀고 생각해보니 벽을 확인하는 로직이 많기 때문에 List를 너무 자주 탐색하게 된다. 처음부터 3차원 배열로 선언하는 게 검사 효율이 높았을 것이다
온도를 조절하면서 이미 온도를 조절한 인접하는 2개의 칸은 중복 검사하지 않기 위하여 3차원 방문 배열을 사용했다. 현재 탐색하는 것이 y, x의 LEFT 라면 y, x-1 의 RIGHT 가 방문처리 되어 있는지 확인한다
package BJO;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJO_23289_온풍기안녕 {
static int R;
static int C;
static int K;
static int W;
static Map<Integer, List<int[]>> wallMap;
static final int EMPTY = 0;
static final int RIGHT = 1;
static final int LEFT = 2;
static final int UP = 3;
static final int DOWN = 4;
static final int CHECKBLOCK = 5;
static List<int[]> heaters = new ArrayList<>();
static List<int[]> checkBlocks = new ArrayList<>();
static int[] dy = {0, 0, -1, 1};
static int[] dx = {1, -1, 0, 0};
static int chocolate;
static int[][] temperature;
static boolean flag;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int[][] room = input(br, st);
while (!flag) {
warmWind(room);
int[][] temp = adjustTemperature();
adjustTemperature2(temp);
chocolate++;
// 조사
if (!checkTemperature() || chocolate == 101) {
flag = true;
System.out.println(chocolate);
}
}
}
private static int[][] input(BufferedReader br, StringTokenizer st) throws IOException {
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
int[][] room = new int[R][C];
temperature = new int[R][C];
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
room[i][j] = Integer.parseInt(st.nextToken());
if (room[i][j] > EMPTY && room[i][j] < CHECKBLOCK) {
heaters.add(new int[]{i, j});
} else if (room[i][j] == CHECKBLOCK) {
checkBlocks.add(new int[]{i, j});
}
}
}
W = Integer.parseInt(br.readLine());
wallMap = new HashMap<>();
wallMap.put(RIGHT, new ArrayList<>());
wallMap.put(LEFT, new ArrayList<>());
wallMap.put(UP, new ArrayList<>());
wallMap.put(DOWN, new ArrayList<>());
for (int i = 0; i < W; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
int t = Integer.parseInt(st.nextToken());
if (t == 0) {
wallMap.get(UP).add(new int[]{y, x});
wallMap.get(DOWN).add(new int[]{y - 1, x});
} else {
wallMap.get(RIGHT).add(new int[]{y, x});
wallMap.get(LEFT).add(new int[]{y, x + 1});
}
}
return room;
}
private static boolean checkTemperature() {
for (int[] idx : checkBlocks) {
if (temperature[idx[0]][idx[1]] < K) {
return true;
}
}
return false;
}
private static void adjustTemperature2(int[][] temp) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
temperature[i][j] += temp[i][j];
if ((i == 0 || j == 0 || i == R - 1 || j == C - 1) && temperature[i][j] > 0) {
temperature[i][j]--;
}
}
}
}
private static int[][] adjustTemperature() {
// 온도 조절
int[][] temp = new int[R][C];
boolean[][][] visited = new boolean[R][C][5];
for (int y = 0; y < R; y++) {
for (int x = 0; x < C; x++) {
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (rangeCheck(ny, nx)) {
int pTemp = temperature[y][x];
int nTemp = temperature[ny][nx];
int adjust = Math.abs(pTemp - nTemp) / 4;
int opposite = (i + 1) % 2 == 0 ? i : i + 2;
if (pTemp != nTemp && isNotWall(y, x, i + 1) && !visited[ny][nx][opposite]) {
temp[y][x] += pTemp > nTemp ? -adjust : adjust;
temp[ny][nx] += pTemp > nTemp ? adjust : -adjust;
visited[y][x][i + 1] = true;
}
}
}
}
}
return temp;
}
private static boolean isNotWall(int y, int x, int dir) {
return wallMap.get(dir).stream().noneMatch(wall -> wall[0] == y && wall[1] == x);
}
private static void warmWind(int[][] room) {
for (int[] idx : heaters) {
boolean[][] visited = new boolean[R][C];
int dir = room[idx[0]][idx[1]];
int y = idx[0] + dy[dir - 1];
int x = idx[1] + dx[dir - 1];
Queue<int[]> queue = new ArrayDeque<>();
if (!rangeCheck(y, x)) {
continue;
}
temperature[y][x] += 5;
queue.offer(new int[]{y, x, 4});
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int ny = arr[0] + dy[dir - 1];
int nx = arr[1] + dx[dir - 1];
int nowTemp = arr[2];
// 직진
if (rangeCheck(ny, nx) && !visited[ny][nx] && isNotWall(arr[0], arr[1], dir)) {
visited[ny][nx] = true;
temperature[ny][nx] += nowTemp;
if (nowTemp != 0) {
queue.offer(new int[]{ny, nx, nowTemp - 1});
}
}
// 대각선
int nDir = dir + 2 > 4 ? dir - 2 : dir + 2;
checkCross(queue, visited, dir - 1, arr, nDir - 1);
// 대각선 반대
nDir = nDir % 2 == 0 ? nDir - 1 : nDir + 1;
checkCross(queue, visited, dir - 1, arr, nDir - 1);
}
}
}
private static void checkCross(Queue<int[]> queue, boolean[][] visited, int dir, int[] arr, int nDir) {
int ny = arr[0] + dy[nDir];
int nx = arr[1] + dx[nDir];
int nowTemp = arr[2];
if (rangeCheck(ny, nx) && isNotWall(arr[0], arr[1], nDir + 1)) {
int nny = ny + dy[dir];
int nnx = nx + dx[dir];
if (rangeCheck(nny, nnx) && !visited[nny][nnx] && isNotWall(ny, nx, dir + 1)) {
visited[nny][nnx] = true;
temperature[nny][nnx] += nowTemp;
if (nowTemp != 0) {
queue.offer(new int[]{nny, nnx, nowTemp - 1});
}
}
}
}
static boolean rangeCheck(int y, int x) {
return y < R && y >= 0 && x < C && x >= 0;
}
}