[BOJ 23289] 온풍기 안녕! (Java)

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

23289번: 온풍기 안녕!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main_BOJ_23289_1 {
	static int R, C, K, W;
	static int[][] map;
	static ArrayList<int[]> heatters=new ArrayList<>();
	static ArrayList<int[]> targets=new ArrayList<>();
	static int[][][] walls;
	static int[][] dx= {{-1,0,1}, {-1,0,1}, {-1,-1,-1}, {1,1,1}};
	static int[][] dy= {{1,1,1}, {-1,-1,-1},{-1,0,1}, {-1,0,1}};
	static int[] first_dx= {0,0,-1,1};
	static int[] first_dy= {1,-1,0,0};	//동,서,북,남
	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];
		walls=new int[R+1][C+1][4];
		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>=1 && x<=4) {
					heatters.add(new int[] {i,j,x});
				}
				else if (x==5) {
					targets.add(new int[] {i,j});
				}
			}
		}
		W=Integer.parseInt(br.readLine());
		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 t=Integer.parseInt(st.nextToken());
			if (t==0) {
				walls[x][y][2]=1;
				walls[x-1][y][3]=1;
			}
			else if (t==1) {
				walls[x][y][0]=1;
				walls[x][y+1][1]=1;
			}
		}
		int answer=0;
		while (answer<=100) {
			onHeatter();
			controlTemp();
			decrease();
			answer++;
			if (check()) break;
		}
/*		for (int a=1; a<=R; a++) {
			for (int b=1; b<=C; b++) {
				System.out.print(map[a][b]+" ");
			}
			System.out.println();
		}*/
		System.out.println(answer);
	}
	
	
	private static void decrease() {
		int x=1, y=1;
		for (y=1; y<=C; y++) {
			if (map[x][y]>0) map[x][y]-=1;
		}
		y=C;
		for (x=2; x<=R; x++) {
			if (map[x][y]>0) map[x][y]-=1;
		}
		x=R;
		for (y=C-1; y>=1; y--) {
			if (map[x][y]>0) map[x][y]-=1;
		}
		y=1;
		for (x=R-1; x>1; x--) {
			if (map[x][y]>0) map[x][y]-=1;
		}
	}


	private static void controlTemp() {
		int[][] delta=new int[R+1][C+1];
		for (int i=1; i<=R; i++) {
			for (int j=1; j<=C; j++) {
				for (int d=0; d<4; d++) {
					int ni=i+first_dx[d];
					int nj=j+first_dy[d];
					if (isInRange(ni, nj) && map[i][j]>map[ni][nj] && walls[i][j][d]==0) {
						int temp=(map[i][j]-map[ni][nj])/4;
						delta[ni][nj]+=temp;
						delta[i][j]-=temp;
					}
				}
			}
		}
		for (int i=1; i<=R; i++) {
			for (int j=1; j<=C; j++) {
				map[i][j]+=delta[i][j];
			}
		}
		
	}


	private static void onHeatter() {
		for (int i=0; i<heatters.size(); i++) {
			int[] heatter=heatters.get(i);
			spread(heatter[0], heatter[1], heatter[2]);
		}
	}


	private static void spread(int start_x, int start_y, int d) {
		d=d-1; 
		int x=start_x+first_dx[d];
		int y=start_y+first_dy[d];
		Queue<int[]> q=new LinkedList<>();
		boolean[][] visited=new boolean[R+1][C+1];
		q.add(new int[] {x,y,5});
		visited[x][y]=true;
		map[x][y]+=5;
		while (!q.isEmpty()) {
			int[] curr=q.poll();
			if (curr[2]==1) break;
			for (int i=0; i<3; i++) {		//3개에 대해 spread 가능한지 체크 
				int nx=curr[0]+dx[d][i];
				int ny=curr[1]+dy[d][i];
				if (isInRange(nx, ny) && !visited[nx][ny] && isPossible(curr[0], curr[1], d, i)) {
					q.add(new int[] {nx, ny, curr[2]-1});
					visited[nx][ny]=true;
					map[nx][ny]+=(curr[2]-1);
				}	
			}
		}
		
	}
	
	private static boolean isPossible(int x, int y, int d, int i) {	//4개의 케이스 벽 살펴보는 경우 따져줌
		if (d==0) {		//동
			if (i==0) {
				if (isInRange(x-1,y) && walls[x-1][y][0]==0 && walls[x-1][y][3]==0) return true;
			}
			else if (i==1) {
				if (walls[x][y][0]==0) return true;
			}
			else if (i==2) {
				if (isInRange(x+1, y) && walls[x+1][y][2]==0 && walls[x+1][y][0]==0) return true;
			}
		}
		else if (d==1) {		//서
			if (i==0) {
				if (isInRange(x-1,y) && walls[x-1][y][1]==0 && walls[x-1][y][3]==0) return true;
			}
			else if (i==1) {
				if (walls[x][y][1]==0) return true;
			}
			else if (i==2) {
				if (isInRange(x+1, y) && walls[x+1][y][2]==0 && walls[x+1][y][1]==0) return true;
			}
		}
		else if (d==2) {		//북
			if (i==0) {
				if (isInRange(x,y-1) && walls[x][y-1][0]==0 && walls[x][y-1][2]==0) return true;
			}
			else if (i==1) {
				if (walls[x][y][2]==0) return true;
			}
			else if (i==2) {
				if (isInRange(x, y+1) && walls[x][y+1][1]==0 && walls[x][y+1][2]==0) return true;
			}
		}
		else if (d==3) {		//남
			if (i==0) {
				if (isInRange(x,y-1) && walls[x][y-1][0]==0 && walls[x][y-1][3]==0) return true;
			}
			else if (i==1) {
				if (walls[x][y][3]==0) return true;
			}
			else if (i==2) {
				if (isInRange(x, y+1) && walls[x][y+1][1]==0 && walls[x][y+1][3]==0) return true;
			}
		}
		return false;
	}


	private static boolean isInRange(int x, int y) {
		return x>=1 && y>=1 && x<=R && y<=C;
	}


	private static boolean check() {
		for (int i=0; i<targets.size(); i++) {
			int x=targets.get(i)[0];
			int y=targets.get(i)[1];
			if (map[x][y]<K) {
				return false;
			}
		}
		return true;
	}

}

구현+시뮬레이션+BFS/DFS 문제

 

처음에는 풀 때 온풍기의 방향에 따라 배열을 돌리는 방식으로 했다가, 이렇게 하면 벽도 움직여줘야 하니까 더 코드가 복잡해졌다.. 사실 이렇게 어렵게 풀 필요 없이 방향에 따라 퍼지는 방향을 달리 하는 방식으로 탐색하면 됐었다..

얍문(https://yabmoons.tistory.com/718) 님의 코드를 참고했다

 

heatters: 온풍기의 위치, 방향을 저장

targets: 살필 위치를 저장

int[][] dx, dy: i번 방향에서 1,2,3번째 퍼질 위치 

int[] first_dx, dy: 온풍기의 방향에 따른 처음에 바람을 받는 방의 위치를 얻기 위한 배열

int[][][] walls: 벽의 위치를 표시하는 배열로 walls[i][j][0] 이면 (i,j) 방의 동쪽 방향에 벽이 있는 것이다

 

나는 0번을 동쪽, 1번을 서쪽, 2번을 북쪽, 3번을 남쪽으로 설정했다, 입력은 1,2,3,4 로 받으므로 여기서 -1을 빼서 로직을 구현했다

 

spread(): 각 온풍기에 따라 퍼지는 온도를 저장하는 함수, BFS 로 구현했다

로직은 간단하다.. 온풍기의 방향에 따라 초기 위치를 구해준다=> 초기 위치를 구해줬으면 큐에 그 위치와, 온도값인 5를 넣어주고, 방문 배열에 true를 표시하고, map의 해당 위치에 5를 더해준다 

그 후, 큐에서 꺼낸 온도값이 1이 될 때까지 다음 과정을 반복한다:

큐에서 꺼낸 현재 위치에서 다음으로 퍼질 위치 3곳에 대해 탐색한다 => 다음 위치가 범위에 있고, 미방문이며, 벽이 없는 경우(isPossible() 함수에서 true를 리턴할 경우), 큐에 그 새 위치를 넣어주고 방문 표시를 해주며 map의 위치에 현재 온도-1 를 더해주면 된다.

 

isPossible(): 현재 위치, 온풍기의 방향, 현재 위치에서 탐색할 다음 위치의 번째 수를 받아 조건에 맞게 체크한다.

각 방향에 따라 체크할 벽의 위치가 다르므로 이는 직접 손으로 써가면서 조건을 구현했다. 

 

controlTemp(): 온도를 조절해주는 함수로, 마찬가지로 map을 다 돌면서 인접 4방향 중에 작은 것이 있을 경우 벽이 그 방향으로 있는지 체크한후 연산을 해주면 된다.

 

 

이 문제의 포인트는 온풍기의 방향에 따라 퍼지는 방향을 달리 하는 것이고, 이 퍼지는 방향에 따라 체크하는 벽의 위치를 잘 생각해줘야 한다는 점이다. 또한 벽이 있는 것을 표시할 때 동/서/남/북 방향에 대해 표시하면 더 구현이 쉬워진다..