[Java] 백준 23289 - 온풍기 안녕!

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

23289번: 온풍기 안녕!

 

정말정말정말 생각해야하는 부분이 많다. 이 문제

ㅠㅠ.. 내 하루..

 

과정

 

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴

- 온풍기 방향으로 온도 5 생성

- 5에서 온풍기랑 같은 방향으로 봤을때, 정면과 왼쪽대각선 및 오른쪽 대각선으로 온도 4 생성

- 위 과정을 1까지 반복 (단, 칸막이에 따라 온도가 높여지지 않을 수 있음)

2. 온도가 조절됨

- 두 칸의 온도 차이가 있을 경우 큰 쪽에서 ⌊(두 칸의 온도의 차이)/4⌋ 만큼 넘겨줌

- 두 칸 사이에 칸막이가 있는 경우 고려 X

3. 온도가 1이상인 가장 바깥쪽 칸의 온도가 1씩 감소

- 가장자리에 있는 칸 1씩 감소

4. 초콜릿 먹음

- 문제에서 리턴해야 하는 카운트(값)

5. 확인해야 할 모든 칸이 K이상이 되었는지 검사, 맞으면 중단

 

해결한 방법

 

• 선풍기는 Fan(x,y,dir) 객체로 ArrayList에 저장
• 확인용 칸은 int[] 배열로 ArrayList에 저장
• 벽은 boolean[R][C][4] 3차원 배열로 해당 칸의 오른쪽0왼쪽1위2아래3 에 있는 경우 true 설정
• 온도는 각 선풍기에서 반영된 온도 int[][] 배열(winds), 모든 선풍기 배열을 합한 값 int[][]배열(temp), 최종 합산 값(hot)으로 구성
• 온도 값은 온풍기의 방향(dir)과 해당 방향을 바라봤을 때 왼쪽(left), 왼쪽(right)를 각각 넣어서 탐색
• 온도 조절은 4방향에서 자기보다 작은 칸을 발견했을 경우만 계산

 

주의할 점 - 시행착오

 

• 온도 조절, 온풍기 작동은 동시에 일어나기 때문에 각 탐색마다 임시로 저장해두고, 마지막에 한 번에 반영하게 해야 함
• 가장자리 1감소는 모서리가 중복으로 감소될 수 있으므로 주의하기
• 복붙할때 dx, dy 잘 보기 ! y값 조정인데 여기저기 dx로 복붙돼서 자꾸 어디서 이상하게 나옴
• 정면 왼쪽 오른쪽 탐색시 범위 벗어나지 않도록 주의

 

 

온도가 퍼질 수 있는 경우

• 대각선 : 빨간색 칸막이가 없어야함 
• 정면 : 파란색 칸막이가 없어야함

 

[코드]

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

public class boj23289 {
	static class Fan {
		int x, y, dir;
		
		public Fan (int x, int y, int dir) {
			this.x=x;this.y=y;this.dir=dir;
		}
	}
	
	public static int R, C, K;
	public static int[][] map, hot, temp;
	public static boolean[][][] wall;
	public static ArrayList<Fan> fans = new ArrayList<Fan>();
	public static ArrayList<int[]> checkList = new ArrayList<int[]>();
	
	public static void main(String[] args) throws IOException {
		init();
		
		int choco = 0;
		while(choco <= 100 && !checkAll()) {
			activeFan();
			
			sum();
			
			distribute();
			
			choco++;
			
			side();
		}
		System.out.println(choco);
	}
	
	public static void printMap(int[][] map, String Message) {
		System.out.println("========="+Message+"=======");
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++)
				System.out.print(map[i][j]+" ");
			System.out.println();
		}	
	}
	
	/* 4. 전부 체크 */
	public static boolean checkAll() {
		for(int[] point : checkList) {
			int x = point[0], y = point[1];
			if(hot[x][y]<K)
				return false;
		}
		return true;
	}
	
	/* 3. 바깥쪽 감소 */
	public static void side() {
		for(int i=0; i<R; i++) {
			if(hot[i][0]!=0)
				hot[i][0]--;
			if(hot[i][C-1]!=0)
				hot[i][C-1]--;
		}
		
		for(int i=1; i<C-1; i++) {
			if(hot[0][i]!=0)
				hot[0][i]--;
			if(hot[R-1][i]!=0)
				hot[R-1][i]--;
		}
			
	}
	
	/* 2. 온도 조절 */
	
	public static void distribute() {
		int[][] change = new int[R][C];
		
		for(int i=0; i<R; i++)
			for(int j=0; j<C; j++) {
				int now = hot[i][j];
				
				for(int d=0; d<4; d++) {
					if(wall[i][j][d])
						continue;
					if(i==2 && j==4)
						System.out.print("");
					
					int nx=i+dx[d], ny=j+dy[d];
					
					if(!isInArea(nx, ny))
						continue;
					
					int next = hot[nx][ny];
					
					if(now > next) {
						int res = (now-next)/4;
						change[i][j] -= res;
						change[nx][ny] += res;
					}
				}
			}
		
		
		for(int i=0; i<R; i++)
			for(int j=0; j<C; j++)
				hot[i][j]+=change[i][j];
	}
	
	/* 1. 온풍기 바람 나옴 */
	// 온도 더함
	public static void sum() {
		
		for(int i=0; i<R; i++)
			for(int j=0; j<C; j++)
				hot[i][j] += temp[i][j];
		temp = new int[R][C];
	}
	
	public static void activeFan() {
		for(Fan f : fans) {
			// 방향 0오른쪽 1왼쪽 2위 3아래
			int x = f.x, y = f.y, dir = f.dir;
			//System.out.println(x+" "+y+" "+dir);
			
			if(wall[x][y][f.dir])
				continue;
			
			if(dir == 0)
				wind(f, 2, 3);
			else if(dir == 1)
				wind(f, 3, 2);
			else if(dir == 2)
				wind(f, 1, 0);
			else
				wind(f, 0, 1);
		}
	}
	
	
	// 방향 0오른쪽 1왼쪽 2위 3아래
	public static int[] dx = {0,0,-1,1};
	public static int[] dy = {1,-1,0,0};
	
	public static void wind(Fan f, int left, int right) {
		int[][] winds = new int[R][C];
		int x = f.x+dx[f.dir], y = f.y+dy[f.dir], dir = f.dir;
		int cnt = 0;
		
		winds[x][y]=5;
		
		// 5Level, 값 입력이기도 함
		for(int i=4; i>=1; i--, cnt+=2) {
			if(!isInArea(x,y))
				break;
			
			// 가운데
			if(winds[x][y]!=0)
				spread(winds, i, x, y, dir, left, right);
			
			// 왼쪽과 오른쪽
			int rx=x,ry=y,lx=x,ly=y;
			
			for(int j=0; j<cnt; j++) {
				rx += dx[right]; ry+=dy[right];
				lx += dx[left]; ly+=dy[left];
				
				if(isInArea(rx,ry) && winds[rx][ry]!=0)
					spread(winds, i, rx, ry, dir, left, right);
				if(isInArea(lx,ly) && winds[lx][ly]!=0)
					spread(winds, i, lx, ly, dir, left, right);
			}
			x+=dx[dir]; y+=dy[dir];
		}
		
		//printMap(winds," Winds ");
		
		for(int i=0; i<R; i++)
			for(int j=0; j<C; j++)
				temp[i][j] += winds[i][j];
	}
	
	public static void spread(int[][] winds, int num, int x, int y, int dir, int left, int right) {
		
		// 정방향
		int nx = x+dx[dir], ny=y+dy[dir];
		if(isInArea(nx, ny) && !wall[x][y][dir])
			winds[nx][ny]=num;
		
		// 왼쪽 대각선
		int lx = nx+dx[left], ly=ny+dy[left];
		if(isInArea(lx, ly) && !wall[x][y][left] && !wall[x+dx[left]][y+dy[left]][dir])
			winds[lx][ly]=num;
		
		// 오른쪽 대각선
		int rx = nx+dx[right] , ry = ny+dy[right];
		if(isInArea(rx, ry) && !wall[x][y][right] && !wall[x+dx[right]][y+dy[right]][dir])
			winds[rx][ry]=num;
	}
	
	public static boolean isInArea(int x, int y) {
		return x>=0 && x<R && y>=0 && y<C;
	}
	
	
	
	static void init() 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());
		hot = new int[R][C];
		temp = new int[R][C];
		wall = new boolean[R][C][4];
		
		for(int i=0; i<R; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<C; j++) {
				int num = Integer.parseInt(st.nextToken());
				if(num > 0 && num <= 4)
					fans.add(new Fan(i,j,num-1));
				else if(num == 5)
					checkList.add(new int[] {i,j});
			}
		}
		
		// 방향 1오른쪽 2왼쪽 3위 4아래
		
		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, y = Integer.parseInt(st.nextToken())-1;
			int k = Integer.parseInt(st.nextToken());
			
			if(k==0) {
				int nx = x-1, ny = y;
				if(!isInArea(nx, ny))
					continue;
				wall[x][y][2]=true;	// 해당 좌표의 위
				wall[nx][ny][3]=true;	// 위 좌표의 아래
			} else {
				int nx = x, ny = y+1;
				if(!isInArea(nx, ny))
					continue;
				wall[x][y][0]=true;	// 해당 좌표의 오른쪽
				wall[nx][ny][1]=true;	// 오른쪽 좌표의 왼쪽
			}
		}
		
	}
}