[백준] 17144 미세먼지 안녕! / 자바(Java)

문제

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

17144번: 미세먼지 안녕!

 

---

해설

2차원배열에서의 탐색을 구현하는 문제입니다.

크게 2단계로 이루어져 있으며 미세먼지가 확산되는 단계와 공기가 순환하는 단계가 있습니다.

 

1단계 : 미세먼지 확산

 

확산의 규칙

1. 인접한 네 방향으로 확산하되 벽과 공기청정기로는 확산되지 않는다.

2. 확산된 곳에는 (본래의 값/5) 의 값만큼 먼지가 추가된다(소수점자리는 이산수학으로 / 사용시 제거된다)

3. 본래의 위치에는 (본래의 값-확산된값*확산된 위치의 수)만큼 먼지가 남는다.

4. 확산은 모든 칸에서 동시에 일어난다.

 

4번 규칙에 의해 확산된 이후 내용을 따로 저장할 임시 배열을 만들어 주어야 합니다.

기존 배열의 먼지가 있는 모든 칸에 대해 확산된 값을 계산 후 4방탐색을 시행해 넘어갈 수 있는 부분을 찾으며 개수를 세고 각각 임시배열에 확산된 값을 추가해 줍니다. 4방향에 대한 탐색이 끝난 후 본래 위치에 남은 값만큼 임시배열에 더해주는 방식으로 1단계 계산이 완료됩니다.

 

 

2단계 : 공기의 순환

 

순환의 규칙

1. 공기청정기를 기준으로 위쪽은 반시계방향으로, 아래쪽은 시계방향으로 순환한다.

2. 공기청정기에서 나오는 바람은 미세먼지가 없고 들어간 미세먼지는 모두 정화된다.

3. 순환에 맞추어 한칸씩 이동한다.

 

위쪽 순환을 기준으로 (j는 위 공기청정기 위치, C는 행렬의 열)

(0,j) -> (0,0) => 위로 진행 <j~0으로, 처음 인덱스는 0으로 고정하고 마지막으로 인덱스가 0일때 저장 후 넘겨줌>
(0,0) -> (C,0) => 우로 진행 <0~C으로, 처음 인덱스에서 넘겨받고 마지막으로 인덱스가 C일때 저장 후 넘겨줌>
(C,0) -> (C,j) => 하로 진행 <0~j으로, 처음 인덱스에서 넘겨받고 마지막으로 인덱스가 j일때 저장 후 넘겨줌>
(C,j)-> (0,j) => 좌로 진행 <C~1으로, 처음 인덱스에서 넘겨받고 마지막으로 인덱스가 0일때는 생략>

 

 

이렇게 4방향에 대해 배열의 이동을 통해 순환을 구현합니다. 진행 끝부분을 저장을 통해 넘겨주어야 합니다.

 

아래 쪽 순환 역시 마찬가지로 진행합니다.

 

주의점

• 2차원 배열에서 내부 값이 이동할 때 이동하는 방향 끝의 값을 저장하고 한 칸 씩 땡겨준다.
• 순환시 배열의 범위를 벗어나지 않도록 주의한다.
• 미세먼지가 퍼짐을 구현할 때는 모든 배열에 있는 미세먼지들이 한번에 퍼지므로 임시 배열을 만들어 계산 후 최종값을 원래의 배열에 저장한다.

---

코드

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

public class Main{

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
	
		// R : 판의 행, C : 판의 열, T : 경과 시간
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());
		
		int [][] board = new int [R][C];
		
		for(int i=0; i<R;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<C;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 구현부
		int [] dr = {-1,0,1,0};
		int [] dc = {0,1,0,-1};
		
		
		// T초동안 진행
		for(int t=0;t<T;t++) {
			//퍼지는 정도의 위치를 저장할 배열 생성
			int [][] tmparr = new int [R][C];
			
			// 1. 미세먼지의 퍼짐
			for(int i=0; i<R;i++) {
				for(int j=0;j<C;j++) {
					//공기청정기 타일인 경우
					if(board[i][j]==-1) tmparr[i][j] = -1;
					
					// 미세먼지타일 인 경우
					else if(board[i][j]!=0 ) {
						int cnt=0;
						int dust = board[i][j];
						// 4방탐색 시작
						for(int k=0;k<4;k++) {
							int newr = i+dr[k];
							int newc = j+dc[k];
							
							if(0<=newr && 0<=newc && R>newr && C>newc) { // 범위 내인 경우
								// 공기청정기 쪽으로는 무시
								if(board[newr][newc]==-1) continue;
								// 조건을 만족하는 경우 퍼짐
								tmparr[newr][newc] += dust/5;
								cnt++;
							}
						}
						tmparr[i][j] += dust - (dust/5) * cnt;
						
					}
				}
			}

			// 2. 공기청정기의 순환
			int a=0,b;
			//공기청정기의 위치 확인
			for(int i=0;i<R;i++) {
				if(board[i][0]==-1) a = i-1;

			}
			b = a+1;
			
			// 2.1 : 위쪽 순환(반시계방향)
			
			// 범위
			int height = a;
			int width = C-1;
			
			// 좌 (상->하)
			for(int i=height-1;i>0;i--) {
				tmparr[i][0] = tmparr[i-1][0];
			}
			
			// 상(우->좌)
			for(int i=1;i<width+1;i++) {
				tmparr[0][i-1] = tmparr[0][i];
			}
			// 우(하->상)
			for(int i=0;i<height;i++) {
				tmparr[i][width] = tmparr[i+1][width];
			}
			// 하(좌->우)
			for(int i=width-1;i>0;i--) {
				tmparr[height][i+1] = tmparr[height][i];
			}
			tmparr[a][1] = 0;
			
			// 2.2 : 아래쪽 순환(시계방향)
			
			// 좌(하->상)
			for(int i=b+2;i<R;i++) {
				tmparr[i-1][0] = tmparr[i][0];
			}
			// 하(우->좌)
			for(int i=1;i<width+1;i++) {
				tmparr[R-1][i-1] = tmparr[R-1][i];
			}
			// 우(상->하)
			for(int i=R-1;i>b;i--) {
				tmparr[i][width] = tmparr[i-1][width];
			}
			// 상(좌->우)
			for(int i=width-1;i>0;i--) {
				tmparr[b][i+1] = tmparr[b][i];
			}
			
			tmparr[b][1] = 0;
			// 완료 후 원본에 덮어쓴다.
			board = tmparr.clone();
		}// T번 반복 후
		
		// 남은 미세먼지 양 확인
		int ans = 0;
		for(int i=0; i<R;i++) {
			for(int j=0;j<C;j++) {
				ans += board[i][j];
			}
		}
		// 공기청정기의 값 제거
		ans += 2;
		
		System.out.println(ans);
		
	}
}