백준 23289번: 온풍기 안녕! (Java)

https://www.acmicpc.net/problem/23289

23289번: 온풍기 안녕!

 

 

 

 

 

 

 

 

---

 

풀이

한 번의 과정은 5단계로 나뉩니다.

 

1) 온풍기에서 바람이 나감

 - 가장 어려운 부분이었습니다.

 - 각 칸마다 바람이 퍼질 수 있는지 bfs/dfs로 판정하면 됩니다.

 - 저는 가로벽을 해당칸에 1, 세로벽을 해당칸에 2로 나타내어 비트처리해줬습니다.

 - 4방향을 다 한꺼번에 처리할 수도 있겠으나, 생각이 잘 안나서 저는 하드코딩 했습니다.

  - 그리고 여기서 오타나서 고생했습니다. 이게 방향처리 한번에 하려고 하면 힘들고, 또 막상 하드코딩하면 오타때문에 실수나고..어떻게 해야할지 잘 모르겠네요.

2) 열이 퍼짐

 - 쓰여진 대로 구현하면 됩니다. 새로운 배열 만들어서 변화를 기록해두세요. 

3) 모서리 식음

 - 꼭지점을 2번 세지 않도록 for문을 모서리별로 나누어서 처리해줍니다.

4) 초콜릿을 먹음

 - 왜 초콜릿일까요?

5) 검사

 - 하면 됩니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] dr = { 0, 0, 0, -1, 1 };
    static int[] dc = { 0, 1, -1, 0, 0 };
    static int R, C, K;
    static int[][] wall, map;
    static boolean[][] visited;
    static List<int[]> heaters = new ArrayList<>();
    static List<int[]> checks = 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+1][C+1];
        wall = new int[R+1][C+1];
        
        for (int i = 1; i <= R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= C; j++) {
                int x = Integer.parseInt(st.nextToken());
                if (x == 0) continue;
                if (x < 5) {
                    heaters.add(new int[] {i, j, x});
                }
                else {
                    checks.add(new int[] {i, j});
                }
            }
        }
        
        int W = Integer.parseInt(br.readLine());
        for (int i = 0; i < W; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            wall[r][c] += (t+1);
        }        
        
        int choco = 0;
        while (true) {
            heat();
            spread();
            coolBorder();
            choco++;
            if (choco > 100) break;
            if (check()) break;
        }
        System.out.println(choco);
    }
    
    static void heat() {
        for (int[] h: heaters) {
            visited = new boolean[R+1][C+1]; // 되려나...
            int r = h[0], c = h[1], dir = h[2];
            if (isIn(r + dr[dir], c + dc[dir])) oneHeater(r + dr[dir], c + dc[dir], dir, 5);
        }
    }
    
    static void oneHeater(int r, int c, int dir, int temp) {
        if (temp == 0) return;
        visited[r][c] = true;
        map[r][c] += temp;
        
        if (dir == 1) {
            try { 
                int nr = r-1, nc = c+1;
                if (isIn(nr, nc) && !visited[nr][nc]) {
                    if (!isWall(r, c, 0) && !isWall(r-1, c, 1)) {
                        oneHeater(nr, nc, dir, temp-1);
                    }
                }
                nr++;
                if (isIn(nr, nc) && !visited[nr][nc]) {
                    if (!isWall(r, c, 1)) {
                        oneHeater(nr, nc, dir, temp-1);
                    }
                }
                nr++;
                if (isIn(nr, nc) && !visited[nr][nc]) {
                    if (!isWall(r+1, c, 0) && !isWall(r+1, c, 1)) {
                        oneHeater(nr, nc, dir, temp-1);
                    }
                }
            } catch (Exception e) {
                throw new ArithmeticException();
            }
        }
        else if (dir == 2) {
            int nr = r+1, nc = c-1;
            if (isIn(nr, nc) && !visited[nr][nc]) {
                if (!isWall(r+1, c, 0) && !isWall(r+1, c-1, 1)) {
                    oneHeater(nr, nc, dir, temp-1);
                }
            }
            nr--;
            if (isIn(nr, nc) && !visited[nr][nc]) {
                if (!isWall(r, c-1, 1)) {
                    oneHeater(nr, nc, dir, temp-1);
                }
            }
            nr--;
            if (isIn(nr, nc) && !visited[nr][nc]) {
                if (!isWall(r, c, 0) && !isWall(r-1, c-1, 1)) {
                    oneHeater(nr, nc, dir, temp-1);
                }
            }
        }
        else if (dir == 3) {
            int nr = r-1, nc = c-1;
            if (isIn(nr, nc) && !visited[nr][nc]) {
                if (!isWall(r, c-1, 0) && !isWall(r, c-1, 1)) {
                    oneHeater(nr, nc, dir, temp-1);
                }
            }
            nc++;
            if (isIn(nr, nc) && !visited[nr][nc]) {
                if (!isWall(r, c, 0)) {
                    oneHeater(nr, nc, dir, temp-1);
                }
            }
            nc++;
            if (isIn(nr, nc) && !visited[nr][nc]) {
                if (!isWall(r, c, 1) && !isWall(r, c+1, 0)) {
                    oneHeater(nr, nc, dir, temp-1);
                }
            }
        }
        else {
            int nr = r+1, nc = c-1;
            if (isIn(nr, nc) && !visited[nr][nc]) {
                if (!isWall(r, c-1, 1) && !isWall(r+1, c-1, 0)) {
                    oneHeater(nr, nc, dir, temp-1);
                }
            }
            nc++;
            if (isIn(nr, nc) && !visited[nr][nc]) {
                if (!isWall(r+1, c, 0)) {
                    oneHeater(nr, nc, dir, temp-1);
                }
            }
            nc++;
            if (isIn(nr, nc) && !visited[nr][nc]) {
                if (!isWall(r, c, 1) && !isWall(r+1, c+1, 0)) {
                    oneHeater(nr, nc, dir, temp-1);
                }
            }
        }
    }
    
    static void spread() {
        int[][] tempMap = new int[R+1][C+1];
        for (int r = 1; r <= R; r++) {
            for (int c = 1; c <= C; c++) {
                int nr = r + dr[1], nc = c + dc[1];
                if (isIn(nr, nc) && map[r][c] > map[nr][nc] && !isWall(r, c, 1)) {
                    int diff = (map[r][c] - map[nr][nc]) / 4;
                    tempMap[nr][nc] += diff;
                    tempMap[r][c] -= diff;
                }
                nr = r + dr[2];
                nc = c + dc[2];
                if (isIn(nr, nc) && map[r][c] > map[nr][nc] && !isWall(r, c-1, 1)) {
                    int diff = (map[r][c] - map[nr][nc]) / 4;
                    tempMap[nr][nc] += diff;
                    tempMap[r][c] -= diff;
                }
                nr = r + dr[3];
                nc = c + dc[3];
                if (isIn(nr, nc) && map[r][c] > map[nr][nc] && !isWall(r, c, 0)) {
                    int diff = (map[r][c] - map[nr][nc]) / 4;
                    tempMap[nr][nc] += diff;
                    tempMap[r][c] -= diff;
                }
                nr = r + dr[4];
                nc = c + dc[4];
                if (isIn(nr, nc) && map[r][c] > map[nr][nc] && !isWall(r+1, c, 0)) {
                    int diff = (map[r][c] - map[nr][nc]) / 4;
                    tempMap[nr][nc] += diff;
                    tempMap[r][c] -= diff;
                }
            }
        }
        
        for (int r = 1; r <= R; r++) {
            for (int c = 1; c <= C; c++) {
                map[r][c] += tempMap[r][c];
            }
        }
    }
    
    static void coolBorder() {
        for (int c = 1; c <= C; c++) {
            if (map[1][c] > 0) map[1][c]--;
        }
        for (int r = 2; r <= R; r++) {
            if (map[r][C] > 0) map[r][C]--;
        }
        for (int c = C-1; c >= 1; c--) {
            if (map[R][c] > 0) map[R][c]--;
        }
        for (int r = 2; r < R; r++) {
            if (map[r][1] > 0) map[r][1]--;
        }
    }
    
    static boolean check() {
        for (int[] c: checks) {
            if (map[c[0]][c[1]] < K) return false;
        }
        return true;
    }
    
    static boolean isIn(int r, int c) {
        return !(r <= 0 || r > R || c <= 0 || c > C);
    }
    
    static boolean isWall(int r, int c, int t) {
        return (wall[r][c] & (t+1)) > 0;
    }
}

 

 

 

P.S.

진짜 죽을 맛의 디버깅이었습니다...