알고리즘/알고리즘문풀
BOJ - 온풍기 안녕! 23289번 (JAVA)
developer-ellen
2022. 4. 30. 16:17
❓ 문제 - 백준 온풍기 안녕! 23289번 - JAVA 풀이법
출처
(https://www.acmicpc.net/problem/23289)
23289번: 온풍기 안녕!
유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기
www.acmicpc.net
📝 문제해결법
1. 이 문제는 구현으로 풀었다.
- 벽에 대한 정보를 ArryList 2차원 배열인 map_wall로 관리하였다. 만약 i, j행에 0이라는 숫자가 있으면 (i, j)위치의 윗부분에 벽이 있다는 것이고, 1이라는 숫자가 존재하면 (i, j)위치에 오른쪽부분에 벽이 있다는 의미이다.
- 온풍기에서 나오는 바람은 각 방향에 맞춰 3방향으로 영향을 줄 수 있으며 만약 그 방향에 맞춰 이동할 곳에 벽이 존재한다면 바람이 이동하지 못한다.
- 각 이동 방향에 맞춰 이동할 수 있는 부분이 빨간색이고 해당 곳에 이동을 하기 위해서는 위와 같이 현재 위치(x, y)에서 각 이동할 방향에 맞춰 벽이 존재하는지를 탐색해야한다. 이것을 check_wall이라는 3차원 배열을 통해 구현하였으며 각 방향(동, 서, 북, 남) 의 방향에 맞춰 벽이 있는지 확인할 수 있는 수치를 넣어 x, y로 nx, ny를 구해 범위를 넘지 않는 범위에서 벽이 존재하는지 체크하였다.
- 현재 위치에서 이동할 방향은 check_dir에 넣었고 각 동, 서, 북, 남의 인덱스에 맞춰 대각선, 직선방향으로 이동할 방향을 넣었다. 만약 이동할 곳이 격자 범위를 넘는 곳이라면 continue 만약 이동할 수 있다면 check_wall이라는 배열을 활용해서 해당 방향으로 이동하는데 체크해야할 벽이 존재하는지를 파악한 후, 벽이 존재하지 않는다면 이동 처리한다.
- 온도 조절 처리도 위의 check_dir을 활용하여 동, 서, 북, 남으로 이동할 때 어느 부분이 벽의 존재 위치를 파악해서 온도 조절이 되는지 안되는지 파악해주는 것이 특징이다.
2. 느낀점
- 세상 빡구현이다... 처음에 동,서,북,남, 대각선들을 체크할 때 벽의 확인 부분이 일관된줄 알고 구현했는데 알고 보니 방향에 따라 이동 위치의 벽의 확인 위치도 다 달라져서... 그냥 맞춰서 다 구현할 수 밖에 없었다 ^_^..
- 깔끔한 코드는 아니지만,,, 그래도 어느정도 코드 다이어트를 할 수 있을만큼 했다... ㅎㅎ
- 이해 안 가는 분들은,, 댓글 달아주세유,,
💻 소스코드
// BOJ - 온풍기 안녕!
// 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_23289 {
public static int r, c, k;
public static int[][] map;
public static int[][] heat;
// 동, 서, 북, 남, 오위, 오아, 왼위, 왼아
public static int[] dx = {0, 0, 0, -1 ,1, -1, 1, -1, 1};
public static int[] dy = {0, 1, -1, 0, 0, 1, 1, -1, -1};
public static int[][] check_dir = {{}, {5, 1, 6}, {7, 2, 8}, {7, 3, 5}, {8, 4, 6}};
public static int[][][][] check_wall = {{},
{{{0, 0, 0}, {-1, 0, 1}}, {{0, 0, 1}}, {{1, 0, 0}, {1, 0, 1}}},
{{{-1, -1, 1}, {0, 0, 0}}, {{0, -1, 1}}, {{1, 0, 0}, {1, -1, 1}}},
{{{0, -1, 1}, {0, -1, 0}}, {{0, 0, 0}}, {{0, 0, 1}, {0, 1, 0}}},
{{{0, -1, 1}, {1, -1 ,0}}, {{1, 0, 0}}, {{0, 0, 1}, {1, 1, 0}}}};
public static ArrayList<Node> machine;
public static ArrayList<Integer>[][] map_wall;
public static class Node {
int x;
int y;
int dir;
int heat;
public Node(int x, int y, int dir) {
this.x = x;
this.y = y;
this.dir = dir;
}
public Node(int x, int y, int dir, int heat) {
this.x = x;
this.y = y;
this.dir = dir;
this.heat = heat;
}
}
public static void main(String[] args) throws IOException {
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];
map_wall = new ArrayList[r][c];
machine = new ArrayList<>();
heat = new int[r][c];
for(int i=0;i<r;i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j=0;j<c;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
map_wall[i][j] = new ArrayList<Integer>();
if(map[i][j] >=1 && map[i][j] <=4) {
machine.add(new Node(i, j, map[i][j]));
}
}
}
int w = Integer.parseInt(br.readLine());
for(int i=0;i<w;i++) {
st = new StringTokenizer(br.readLine()," ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
map_wall[x-1][y-1].add(t);
}
int eat = 0;
while(eat <= 100) {
for(int i=0;i<machine.size();i++) {
Node node = machine.get(i);
int x = node.x + dx[node.dir];
int y = node.y + dy[node.dir];
boolean[][] visited = new boolean[r][c];
if(is_chk(x, y)) {
visited[x][y] = true;
Queue<Node> q = new LinkedList<>();
q.add(new Node(x, y, node.dir, 5));
while(!q.isEmpty()) {
Node nd = q.poll();
heat[nd.x][nd.y] += nd.heat;
outer:for(int d=0;d<3;d++) {
int dir = check_dir[nd.dir][d];
int ch_x = nd.x + dx[dir];
int ch_y = nd.y + dy[dir];
if(!is_chk(ch_x, ch_y)) continue;
if(visited[ch_x][ch_y]) continue;
for(int n=0;n<check_wall[nd.dir][d].length;n++) {
int nx = nd.x + check_wall[nd.dir][d][n][0];
int ny = nd.y + check_wall[nd.dir][d][n][1];
if(is_chk(nx, ny)) {
for(int a=0;a<map_wall[nx][ny].size();a++) {
if(map_wall[nx][ny].get(a) == check_wall[nd.dir][d][n][2]) {
continue outer;
}
}
}
}
if(nd.heat >= 2) {
visited[ch_x][ch_y] = true;
q.add(new Node(ch_x, ch_y, nd.dir, nd.heat-1));
}
}
}
}
}
int[][] heat_copy = new int[r][c];
for(int i=0;i<r;i++) {
heat_copy[i] = heat[i].clone();
}
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
if(heat[i][j] == 0) continue;
outer: for(int d=1;d<=4;d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if(!is_chk(nx, ny)) continue;
if(heat[i][j] < heat[nx][ny]) continue;
int chk_x = i + check_wall[d][1][0][0];
int chk_y = j + check_wall[d][1][0][1];
int chk_t = check_wall[d][1][0][2];
if(is_chk(chk_x, chk_y)) {
for(int a=0;a<map_wall[chk_x][chk_y].size();a++) {
if(map_wall[chk_x][chk_y].get(a) == chk_t) {
continue outer;
}
}
}
int diff = heat[i][j] - heat[nx][ny];
if(heat_copy[i][j] >= diff/4) {
heat_copy[i][j] -= diff/4;
heat_copy[nx][ny] += diff/4;
}
}
}
}
for(int i=0;i<r;i++) {
heat[i] = heat_copy[i].clone();
}
// 바깥쪽 칸의 온도 1씩 감소
for(int j=0;j<c;j++) {
if(heat[0][j] >= 1) heat[0][j]--;
if(heat[r-1][j] >= 1) heat[r-1][j]--;
}
for(int i=1;i<r-1;i++) {
if(heat[i][0] >= 1) heat[i][0]--;
if(heat[i][c-1] >= 1) heat[i][c-1]--;
}
eat++;
if(check()) {
break;
}
}
System.out.println(eat>=101?101:eat);
}
public static void print() {
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
System.out.print(heat[i][j] +" ");
}
System.out.println();
}
System.out.println();
}
public static boolean check() {
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
if(map[i][j] == 5 && (heat[i][j] < k)) return false;
}
}
return true;
}
public static boolean is_chk(int x, int y) {
if(x < 0 || x >= r || y < 0 || y >= c) return false;
return true;
}
}