문제 탐색하기

입력 자료 정리

1. r과 c는 각각 전체 좌표의 세로, 가로길이다
2. k는 검증에 사용할 기준 온도다
3. 이어서 들어오는 값은 각 좌표의 상태를 의미한다
   0은 빈칸, 1,2,3,4는 온풍기가 존재하며 우,좌,상,하 방향으로 작동한다. 5는 검증위치다
4. w는 벽의 개수다
5. w번 반복되는 입력값들은 y좌표, x좌표 벽의 설치 유형이다
   0일 경우 y|x / y-1|x, y-1|x / y,x위치에 설치하며,
   1일 경우 y|x / y|x+1, y|x+1 / y|x 위치에 설치한다

해결방법 추론

1. r과 c의 최대 크기가 20으로 매우 작기 때문에 구현문제다
2. 이 문제에서 구현해야할 것은 다음과 같다

• 벽 설치
• 온풍기 가동 및 온도 상승 기록
• 주변 온도 확인해서 각각 온도 조절
• 가장자리 온도 1만큼 감소
• 검증 위치 온도가 모두 k이상인지 검증
• 초콜릿 개수 증가 및 100 초과일 경우 101로 고정

1. 벽은 경계선에 설치해야하기 때문에 배열의 값이 아닌 인덱스로 해결하기로 결정했다
2. 온풍기를 가동하고 전파되는 온도 상승을 기록하는 것은 BFS 탐색으로 해결히기로 결정했다
3. 주변 온도를 확인하는 것과 가장자리 온도 감소도 완전탐색으로 해결하기로 결정했다
4. 마지막 검증 위치 온도도 마찬가지로 완전탐색이며, 초콜릿 개수는 위의 과정을 포함해서 시뮬레이션으로 완성하기로 결정했다

시간복잡도 계산

1. rxc의 최대 값보다 k 최대값이 더 크기 때문에 k를 시간복잡도로 하겠다
2. 시간복잡도는 O(k)이며 시간제한안에 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 각 크기 입력값들은 int형 변수로 관리한다
2. 온풍기 위치와 검증 위치는 int형 1차원 배열 타입의 리스트로 관리한다
3. 온도를 관리하는 int형 2차원 배열은 두가지 타입으로 만들어서 관리한다

• 누적합산 온도 배열
• 임시합산 온도 배열
  크기는 r x c이다

4. 벽의 정보를 관리하는 배열은 4차원 boolean 배열로 관리한다. 크기는 r x c x r x c이며, 인덱스를 기준으로 벽의 유무를 구분한다
5. 탐색 편의 배열을 선언한다. 온도 조절을 위해 상하좌우를 탐색하거나 BFS탐색할때 사용할 배열을 하나 선언한다
6. 이어서 특수 유형 배열을 선언한다. 이 배열은 int형 2차원 배열로 온풍기의 dir에 따라 확산되는 위치를 표현한다.
   따라서 각각의 배열은 3가지 값을 갖으며, 가운데, 왼쪽, 오른쪽 순으로 정리했다
7. 정답을 출력할 ans를 0으로 초기화한다.
8. 또한 이전 문제들까지만 해도 y축은 무조건 y로 표현하고 x축도 x로만 표현했는데 주어진 방식이
   y축은 x, x축은 y형식이다. 문제 난이도가 높은 만큼 비교할 때 편하게 하기 위해 이전 방식을 버리고 문제에서 주어진 방식을 따랐다
9. 또한 벽의 위치 값이 1부터 시작하기 때문에 1~ r+1, c+1로 탐색하도록 크기와 탐색 범위를 변경해서 구현했다.

구현 코드 설계

벽 설치

1. 입력값 유형이 0인 경우 wall[x][y][x-1][y]와 wall[x-1][y][x][y]인 지점에 true를 표시한다
2. 입력값 유형이 1인 경우 wall[x][y+1][x][y]와 wall[x][y][x][y+1]인 지점에 true를 표시한다
3. 경계값에 설치하기 때문에 인덱스를 기준으로 두 지점에 true로 표시하면, 이후 탐색에 방해되지는 않을 것이다!

온풍기 실행

1. 온풍기를 하나씩 모두 실행한다
2. 온풍기 온도가 중복으로 증가하면 안되므로 방문배열을 선언한다
3. 처음 온도는 5이므로 int형 변수에 해당 값을 관리한다
4. 또한 방향에 따라 편의 메소드를 활용해서 온도가 5도인 지점의 좌표값을 구한뒤 방문체크와 임시 온도배열에 5를 더한다
5. 큐에는 바뀐 지점의 좌표값과 온풍기와의 거리를 의미하는 2를 넣어주며 bfs 탐색을 시작한다
6. 만약 현재 거리가 5 이상이라면 해당 방문은 스킵한다
7. 이제 특수 유형 편의 메소드를 사용해서 범위/벽여부/방문여부를 확인 한뒤, 방문체크와 온도 합산을 진행한다. 기준 온도 5에서 거리를 빼고 1을 더하면 문제의 조건에 맞는 상승 온도를 구할 수 있다
8. 해당 지점에서 거리를 1 증가한 값을 큐에 넣고 탐색을 반복한다

변화 온도 누적

1. 모든 온풍기를 실행하고 임시 온도 배열에 있는 값을 누적합산 온도 배열에 더해준다

온도 조절

1. 임시 온도 배열을 새로운 인스턴스로 초기화한다
2. 모든 지점을 돌아다니면서 0인 지점이 아닌 경우 상하좌우를 탐색하며 범위여부와 벽의 존재 여부를 확인한다
3. 모두 통과하면 두 지점을 비교해서, 기준 지점이 더 큰 경우 두 지점의 온도 차이를 4로 나눈 값을
   기준 지점에는 감산하고 탐색지점에는 합산한다

가장자리 온도 감소

1. 가장자리의 개념은 말그대로 전체 배열 크기의 가장자리를 의미한다. (아마 해당 개념이 아니었다면 더 어려웠을 것이다...)
2. 앞서 온도 조절한 결과를 누적합산 배열에 더한 뒤, 가장자리인 경우 누적합산 배열의 온도가 0이상인 경우
   1만큼 감소한다

검증

1. 이제 입력값을 받을 때, 미리 리스트에 저장해뒀던 검증 위치를 모두 확인하며, k보다 작은 지점이 있는지 확인한다
2. 한 지점이라도 k보다 작다면 false를 리턴한다. 모두 통과하면 true를 리턴한다
3. true를 리턴할 경우 시뮬레이션을 종료한다.

출력값 설계

1. 만약 ans의 값이 100보다 크면 101로 바꾸고 출력한다
2. 1번에 해당하지 않는 경우 그대로 ans를 출력하면 정답이 된다!

정답 코드

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

public class Main {


    static int r;
    static int c;
    static int k;
    static int[][] arr;
    static int w;
    static boolean[][][][] wall;
    static List<int[]> heaters;
    static List<int[]> check;
    static int[][] temp;
    static int[][] dx = {{0,0,0},{0,-1,1},{0,-1,1},{-1,-1,-1},{1,1,1}};
    static int[][] dy = {{0,0,0},{1,1,1},{-1,-1,-1},{0,-1,1},{0,-1,1}};
    static int[] ddx = {0,0,0,-1,1};
    static int[] ddy = {0,1,-1,0,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        arr = new int[r+1][c+1];
        temp = new int[r+1][c+1];
        check = new ArrayList<>();
        heaters = new ArrayList<>();
        for (int i = 1; i < r+1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < c+1; j++) {
                int a = Integer.parseInt(st.nextToken());
                if(a >= 1 && a <= 4){
                    heaters.add(new int[]{i,j, a});
                }
                if(a == 5){
                    check.add(new int[]{i,j});
                }
            }
        }
        w = Integer.parseInt(br.readLine());
        wall = new boolean[r+1][c+1][r+1][c+1];


        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 type = Integer.parseInt(st.nextToken());
            if(type == 0){
                wall[x][y][x-1][y] = true;
                wall[x-1][y][x][y] = true;
            }else{
                wall[x][y][x][y+1] = true;
                wall[x][y+1][x][y] = true;
            }
        }
        int ans = 0;
        while(ans <= 100){
            solve();
            adjust();
            ans++;
            if(checks()){
                break;
            }
        }

        if(ans > 100){
            ans = 101;
        }
        bw.write(ans+"");

        br.close();
        bw.close();
    }

    private static void adjust() {
        temp = new int[r+1][c+1];
        for (int i = 1; i < r + 1; i++) {
            for (int j = 1; j < c + 1; j++) {
                if(arr[i][j] == 0){
                    continue;
                }
                for (int l = 1; l < 5; l++) {
                    int nx = i + ddx[l];
                    int ny = j + ddy[l];
                    if(!isRange(nx, ny) || wall[i][j][nx][ny]){
                        continue;
                    }
                    if(arr[i][j] > arr[nx][ny]){
                        int tmp = (arr[i][j] - arr[nx][ny])/4;
                        temp[i][j] -= tmp;
                        temp[nx][ny] += tmp;
                    }
                }
            }
        }

        for (int i = 1; i < r + 1; i++) {
            for (int j = 1; j < c + 1; j++) {
                arr[i][j] += temp[i][j];
                if(i == 1 || j == 1 || i == r || j == c){
                    if(arr[i][j] > 0){
                        arr[i][j]--;
                    }
                }
            }
        }
    }

    private static boolean checks() {
        for (int[] a : check) {
            int x = a[0];
            int y = a[1];
            if (arr[x][y] < k) {
                return false;
            }
        }
        return true;
    }

    private static void solve() {
        temp = new int[r+1][c+1];
        for (int[] heater : heaters) {
            operate(heater[0], heater[1], heater[2]);
        }

        for (int i = 1; i < r + 1; i++) {
            for (int j = 1; j < c + 1; j++) {
                arr[i][j] += temp[i][j];
            }
        }
    }

    private static void operate(int x, int y, int dir) {
        boolean[][] visited = new boolean[r+1][c+1];
        Queue<int[]> q = new LinkedList<>();
        int now = 5;
        int nx = x + ddx[dir];
        int ny = y + ddy[dir];

        visited[nx][ny] = true;
        temp[nx][ny] += 5;
        q.add(new int[]{nx, ny, 2});
        while(!q.isEmpty()){
            int[] cur = q.poll();
            if(cur[2] > 5){
                continue;
            }

            for (int i = 0; i < 3; i++) {
                nx = cur[0] + dx[dir][i];
                ny = cur[1] + dy[dir][i];
                if(!isRange(nx, ny) || visited[nx][ny] || isWall(cur[0], cur[1], nx, ny, dir)){
                    continue;
                }
                visited[nx][ny] = true;
                temp[nx][ny] += now - cur[2] + 1;
                q.add(new int[]{nx,ny,cur[2]+1});
            }
        }
    }

    private static boolean isWall(int x, int y, int xx, int yy, int dir) {
        if(x == xx || y == yy) {
            if (wall[x][y][xx][yy]) {
                return true;
            }
        }else{
            if(dir == 1 || dir == 2){
                if(wall[x][y][xx][y] || wall[xx][y][xx][yy]){
                    return true;
                }
            }else{
                if(wall[x][y][x][yy] || wall[x][yy][xx][yy]){
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean isRange(int x, int y) {
        if(x > 0 && x <= r && y > 0 && y <= c){
            return true;
        }
        return false;
    }
}

문제 링크

23289번 - 온풍기 안녕!