[BOJ] 백준 23289 온풍기 안녕!

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static class Node{
		int r,c,dir,heat;
		Node(int r,int c,int dir){
			this.r = r;
			this.c = c;
			this.dir = dir;
		}
		Node(int r,int c,int dir,int heat){
			this.r = r;
			this.c = c;
			this.dir = dir;
			this.heat = heat;
		}
	}
	static int r,c,k;
	static int[][] map,heat;
	static int[] dr = {0,0,0,-1,1,-1,1,1,-1};
	static int[] dc = {0,1,-1,0,0,1,1,-1,-1};
	static int[][] check_dir = {{},{5,1,6},{8,2,7},{8,3,5},{7,4,6}};
	static int[][][][] check_wall = {
			{},
			{{{0,0,0},{-1,0,1}},{{0,0,1}},{{1,0,0},{1,0,1}}},
			{{{0,0,0},{-1,-1,1}},{{0,-1,1}},{{1,0,0},{1,-1,1}}},
			{{{0,-1,1},{0,-1,0}},{{0,0,0}},{{0,0,1},{0,1,0}}},
			{{{0,-1,1},{1,-1,0}},{{1,0,0}},{{0,0,1},{1,1,0}}}
	};
	static List<Node> machine = new ArrayList<>();
	static List<Integer>[][] wall;
	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];
		wall = new ArrayList[r][c];
		for(int i=0;i<r;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<c;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				wall[i][j] = new ArrayList<>();
				if(map[i][j]>=1 && map[i][j]<=4) {
					machine.add(new Node(i,j,map[i][j]));
				}
			}
		}
		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 t = Integer.parseInt(st.nextToken());
			wall[x][y].add(t);
		}
		int choco = 0;
		heat = new int[r][c];
		while(choco<=100) {
			for(Node m : machine) {
				int nr = m.r + dr[m.dir];
				int nc = m.c + dc[m.dir];
				if(nr<0 || nr>=r || nc<0 || nc>=c) continue;
				
				Queue<Node> q = new LinkedList<>();
				boolean[][] visit = new boolean[r][c];
				visit[nr][nc] = true;
				q.offer(new Node(nr,nc,m.dir,5));
				
				while(!q.isEmpty()) {
					Node curr = q.poll();
					heat[curr.r][curr.c] += curr.heat;
					out:
					for(int d=0;d<3;d++) {
						int dir = check_dir[curr.dir][d];
						int chR = curr.r + dr[dir];
						int chC = curr.c + dc[dir];
						if(chR<0 || chR>=r || chC<0 || chC>=c || visit[chR][chC]) continue;
						
						for(int i=0;i<check_wall[curr.dir][d].length;i++) {
							int nnr = curr.r + check_wall[curr.dir][d][i][0];
							int nnc = curr.c + check_wall[curr.dir][d][i][1];
							if(nnr<0 || nnr>=r || nnc<0 || nnc>=c) continue;
							int nw = check_wall[curr.dir][d][i][2];
							for(int wall : wall[nnr][nnc]) {
								if(wall==nw) continue out;
							}
						}
						if(curr.heat>=2) {
							visit[chR][chC] = true;
							q.offer(new Node(chR,chC,curr.dir,curr.heat-1));
						}
					}
				}
			}
			int[][] copy_heat = new int[r][c];
			for(int i=0;i<r;i++) {
				copy_heat[i] = heat[i].clone();
			}
			for(int i=0;i<r;i++) {
				for(int j=0;j<c;j++) {
					if(heat[i][j]==0) continue;
					out:
					for(int d=1;d<=4;d++) {
						int nr = i + dr[d];
						int nc = j + dc[d];
						if(nr<0 || nr>=r || nc<0 || nc>=c) continue;
						if(heat[i][j]<heat[nr][nc]) continue;
						
						int nnr = i + check_wall[d][1][0][0];
						int nnc = j + check_wall[d][1][0][1];
						if(nnr<0 || nnr>=r || nnc<0 || nnc>=c) continue;
						int nw = check_wall[d][1][0][2];
						for(int wall : wall[nnr][nnc]) {
							if(wall==nw) continue out;
						}
						int diff = heat[i][j] - heat[nr][nc];
						copy_heat[i][j] -= diff / 4;
						copy_heat[nr][nc] += diff / 4;
					}
				}
			}
			for(int i=0;i<r;i++) {
				heat[i] = copy_heat[i].clone();
			}
			for(int i=0;i<r;i++) {
				if(heat[i][0]>=1) heat[i][0]--;
				if(heat[i][c-1]>=1) heat[i][c-1]--;
			}
			for(int j=1;j<c-1;j++) {
				if(heat[0][j]>=1) heat[0][j]--;
				if(heat[r-1][j]>=1) heat[r-1][j]--;
			}
			choco++;
			if(check()) break;
		}
		System.out.println(choco);
	}
	private static boolean check() {
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(map[i][j]==5 && heat[i][j]<k) return false;
			}
		}
		return true;
	}
}