[백준/23289/Java] 온풍기 안녕!_간단 해설

Jake·2022년 3월 5일
Problem Solving
0

PS

목록 보기
6/14

1. 문제 이해

삼성의 전형적인 복잡한 구현 문제입니다.

2. 문제 해석

스킵하겠습니다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int r, c, k, w;
    static int chocolate;
    static Room[][] board;
    static ArrayList<Heater> heaters;
    static ArrayList<Room> testRooms;
    static final int up = 0, right = 1, down = 2, left = 3;
    static int[] dx = {-1, 0, 1, 0}; //[위, 오, 아래, 왼]
    static int[] dy = {0, 1, 0, -1};


    public static void main(String[] args) throws IOException {
        init();

        while(chocolate <= 100) {
            //System.out.println("activateHeater======================");
            activateHeater(); // step 1
            //print();

            //System.out.println("adjustHeat======================");
            adjustHeat(); // step 2
            //print();

            //System.out.println("decreaseHeat======================");
            decreaseHeat(); // step 3
            //print();
            
            chocolate++; // step 4
            if(testPass()) { // step 5
                System.out.println(chocolate);
                return;
            }
        }

        System.out.println(101);
    }

    public static void activateHeater() {
        for (Heater heater : heaters) {
            heater.wind();
        }
    }


    public static void adjustHeat() {
        int[][] saveHeat = new int[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                Room room = board[i][j];
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if(valid(nx, ny) && !room.isWalled[dir]) {
                        Room nextRoom = board[nx][ny];
                        int adjust = (room.hot - nextRoom.hot)/4;
                        if(adjust > 0) {
                            saveHeat[i][j] -= adjust;
                            saveHeat[nx][ny] += adjust;
                        }
                    }
                }
            }
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                board[i][j].hot += saveHeat[i][j];
            }
        }
    }


    public static void decreaseHeat() {
        for (int j = 0; j < c-1; j++) {
            if(board[0][j].hot > 0) board[0][j].hot--;
        }
        for (int i = 0; i < r-1; i++) {
            if(board[i][c-1].hot > 0) board[i][c-1].hot--;
        }
        for (int j = c-1; j >= 1; j--) {
            if(board[r-1][j].hot > 0) board[r-1][j].hot--;
        }
        for (int i = r-1; i >= 1; i--) {
            if(board[i][0].hot > 0) board[i][0].hot--;
        }
    }


    public static boolean testPass() {
        for (Room room : testRooms) {
            if(room.hot >= k) continue;
            else return false;
        }
        return true;
    }


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = pi(st.nextToken());
        c = pi(st.nextToken());
        k = pi(st.nextToken());

        chocolate = 0;
        board = new Room[r][c];
        heaters = new ArrayList<>();
        testRooms = new ArrayList<>();

        for(int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                board[i][j] = new Room();
                int num = pi(st.nextToken());
                if (num != 0) {
                    if (num < 5) {
                        int dir = getDir(num);
                        heaters.add(new Heater(i, j, dir));
                    } else {
                        testRooms.add(board[i][j]);
                    }
                }
            }
        }

        w = pi(br.readLine());
        for (int i = 0; i < w; i++) {
            st = new StringTokenizer(br.readLine());
            setWall(pi(st.nextToken())-1, pi(st.nextToken())-1, pi(st.nextToken()));
        }
    }

    public static int getDir(int num) {
        if(num == 1) return right;
        else if(num == 2) return left;
        else if(num == 3) return up;
        else return down;
    }

    public static void setWall(int x, int y, int t) {
        if(t == 0) {
            board[x-1][y].isWalled[down] = true;
            board[x][y].isWalled[up] = true;
        } else {
            board[x][y].isWalled[right] = true;
            board[x][y+1].isWalled[left] = true;
        }
    }

    public static int pi(String str) {
        return Integer.parseInt(str);
    }

    public static boolean valid(int x, int y) {
        if(x < 0 || x >= r || y < 0 || y >= c) return false;
        else return true;
    }

    public static void print() {
        for(int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                System.out.print(board[i][j].hot + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static class Room{
        int hot; //temp는 임시같고, temperature는 너무 길고..
        boolean[] isWalled;

        public Room() {
            hot = 0;
            isWalled = new boolean[4]; // [위, 오, 아래, 왼]
        }
    }

    static class Heater{
        int x, y;
        int dir;

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

        public void wind() {
            int forward = dir;
            int forLeft = (dir+3)%4;
            int forRight = (dir+1)%4;

            boolean[][] visited = new boolean[r][c];
            visited[x + dx[dir]][y + dy[dir]] = true;
            Queue<Node> queue = new LinkedList<>();
            queue.add(new Node(x + dx[dir], y + dy[dir], 5));

            while (!queue.isEmpty()) {
                Node node = queue.poll();
                if(node.remain == 0) continue;

                board[node.x][node.y].hot += node.remain;

                //직진 방향 체크
                int nx = node.x + dx[forward];
                int ny = node.y + dy[forward];
                if(valid(nx, ny) && !visited[nx][ny] && !board[node.x][node.y].isWalled[forward]) {
                    visited[nx][ny] = true;
                    queue.add(new Node(nx, ny, node.remain - 1));
                }

                int nx2, ny2;//nx, nx2에 대한 설명은 아래 코드 해설의 그림 참조
                nx = node.x + dx[forLeft]; nx2 = nx + dx[forward];
                ny = node.y + dy[forLeft]; ny2 = ny + dy[forward];
                if(valid(nx, ny) && valid(nx2, ny2) && !visited[nx2][ny2]) {//가려는 좌표가 모두 유효한 좌표인지 체크 + 이미 바람이 전파된 곳인지 체크
                    if(!board[node.x][node.y].isWalled[forLeft] && !board[nx][ny].isWalled[forward]) {//벽 쳐져있는지 여부 체크
                        visited[nx2][ny2] = true;
                        queue.add(new Node(nx2, ny2, node.remain - 1));
                    }
                }

                nx = node.x + dx[forRight]; nx2 = nx + dx[forward];
                ny = node.y + dy[forRight]; ny2 = ny + dy[forward];
                if(valid(nx, ny) && valid(nx2, ny2) && !visited[nx2][ny2]) {
                    if(!board[node.x][node.y].isWalled[forRight] && !board[nx][ny].isWalled[forward]) {
                        visited[nx2][ny2] = true;
                        queue.add(new Node(nx2, ny2, node.remain - 1));
                    }
                }
            }
        }
    }

    static class Node {
        int x, y, remain;

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

4. 코드 해설

  • Heater, Room 클래스를 구현해서 사용했고, Room을 2차원 배열 형태로 관리하면서 loop를 돌렸습니다

  • Heater.wind()에 대한 설명은 다음과 같습니다

    1. 바람 방향과 바람 방향의 왼쪽, 오른쪽에 대한 방향을 구합니다 (각 forward, forLeft, forRight)
    2. 큐에서 node 하나를 poll 합니다
    3. 직진 방향으로 나아갈 수 있는지 체크하고, 가능하다면 해당 좌표를 큐에 넣어줍니다
    4. 왼쪽, 오른쪽 방향도 문제의 요구사항에 맞춰 체크합니다.

5. 각 예제의 단계별 출력

예제 1 ~ 3번의 각 단계별 출력입니다.
(예제 4부터는 출력이 너무 많아져서 여기서는 생략합니다. 코드의 main에서 주석처리된 부분을 해제하고 실행하시면 아래와 같이 출력 얻으실 수 있습니다)

//예제 1
activateHeater======================
0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 
0 2 2 2 7 2 2 2 
0 0 3 4 7 4 3 0 
0 0 3 4 7 4 3 0 
0 2 2 2 7 2 2 2 
1 1 1 1 1 1 1 1 

adjustHeat======================
0 0 0 0 0 0 0 0 
1 1 1 1 2 1 1 1 
0 2 2 3 4 3 2 2 
0 0 3 4 7 4 3 0 
0 0 3 4 7 4 3 0 
0 2 2 3 4 3 2 2 
1 1 1 1 2 1 1 1 

decreaseHeat======================
0 0 0 0 0 0 0 0 
0 1 1 1 2 1 1 0 
0 2 2 3 4 3 2 1 
0 0 3 4 7 4 3 0 
0 0 3 4 7 4 3 0 
0 2 2 3 4 3 2 1 
0 0 0 0 1 0 0 0 
//예제 2

//loop1
activateHeater======================
0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 
0 2 2 2 7 2 2 2 
0 0 3 4 7 4 3 0 
0 0 3 4 7 4 3 0 
0 2 2 2 7 2 2 2 
1 1 1 1 1 1 1 1 

adjustHeat======================
0 0 0 0 0 0 0 0 
1 1 1 1 2 1 1 1 
0 2 2 3 4 3 2 2 
0 0 3 4 7 4 3 0 
0 0 3 4 7 4 3 0 
0 2 2 3 4 3 2 2 
1 1 1 1 2 1 1 1 

decreaseHeat======================
0 0 0 0 0 0 0 0 
0 1 1 1 2 1 1 0 
0 2 2 3 4 3 2 1 
0 0 3 4 7 4 3 0 
0 0 3 4 7 4 3 0 
0 2 2 3 4 3 2 1 
0 0 0 0 1 0 0 0 

//loop2
activateHeater======================
0 0 0 0 0 0 0 0 
1 2 2 2 3 2 2 1 
0 4 4 5 11 5 4 3 
0 0 6 8 14 8 6 0 
0 0 6 8 14 8 6 0 
0 4 4 5 11 5 4 3 
1 1 1 1 2 1 1 1 

adjustHeat======================
0 0 0 0 0 0 0 0 
1 2 2 2 5 2 2 1 
1 2 4 6 7 6 4 3 
0 2 5 8 13 9 5 1 
0 2 5 9 12 9 5 1 
1 2 4 5 7 5 4 3 
1 1 1 2 4 2 1 1 

decreaseHeat======================
0 0 0 0 0 0 0 0 
0 2 2 2 5 2 2 0 
0 2 4 6 7 6 4 2 
0 2 5 8 13 9 5 0 
0 2 5 9 12 9 5 0 
0 2 4 5 7 5 4 2 
0 0 0 1 3 1 0 0 
//예제 3
//loop1
activateHeater======================
0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 
0 2 2 2 7 2 2 2 
0 0 3 4 7 4 3 0 
0 0 3 4 7 4 3 0 
0 2 2 2 7 2 2 2 
1 1 1 1 1 1 1 1 

adjustHeat======================
0 0 0 0 0 0 0 0 
1 1 1 1 2 1 1 1 
0 2 2 3 4 3 2 2 
0 0 3 4 7 4 3 0 
0 0 3 4 7 4 3 0 
0 2 2 3 4 3 2 2 
1 1 1 1 2 1 1 1 

decreaseHeat======================
0 0 0 0 0 0 0 0 
0 1 1 1 2 1 1 0 
0 2 2 3 4 3 2 1 
0 0 3 4 7 4 3 0 
0 0 3 4 7 4 3 0 
0 2 2 3 4 3 2 1 
0 0 0 0 1 0 0 0 

//loop2
activateHeater======================
0 0 0 0 0 0 0 0 
1 2 2 2 3 2 2 1 
0 4 4 5 11 5 4 3 
0 0 6 8 14 8 6 0 
0 0 6 8 14 8 6 0 
0 4 4 5 11 5 4 3 
1 1 1 1 2 1 1 1 

adjustHeat======================
0 0 0 0 0 0 0 0 
1 2 2 2 5 2 2 1 
1 2 4 6 7 6 4 3 
0 2 5 8 13 9 5 1 
0 2 5 9 12 9 5 1 
1 2 4 5 7 5 4 3 
1 1 1 2 4 2 1 1 

decreaseHeat======================
0 0 0 0 0 0 0 0 
0 2 2 2 5 2 2 0 
0 2 4 6 7 6 4 2 
0 2 5 8 13 9 5 0 
0 2 5 9 12 9 5 0 
0 2 4 5 7 5 4 2 
0 0 0 1 3 1 0 0 

//loop3
activateHeater======================
0 0 0 0 0 0 0 0 
1 3 3 3 6 3 3 1 
0 4 6 8 14 8 6 4 
0 2 8 12 20 13 8 0 
0 2 8 13 19 13 8 0 
0 4 6 7 14 7 6 4 
1 1 1 2 4 2 1 1 

adjustHeat======================
0 0 0 0 1 0 0 0 
1 3 3 4 7 4 3 1 
1 3 6 9 11 9 6 3 
0 3 8 10 18 12 7 3 
0 3 8 12 16 12 7 3 
1 3 5 8 11 8 5 3 
1 1 2 3 6 3 2 1 

decreaseHeat======================
0 0 0 0 0 0 0 0 
0 3 3 4 7 4 3 0 
0 3 6 9 11 9 6 2 
0 3 8 10 18 12 7 2 
0 3 8 12 16 12 7 2 
0 3 5 8 11 8 5 2 
0 0 1 2 5 2 1 0

6. 리팩토링

  • Heater.wind() 함수에서 forward, forLeft, forRight의 변수명이 명확하지 않은 것 같다는 느낌이 든다. 차라리 windDirection, windDirectionLeft, windDirectionRight처럼 조금 길어지더라도 명확한 변수명을 사용하면 좀 더 읽기 쉬운 코드가 되지 않을까 싶다.

  • forLeft, forRight를 구하는 방식이 나에게는 너무 익숙한 방식이나, 함수로 빼내서 getLeft(int forward) 같이 만들었으면 더 가독성 좋은 코드가 됐을 것 같다.

  • (nx, ny), (nx2, ny2)를 사용하는 방식이 별로다. 게다가 wind 함수도 너무 길다. forward를 체크하는 함수, 각 side를 체크하는 함수를 다 만들어서 빼내줘야 했다.

profile
Jake
Java/Spring Back-End Developer
이전 포스트

[백준/23288/Java] 주사위 굴리기 2_초간단 설명

다음 포스트

[백준/23290/Java] 마법사 상어와 복제_안간단 풀이

0개의 댓글