[백준/골드1] 23289. 온풍기 안녕!

문제

---

• 너무 길어서 링크 참조

23289번: 온풍기 안녕!

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
2. 온도가 조절됨
3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
4. 초콜릿을 하나 먹는다.
5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.

풀이

---

접근

• 문제는 누가봐도 빡빡한 구현이다....!
• 1번부터 차근차근 해보기로 했다.
• 2번 단계는 다른 문제에서 비슷한 걸 풀어봐서 1번을 구현하기가 가장 힘들었다.
• 문제에서는 1~R, 1~C 로 썼지만 나는 0~R-1 1~C-1로 바꿔서 나에게 익숙한대로 풀기로 했다.

구현

벽

• 벽도 입력을 받을 때 값을 조절 해 준다.
  • 벽은 3차원 boolean 배열 walls 라고 선언한다. 그 중 1차원에는 가로 좌표, 2차원에는 세로 좌표, 3차원에는 벽의 종류(0이면 가로벽 1이면 세로벽)으로 두고 풀었다.
  • (x,y) 와 (x+1,y) 사이에 가로 벽이 있으면 walls(x,y,0) = true

체크할 곳과 온풍기 위치

• 체크할 곳은 Loc이라는 위치를 저장하는 클래스를 만든다. ArrayList로 checkList를 만든다.
• 온풍기는 Heater라는 클래스를 만들어 저장한다. ArrayList에 Heater들을 저장해 두고 썼다.

1단계 구현

• 이 부분이 가장 어려웠다.
• 나는 규칙을 못찾겠어서 방향 별로 하드코딩을 했다. + 재귀함수

• DFS로 더해줄 온도를 5부터 1씩 줄여가면서 재귀함수에 들어가도록 했고, 0이되면 끝난다.
• 주의해야 할 점은 더해줄 온도는 누적되면 안된다.
  • 그 칸에 바람이 갈 수 있는지 못가는 지를 체크한 뒤 한 번만 더해주고 재귀함수를 실행해야 한다.

2단계 구현

• 이 부분은 예전에 푼 어항 정리 라는 문제에서 비슷한 방식으로 풀었기에 그 때 설명을 복사해 왔다.
  • dx, dy 배열을 이용해서 모든 위치에서 모든 방향을 확인하면서 차이가 얼마나 나는지 확인한다.
  • 이 때 주의할 점은 계산을 두번 하지 않도록 해야 한다.
  • 내가 보고있는 위치만 생각해서 계산해야 한다. 예를 들어 아래 그림에서 4,1을 기준 위치라고 하면 +1 부분만 계산하는 것이다. 그래야지 모든 위치를 확인할 때 중복해서 계산되지 않는다.

3단계 구현

• 계산량을 조금이라도 줄이기 위해서 모든 테두리를 돌면서 0이 아니면 1씩 빼주는 식으로 진행했다.

4, 5단계는 생략하겠다.

깨달은 점

• 1단계 구현에서 비슷한 코드를 복붙해서 쓰느라 범위 체크 실수나 제대로 수정하지 못한 실수가 생겼다. 이부분을 조심해야 겠다.
• 1단계 구현에서 조건문을 if문에 안쓰고 else쪽에 썼는데, 이 부분이 코드를 더럽고 헷갈리게 만들었다. 반성함
  • 바른 방식

  if 벽이 둘 다 없으면
  	바람이 간다.
  

  • 내가 짠 더러운 방식

  if 벽이 하나라도 있으면
  	아무행동 x
  else
  	바람이 간다.
  

 

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

//[골드1] 온풍기 안녕!
public class baekjoon_23289 {
    //1. 모든 온풍기에서 바람 나옴
    // 2. 온도가 조절됨
    // 3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
    // 4. 초콜릿 하나 먹음
    // 5. 모든 칸의 온도가 K이상이 되었는지 검사, 모든칸의 온도가 K이상이면 테스트 중단. 아니면 1부터 다시 시작
    static int R, C, K;
    static int[][] map;
    static ArrayList<Heater> heaters;
    static ArrayList<Loc> checkList;
    static boolean[][][] walls;
    static int[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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]; // 온도를 저장할 곳
        heaters = new ArrayList<>();
        checkList = new ArrayList<>();
        walls = new boolean[R][C][2]; // 0이면 가로 벽 , 1이면 세로 벽

        int choco = 0;

        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                int d = Integer.parseInt(st.nextToken());
                if (d == 0) continue;
                else if (d == 5) checkList.add(new Loc(i, j));
                else heaters.add(new Heater(i, j, d));
            }
        }

        int W = Integer.parseInt(br.readLine()); // 벽의 개수
        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 w = Integer.parseInt(st.nextToken());

            if (w == 0) { // 가로 벽
                walls[x - 1][y][w] = true;
            } else { // 세로 벽
                walls[x][y][w] = true;
            }
        }

        while (true) {
            for (int k = 0; k < heaters.size(); k++) {
                Heater heater = heaters.get(k);
                int x = heater.x;
                int y = heater.y;
                int d = heater.d;
                visited = new int[R][C];
                switch (d) {
                    case 1:
                        if (y + 1 < C) {
                            visited[x][y + 1] = 5;
                            windAround(x, y + 1, d, 4);
                        }
                        break;
                    case 2:
                        if (y - 1 >= 0) {
                            visited[x][y - 1] += 5;
                            windAround(x, y - 1, d, 4);
                        }
                        break;
                    case 3:
                        if (x - 1 >= 0) {
                            visited[x - 1][y] += 5;
                            windAround(x - 1, y, d, 4);
                        }
                        break;
                    case 4:
                        if (x + 1 < R) {
                            visited[x + 1][y] += 5;
                            windAround(x + 1, y, d, 4);
                        }
                        break;
                    default:
                        break;
                }
                for (int i = 0; i < R; i++) {
                    for (int j = 0; j < C; j++) {
                        map[i][j] += visited[i][j];
                    }
                }
            }

//            for (int i = 0; i < R; i++) {
//                for (int j = 0; j < C; j++) {
//                    System.out.print(map[i][j] + " ");
//                }
//                System.out.println();
//            }

            // 온도 조절
            int[][] temp = new int[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    for (int d = 0; d < 4; d++) {
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                        if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;

                        switch (d) {
                            case 0: // 상
                                if (walls[nx][ny][0]) break;
                                temp[i][j] += (-map[i][j] + map[nx][ny]) / 4;
                                break;
                            case 1: // 하
                                if (walls[i][j][0]) break;
                                temp[i][j] += (-map[i][j] + map[nx][ny]) / 4;
                                break;
                            case 2: // 좌
                                if (walls[nx][ny][1]) break;
                                temp[i][j] += (-map[i][j] + map[nx][ny]) / 4;
                                break;
                            case 3: // 우
                                if (walls[i][j][1]) break;
                                temp[i][j] += (-map[i][j] + map[nx][ny]) / 4;
                                break;
                        }
                    }
                }
            }

            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    map[i][j] += temp[i][j];
                }
            }

//            System.out.println("온도 조절 후");
//            for (int i = 0; i < R; i++) {
//                for (int j = 0; j < C; j++) {
//                    System.out.print(map[i][j] + " ");
//                }
//                System.out.println();
//            }


            // 온도감소
            for (int j = 0; j <= C - 2; j++) {
                if (map[0][j] != 0) map[0][j]--;
            }
            for (int j = C - 1; j >= 1; j--) {
                if (map[R - 1][j] != 0) map[R - 1][j]--;
            }
            for (int i = 0; i <= R - 2; i++) {
                if (map[i][C - 1] != 0) map[i][C - 1]--;
            }
            for (int i = R - 1; i >= 1; i--) {
                if (map[i][0] != 0) map[i][0]--;
            }

//            System.out.println("온도 감소 후");
//            for (int i = 0; i < R; i++) {
//                for (int j = 0; j < C; j++) {
//                    System.out.print(map[i][j] + " ");
//                }
//                System.out.println();
//            }

            choco++;

            boolean flag = true;
            for (Loc check : checkList) {
                if (map[check.x][check.y] < K) {
                    flag = false;
                    break;
                }
            }

            if (flag) break;

            if (choco == 100){
                choco ++;
                break;
            }
        }

        System.out.print(choco);

    }

    private static void windAround(int x, int y, int d, int step) {
        if (step == 0) return;

        boolean[][] v = new boolean[R][C];
        switch (d) {
            case 1:
                if (y + 1 < C) {
                    if (x - 1 < 0) {
                    } else if (!walls[x - 1][y][1] && !walls[x - 1][y][0]) {
                        visited[x - 1][y + 1] = step;
                        v[x - 1][y + 1] = true;
                    }

                    if (!walls[x][y][1]) {
                        visited[x][y + 1] = step;
                        v[x][y + 1] = true;
                    }

                    if (x + 1 >= R) {
                    } else if (!walls[x][y][0] && !walls[x + 1][y][1]) {
                        visited[x + 1][y + 1] = step;
                        v[x + 1][y + 1] = true;
                    }

                    for (int i = -1; i <= 1; i++) {
                        if (x + i < 0 || x + i >= R || !v[x + i][y + 1]) continue;
                        windAround(x + i, y + 1, d, step - 1);
                    }
                }
                break;
            case 2:
                if (y - 1 >= 0) {
                    if (x - 1 < 0) {
                    } else if (!walls[x - 1][y - 1][1] && !walls[x - 1][y][0]) {
                        visited[x - 1][y - 1] = step;
                        v[x - 1][y - 1] = true;
                    }

                    if (!walls[x][y - 1][1]) {
                        visited[x][y - 1] = step;
                        v[x][y - 1] = true;
                    }

                    if (x + 1 >= R) {
                    } else if (!walls[x + 1][y - 1][1] && !walls[x][y][0]) {
                        visited[x + 1][y - 1] = step;
                        v[x + 1][y - 1] = true;
                    }

                    for (int i = -1; i <= 1; i++) {
                        if (x + i < 0 || x + i >= R || !v[x + i][y - 1]) continue;
                        windAround(x + i, y - 1, d, step - 1);
                    }
                }
                break;
            case 3:
                if (x - 1 >= 0) {
                    if (y - 1 < 0) {
                    } else if (!walls[x - 1][y - 1][0] && !walls[x][y - 1][1]) {
                        visited[x - 1][y - 1] = step;
                        v[x - 1][y - 1] = true;
                    }

                    if (!walls[x - 1][y][0]) {
                        visited[x - 1][y] = step;
                        v[x - 1][y] = true;
                    }

                    if (y + 1 >= C) {
                    } else if (!walls[x - 1][y + 1][0] && !walls[x][y][1]) {
                        visited[x - 1][y + 1] = step;
                        v[x - 1][y + 1] = true;
                    }

                    for (int i = -1; i <= 1; i++) {
                        if (y + i < 0 || y + i >= C || !v[x - 1][y + i]) continue;
                        windAround(x - 1, y + i, d, step - 1);
                    }
                }
                break;
            case 4:
                if (x + 1 < R) {
                    if (y - 1 < 0) {
                    } else if (!walls[x][y - 1][1] && !walls[x][y - 1][0]) {
                        visited[x + 1][y - 1] = step;
                        v[x + 1][y - 1] = true;
                    }

                    if (!walls[x][y][0]) {
                        visited[x + 1][y] = step;
                        v[x + 1][y] = true;
                    }

                    if (y + 1 >= C) {
                    } else if (!walls[x][y][1] && !walls[x][y + 1][0]) {
                        visited[x + 1][y + 1] = step;
                        v[x + 1][y + 1] = true;
                    }

                    for (int i = -1; i <= 1; i++) {
                        if (y + i < 0 || y + i >= C || !v[x + 1][y + i]) continue;
                        windAround(x + 1, y + i, d, step - 1);
                    }
                }
                break;
            default:
                break;
        }

    }


    private static class Heater {
        int x;
        int y;
        int d;

        public Heater(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    private static class Loc {
        int x;
        int y;

        public Loc(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}