BOJ 23289 온풍기 안녕!(Java)
문제 탐색하기
- 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나타냈다.
- 각 칸 (r, c)의 온도를 실시간으로 모니터링하고 있고 (r, c)는 r행 c열을 의미
- 가장 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 의미한다.
- 집에 있는 모든 온풍기에서 바람이 한 번 나옴
- 온도가 조절됨
- 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
- 초콜릿을 하나 먹는다.
- 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사 해서 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.
위 그림은 7×8인 집에 온풍기가 (3, 1)에 설치되어 있는 상황이다.
- 온풍기는 바람이 나오는 방향이 있는데, 그 방향은 오른쪽, 왼쪽, 위, 아래 중 하나이다.
- 온풍기에서 따뜻한 바람이 한 번 나오면, 다음과 같은 영역의 온도가 칸에 적힌 값만큼 증가한다.
온풍기 바람이 한 번 불었다면, 증가하는 온도의 양은 위 그림과 같다.
위 그림과 같이, 벽이 존재하는 경우 바람이 이동할 수 없다.
-
바람이 오른쪽으로 불었을 때 어떤 칸 (x, y)에서 (x-1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x-1, y) 사이에 벽이 없어야 하고, (x-1, y)와 (x-1, y+1) 사이에도 벽이 없어야 한다.
-
(x, y)에서 (x, y+1)로 바람이 이동할 수 있으려면 (x, y)와 (x, y+1) 사이에 벽이 없어야 한다. 마지막으로 (x, y)에서 (x+1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x+1, y), (x+1, y)와 (x+1, y+1) 사이에 벽이 없어야 한다.
온풍기가 2대 이상 있을 수도 있다. 이 경우 각각의 온풍기에 의해서 상승한 온도를 모두 합한 값이 해당 칸의 상승한 온도이다.
온도가 조절되는 과정은 다음과 같다.
- 모든 인접한 칸에 대해서, 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이)/4⌋만큼 온도가 조절된다.
- 온도가 높은 칸은 이 값만큼 온도가 감소하고, 낮은 칸은 온도가 상승한다.
- 인접한 두 칸 사이에 벽이 있는 경우에는 온도가 조절되지 않는다.
이 과정은 모든 칸에 대해서 동시에 발생한다.
- 입력
방의 크기와 방에 설치된 온풍기의 정보, 벽의 위치와 조사하려고 하는 칸의 위치가 주어진다.
첫째 줄에 세 정수 R, C, K가 주어진다. 둘째 줄부터 R개의 줄에 방의 정보가 주어진다. i번째 줄의 j번째 정수는 (i, j)의 정보를 의미하며 다음 중 하나이다.
0: 빈 칸 1: 방향이 오른쪽인 온풍기가 있음 2: 방향이 왼쪽인 온풍기가 있음 3: 방향이 위인 온풍기가 있음 4: 방향이 아래인 온풍기가 있음 5: 온도를 조사해야 하는 칸
다음 줄에는 벽의 개수 W가 주어진다.
다음 W개의 줄에는 벽의 정보가 주어지며, 이 정보는 세 정수 x, y, t로 이루어져 있다.
t가 0인 경우 (x, y)와 (x-1, y) 사이에 벽이 있는 것이고, 1인 경우에는 (x, y)와 (x, y+1) 사이에 벽이 있는 것이다.
- 출력
먹은 초콜릿의 개수를 출력하고, 초콜릿의 개수가 100이상이면 101을 출력한다.
-
제한
- 2 ≤ R, C ≤ 20
- 1 ≤ K ≤ 1,000
- 온풍기는 하나 이상 있고, 온도를 조사해야 하는 칸도 하나 이상 있다.
- 0 ≤ W ≤ R×C
- 1 < x ≤ R, 1 ≤ y ≤ C (t = 0)
- 1 ≤ x ≤ R, 1 ≤ y < C (t = 1)
- 온풍기가 있는 칸과 바람이 나오는 방향에 있는 칸 사이에는 벽이 없다.
- 온풍기의 바람이 나오는 방향에 있는 칸은 항상 존재한다.
- 같은 벽이 두 번 이상 주어지는 경우는 없다.
코드 설계하기
구현 방법
- 바람 통해 확산 -> BFS.
- 벽에 의해 막혔을 경우 확산 안되게 처리
- 온풍기 바람 통해 확산된 것 전체 온풍기에 대해 처리
- 온도 조절 -> 모든 칸에 대해 동시에 일어나야 하므로 따로 함수 만들어서 처리
- 온도 감소 -> 모든 칸에 대해 동시에 일어나야 하므로 따로 함수 만들어서 처리
- 초콜릿 먹기 -> 카운트
- 조사하는 모든 칸의 온도가 K 이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다. -> 카운트 출력
바람 확산 과정 (blowWind 메서드)
- BFS 알고리즘을 사용하여 온풍기에서 퍼지는 바람을 시뮬레이션
- 각 온풍기마다 바람이 시작되는 칸부터 탐색 시작
- 큐를 사용하여 현재 위치에서 3방향(직진, 좌측 대각선, 우측 대각선)으로 퍼져나가는 바람 관리
- 바람 세기는 시작점에서 5로 시작하여 1씩 감소하며, 세기가 1이 되면 더 이상 퍼지지 않음
- 벽이 있는 경우
canSpread메서드로 해당 방향으로 바람이 퍼질 수 있는지 확인- 직진 방향: 단순히 두 칸 사이에 벽이 없는지 체크
- 대각선 방향: 두 가지 경로 중 하나라도 열려있는지 확인 (예: 위→오른쪽 또는 오른쪽→위)
온도 조절 과정 (adjustTemperature 메서드)
- 모든 칸에 대해 동시에 처리해야 하므로 임시 배열(
tempDiff)에 변화량을 저장 - 각 칸마다 인접한 4방향을 확인하여 온도 차이를 계산
- 온도 차이의 1/4만큼 높은 칸에서 낮은 칸으로 이동 (정수 나눗셈)
- 벽이 있는 경우 온도 조절이 일어나지 않음
- 마지막에 변화량을 모든 칸에 한 번에 적용
가장자리 온도 감소 (decreaseEdgeTemperature 메서드)
- 위쪽 행(r=0), 아래쪽 행(r=R-1), 왼쪽 열(c=0), 오른쪽 열(c=C-1)의 온도가 0보다 크면 1씩 감소
- 중복 감소를 방지하기 위해 코너 칸은 처리 순서에 주의
온도 확인 과정 (isComfortable 메서드)
- 모든 조사 지점을 순회하며 온도가 K 이상인지 확인
- 하나라도 K 미만이면
false반환
시간 복잡도
- 격자 크기: R×C (최대 20×20)
- 온풍기 바람 시뮬레이션: O(온풍기 수 × R×C) ≈ O((R×C)²) (최악의 경우)
- 각 온풍기마다 BFS로 최대 R×C 칸 탐색 가능
- 온도 조절: O(R×C) (모든 칸에 대해 4방향 확인)
- 가장자리 온도 감소: O(R+C) (모든 가장자리 칸)
- 최대 반복 횟수: 100회
- 전체 시간 복잡도: O(100 × (R×C)²) = O((R×C)²)
- 20×20 격자 기준 최악의 경우, 약 16,000,000번 연산 발생
정답 코드 (Java)
package simulation;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class b23289 {
private static int[][] map;
private static int R, C, K, W, cnt = 0;
// 방향: 0은 사용안함, 1:오른쪽, 2:왼쪽, 3:위쪽, 4:아래쪽
private static int[] dr = {0, 0, 0, -1, 1}; // 온풍기 방향
private static int[] dc = {0, 1, -1, 0, 0}; // 온풍기 방향
// 각 방향별로 퍼지는 바람의 방향 (행,열)
private static int[][] spreadR = {{0, 0, 0}, {-1, 0, 1}, {-1, 0, 1}, {-1, -1, -1}, {1, 1, 1}};
private static int[][] spreadC = {{0, 0, 0}, {1, 1, 1}, {-1, -1, -1}, {-1, 0, 1}, {-1, 0, 1}};
// 벽 정보 저장
private static boolean[][][][] wall;
// 조사할 칸과 온풍기 정보
private static List<Point> checkPoints = new ArrayList<>();
private static List<Heater> heaters = new ArrayList<>();
private static final int MAX = 100;
// 위치 정보
static class Point {
int r, c; // 행, 열
public Point(int r, int c) {
this.r = r;
this.c = c;
}
}
// 온풍기 정보
static class Heater {
int r, c, dir; // 행, 열, 방향
public Heater(int r, int c, int dir) {
this.r = r;
this.c = c;
this.dir = dir;
}
}
// 바람 퍼짐 정보
static class Wind {
int r, c, power;
Wind(int r, int c, int power) {
this.r = r;
this.c = c;
this.power = power;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new int[R][C];
wall = new boolean[R][C][R][C];
for (int r = 0; r < R; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 0; c < C; c++) {
int value = Integer.parseInt(st.nextToken());
if (value == 5) {
checkPoints.add(new Point(r, c));
} else if (value >= 1 && value <= 4) {
heaters.add(new Heater(r, c, value));
}
}
}
st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
for (int i = 0; i < W; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken()) - 1; // 행
int y = Integer.parseInt(st.nextToken()) - 1; // 열
int t = Integer.parseInt(st.nextToken());
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;
}
}
while (cnt <= MAX && !isComfortable()) {
// 1. 온풍기 바람 나옴
blowWind();
// 2. 온도 조절
adjustTemperature();
// 3. 가장 바깥쪽 칸 온도 1 감소
decreaseEdgeTemperature();
// 4. 초콜릿 먹기
cnt++;
// 5. 모든 칸의 온도가 K 이상인지 확인
// isComfortable() 함수를 while 조건에서 체크
}
System.out.println(cnt > 100 ? 101 : cnt);
}
// 온풍기 바람 나오는 함수
private static void blowWind() {
for (Heater heater : heaters) {
int r = heater.r;
int c = heater.c;
int dir = heater.dir;
// 바람이 처음 나오는 칸
int nr = r + dr[dir];
int nc = c + dc[dir];
if (!inRange(nr, nc)) continue;
boolean[][] visited = new boolean[R][C];
Queue<Wind> q = new ArrayDeque<>();
// 바람 시작점
visited[nr][nc] = true;
map[nr][nc] += 5; // 온도 5 상승
q.offer(new Wind(nr, nc, 5));
while (!q.isEmpty()) {
Wind curr = q.poll();
if (curr.power == 1) continue; // 파워 1이면 더 퍼지지 않음
// 3방향으로 퍼짐
for (int i = 0; i < 3; i++) {
int nnr = curr.r + spreadR[dir][i];
int nnc = curr.c + spreadC[dir][i];
if (!inRange(nnr, nnc) || visited[nnr][nnc]) continue;
if (!canSpread(curr.r, curr.c, nnr, nnc, dir, i)) continue;
visited[nnr][nnc] = true;
map[nnr][nnc] += (curr.power - 1); // 온도 증가
q.offer(new Wind(nnr, nnc, curr.power - 1));
}
}
}
}
// 바람이 퍼질 수 있는지 벽 체크하는 함수
private static boolean canSpread(int r1, int c1, int r2, int c2, int dir, int idx) {
if (dir == 1) { // 오른쪽
if (idx == 0) { // 위+오른쪽
return !wall[r1][c1][r1-1][c1] && !wall[r1-1][c1][r1-1][c1+1];
} else if (idx == 1) { // 직진
return !wall[r1][c1][r1][c1+1];
} else { // 아래+오른쪽
return !wall[r1][c1][r1+1][c1] && !wall[r1+1][c1][r1+1][c1+1];
}
} else if (dir == 2) { // 왼쪽
if (idx == 0) { // 위+왼쪽
return !wall[r1][c1][r1-1][c1] && !wall[r1-1][c1][r1-1][c1-1];
} else if (idx == 1) { // 직진
return !wall[r1][c1][r1][c1-1];
} else { // 아래+왼쪽
return !wall[r1][c1][r1+1][c1] && !wall[r1+1][c1][r1+1][c1-1];
}
} else if (dir == 3) { // 위쪽
if (idx == 0) { // 왼쪽+위
return !wall[r1][c1][r1][c1-1] && !wall[r1][c1-1][r1-1][c1-1];
} else if (idx == 1) { // 직진
return !wall[r1][c1][r1-1][c1];
} else { // 오른쪽+위
return !wall[r1][c1][r1][c1+1] && !wall[r1][c1+1][r1-1][c1+1];
}
} else { // 아래쪽
if (idx == 0) { // 왼쪽+아래
return !wall[r1][c1][r1][c1-1] && !wall[r1][c1-1][r1+1][c1-1];
} else if (idx == 1) { // 직진
return !wall[r1][c1][r1+1][c1];
} else { // 오른쪽+아래
return !wall[r1][c1][r1][c1+1] && !wall[r1][c1+1][r1+1][c1+1];
}
}
}
// 온도 조절 함수
private static void adjustTemperature() {
int[][] tempDiff = new int[R][C]; // 온도 변화량 저장
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
for (int d = 1; d <= 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (!inRange(nr, nc) || wall[r][c][nr][nc]) continue;
int diff = (map[r][c] - map[nr][nc]) / 4;
if (diff > 0) {
tempDiff[r][c] -= diff;
tempDiff[nr][nc] += diff;
}
}
}
}
// 온도 변화 적용
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
map[r][c] += tempDiff[r][c];
}
}
}
// 가장 바깥쪽 칸 온도 감소 함수
private static void decreaseEdgeTemperature() {
// 위쪽과 아래쪽 행
for (int c = 0; c < C; c++) {
if (map[0][c] > 0) map[0][c]--;
if (map[R-1][c] > 0) map[R-1][c]--;
}
// 왼쪽과 오른쪽 열 (가장자리 제외)
for (int r = 1; r < R-1; r++) {
if (map[r][0] > 0) map[r][0]--;
if (map[r][C-1] > 0) map[r][C-1]--;
}
}
// 모든 조사 칸의 온도가 K 이상인지 확인
private static boolean isComfortable() {
for (Point p : checkPoints) {
if (map[p.r][p.c] < K) {
return false;
}
}
return true;
}
// 범위 체크
private static boolean inRange(int r, int c) {
return r >= 0 && r < R && c >= 0 && c < C;
}
}
Leave a comment