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

 

 

🧫 문제 분석

 

✔️ 출처

온풍기 안녕! 플래티넘 5

 

📖 문제

 

벽 체크하는게 너무 어려웠다.

 

그냥 하드코딩해서 벽체크하면 되는데 

자꾸 다른 방법이 있을 거같아서 그것만 파다가 시간 다보냈다.

 

벽 체크의 경우 

boolean[][] 이중 배열로 

up 일때 벽,

right을 때 벽 두가지를 체크하는 방식으로 풀어나간다. 

 

3차원 배열도 생각해봤는데 

너무 복잡할거 같아서 버렸다.

 

좀 헷갈린게 여기인데

 

대각선 이동 시 벽체크에서

상대적 위치에서 

양 옆으로 이동했다가 앞으로 전진하는 식으로 생각해야한다. 

 

 

온도조절의 경우

동시 발생이기에 따로 임시배열 생성해서 처리해야한다. 

상하좌우 처리후 현재 위치를 방문처리해서 

중복 연산되지 않게 막는다. 

 

 

초콜릿이 100개를 넘어버리면 바로 중지한다.

이것때문에 시간초과도 났다. 

 

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {

    // 오 왼 위 아래
    static int[] dr = {0, 0, -1, 1};
    static int[] dc = {1, -1, 0, 0};

    static int[][] adr = {
            {-1, 0, 1},
            {-1, 0, 1},
            {-1, -1, -1},
            {1, 1, 1}
    };
    static int[][] adc = {
            {1, 1, 1},
            {-1, -1, -1},
            {-1, 0, 1},
            {-1, 0, 1}
    };

    static int[][] map;
    static boolean[][] wallUp;
    static boolean[][] wallRight;

    static int R, C, K, W, answer;
    static List<int[]> heaters = new ArrayList<>();
    static List<int[]> cond = new ArrayList<>();

    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];
        wallUp = new boolean[R][C];
        wallRight = new boolean[R][C];

        int choco = 0;

        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                int value = Integer.parseInt(st.nextToken());

                if (value == 5) {
                    cond.add(new int[]{i, j});
                } else if (value != 0) {
                    heaters.add(new int[]{i, j, value - 1});
                }
            }
        }

        W = Integer.parseInt(br.readLine());
        for (int i = 0; i < W; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int t = Integer.parseInt(st.nextToken());

            if (t==0) wallUp[r][c] = true;
            else wallRight[r][c] = true;
        }

        while (true) {
            // 1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
            for (int i = 0; i < heaters.size(); i++) {
                int[] heater = heaters.get(i);
                int dir = heater[2];

                int r = heater[0] + dr[dir];
                int c = heater[1] + dc[dir];

                // 처음 온풍기 나오는 쪽은 무조건 가능하므로 바로 계산
                bfs(r, c, dir);

            }

            // 2. 온도 조절
            // 임시 배열 사용할 것
            int[][] tmp = new int[R][C];
            boolean[][] visited = new boolean[R][C];

            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    for (int k = 0; k < 4; k++) {

                        int nr = i + dr[k];
                        int nc = j + dc[k];
                        if (nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc]) continue;

                        // 벽이 아니라면
                        if (wallCheck2(i, j, k)) {
                            int diff = Math.abs(map[i][j] - map[nr][nc]) / 4;
                            if (map[i][j] > map[nr][nc]) {
                                tmp[i][j] -= diff;
                                tmp[nr][nc] += diff;
                            } else if (map[i][j] < map[nr][nc]) {
                                tmp[i][j] += diff;
                                tmp[nr][nc] -= diff;
                            }

                            visited[i][j] = true;
                        }
                    }
                }
            }

            // 온도 실제 적용
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    map[i][j] += tmp[i][j];
                }
            }


            // 3. 온도가 1 이상인 가장 바깥쪽 칸의 온도 1씩 감소
            for (int j = 0; j < C; j++) {
                if (map[0][j] != 0) {
                    map[0][j]--;
                }

                if (map[R - 1][j] != 0) {
                    map[R - 1][j]--;
                }
            }

            for (int i = 1; i < R - 1; i++) {
                if (map[i][0] != 0) {
                    map[i][0]--;
                }
                if (map[i][C - 1] != 0) {
                    map[i][C-1]--;
                }
            }

            // 4. 초콜릿 1개 먹기
            choco++;

            if (choco > 100) {
                System.out.println(101);
                return;
            }

            int cnt = 0;
            // 5. 조사하는 모든 칸의 온도가 K이상이면 중단, 아니면 1번부터 다시
            for (int i = 0; i < cond.size(); i++) {
                int[] pos = cond.get(i);
                int r = pos[0];
                int c = pos[1];

                if (map[r][c] >= K) {
                    cnt++;
                }
            }

            // (초콜릿 개수 > 100) ? 101을 출력
            if (cnt == cond.size()) {
                System.out.println(choco);
                return;
            }

        }

    }

    private static void bfs(int startR, int startC, int dir) {
        boolean[][] visited = new boolean[R][C];
        Queue<int[]> q = new LinkedList<>();
        map[startR][startC] += 5;
        visited[startR][startC] = true;
        q.add(new int[]{startR, startC, 5});

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1], power = cur[2];

            if (power == 1) continue;

            for (int i = 0; i < 3; i++) {
                int nr = r + adr[dir][i];
                int nc = c + adc[dir][i];

                if (nr < 0 || nr >= R
                        || nc < 0 || nc >= C) {
                    continue;
                }

                if (!visited[nr][nc] && wallCheck(r, c, nr, nc, dir)) {
                    visited[nr][nc] = true;
                    map[nr][nc] += power - 1;
                    q.add(new int[]{nr, nc, power - 1});
                }

            }
        }
    }
    private static boolean wallCheck2(int r, int c, int dir) {
        // 오른
        if (dir == 0) {
            return !wallRight[r][c];
            // 왼
        } else if (dir == 1) {
            return !wallRight[r][c - 1];
            // 위
        } else if (dir == 2) {
            return !wallUp[r][c];
            // 아래
        } else {
            return !wallUp[r + 1][c];
        }
    }

    private static boolean wallCheck(int r, int c, int nr, int nc, int dir) {
        // 오른쪽
        if (dir == 0) {
            if (nr == r - 1 && nc == c + 1) {
                return !wallRight[r - 1][c] && !wallUp[r][c];
            } else if (nr == r + 1 && nc == c + 1) {
                return !wallUp[nr][c] && !wallRight[nr][c];
            }else if (nc == c + 1) {
                return !wallRight[r][c];
            }

            // 왼쪽
        } else if (dir == 1) {
            if (nr == r - 1 && nc == c - 1) {
                return !wallUp[r][c] && !wallRight[nr][nc];
            } else if (nr == r + 1 && nc == c - 1) {
                return !wallUp[r + 1][c] && !wallRight[nr][nc];
            } else if (nc == c - 1) {
                return !wallRight[r][c - 1];
            }
            // 위
        } else if (dir == 2) {
            if (nr == r - 1 && nc == c - 1) {
                return !wallRight[r][c - 1] && !wallUp[r][c - 1];
            } else if (nr == r - 1 && nc == c + 1) {
                return !wallRight[r][c] && !wallUp[r][c + 1];
            } else if (nr == r - 1) {
                return !wallUp[r][c];
            }
            // 아래
        } else {
            if (nr == r + 1 && nc == c - 1) {
                return !wallRight[r][c - 1] && !wallUp[nr][nc];
            } else if (nr == r + 1 && nc == c + 1) {
                return !wallRight[r][c] && !wallUp[nr][nc];
            } else if (nr == r + 1) {
                return !wallUp[nr][c];
            }
        }

        return false;
    }


}

 

 

 

❗ 오답노트 / 필요한 지식

1.  문제를 푸는게 먼저지 최적화화면서 푸는게 먼저가 아니다. 먼저 풀고 나중에 리팩토링하고 최적화하면된다.
2. 조건을 잘 확인하자. 초콜릿이 100개를 넘으면 굳이 쓸데없는 연산을 할 필요가 없다.
3. 배열사이 벽 체크하는 법을 배웠다. 잘 기억하자.