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

백준 17144번 미세먼지 안녕! (자바)

 

 

출처

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

17144번: 미세먼지 안녕!

 

 

 

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

격자판

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

확산 예

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

순환

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

 

 

 

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000)가 주어진다.

둘째 줄부터 R개의 줄에 Ar, c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

 

 

 

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

 

 

입출력 예

 

입출력 예

미세먼지의 확산이 일어나면 다음과 같은 상태가 된다.

확산 예

공기청정기가 작동한 이후 상태는 아래와 같다.

공기청정기 작동 후 예시

 

 

한 줄 요약

확산 - 상하좌우 확산을 고려하고, 이중 -1을 만나면 확산하지 않는다.

공기청정기 - 각 행, 열 마다 진행 방향이 다르므로 경우의 수를 다 계산한다.

 

 

 

내 코드

1. 전역 변수로 행, 열, 초, 공기청정기 위, 공기청정기 아래, 인접 행렬, 상하좌우 y, 상하좌우 x를 선언한다.

    - 공기청정기 위(upY)는 -1로 초기화한다.(인접 행렬 순회중 처음 -1을 만난 경우가 위 이기 때문에)

    - (0,1), (0,-1), (1,0), (-1,0)을 dy와 dx 배열로 나누어 선언한다.

 

2. r(행), c(열), t(초)를 입력받고 map[r][c]로 크기를 지정한다.

3. 이중 for문으로 각 위치별 정수를 입력한다.

    - 만약 -1을 입력하면 upY에 i(행)을 넣는다. 두 번째 -1은 downY에 i(행)을 넣는다.

4. 시간초만큼 확산(diffusion()), 순환(cycle())메서드를 실행한다.

 

//확산

5. 확산 계산에 사용할 동일한 이차원 행렬(diffMap)을 만든다.

6. diffMap[upY][0], diffMap[downY][0] 에 -1을 넣는다.

7. 이중 for문에서 원소가 0이면 continue 한다.

    - diffCnt(주변에 확산할 수 있는 개수), diffNum(원소/5)를 선언한다.

8. dy[] 길이의 for문을 하나 더 선언한다. (좌우상하 값 더하기 위해)

    - ny에는 i(행) + dy[k]를 넣는다.

    - nx에는 j(열) + dx[k]를 넣는다.

    - nx나 ny가 0보다 작거나 행렬 크기보다 크면 continue 한다.

    - map[nx][ny](상하좌우)에 -1이 있으면 continue 한다.

    - 위 두 경우에 해당하지 않을 때, 상하좌우에 나눈 값 더한다. (diffMap[ny][nx] += diffNum)
    - 상하좌우 개수(diffCnt)를 +1 한다.

9. diffMap[i][j]에 기존 값(map[i][j]) - 확산 값(diffNum*diffCnt)한다.

10. map[i][j] 에 diffMap[i][j]를 넣는다.

 

//순환

11. 공기청정기 위, 아래를 구분한다.

12. 각 행, 열의 순환 방향 경우의 수를 나눠 계산한다.

 

//합

13. main에서 모든 수를 더한 후 출력한다.

package argorithmStudy;

import java.util.Scanner;

public class HiDust {
	
	//행
	static int r;
	//열
	static int c;
	//초
	static int t;
	//공기청정기 위
	static int upY = -1;
	//공기청정기 아래
	static int downY;
	static int map[][];
	//0,1 || 0,-1 || 1,0 || -1,0 
	static int dy[] = {0, 0, 1, -1};
	static int dx[] = {1, -1, 0, 0};
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		r = sc.nextInt();
		c = sc.nextInt();
		t = sc.nextInt();
		
		map = new int[r][c];
		
		for (int i=0; i<r; i++) {
			for (int j=0; j<c; j++) {
				int temp = sc.nextInt();
				map[i][j] = temp;
				
				if (temp == -1) {
					//초기값을 -1로해 위에값을 upY, 아래값을 downY로 한다.
					if (upY == -1) {
						//2,0
						upY = i;
					} else {
						//3,0
						downY = i;
					}
				}
			}
		}
		
		
		//시간초만큼 확산, 순환
		for (int i=0; i<t; i++) {
			//확산
			diffusion();
			//순환
			cycle();
		}
		
		int sum = 0;
		for (int i=0; i<r; i++) {
			for (int j=0; j<c; j++) {
				if (map[i][j]<=0) {
					continue;
				}
				sum += map[i][j];
			}
		}
		
		System.out.println(sum);
		
	}

	//확산
	private static void diffusion() {
		
		//새로운 2차원 행렬 생성
		int diffMap[][] = new int[r][c];
		diffMap[upY][0] = -1;
		diffMap[downY][0] = -1;
		
		for (int i=0; i<r; i++) {
			for (int j=0; j<c; j++) {
				//공기청정기는 패스
				if (map[i][j] <= 0) {
					continue;
				}
				
				int diffCnt = 0;
				int diffNum = map[i][j]/5;
				for (int k=0; k<dy.length; k++) {
					//상하좌우
					int ny = i + dy[k];
					int nx = j + dx[k];
					
					//상하좌우가 0보다 작거나 행렬보다 크면 넘긴다.
					if (ny < 0 || nx < 0 || ny >= r || nx >= c) {
						continue;
					}
					
					//상하좌우에 -1이 있으면 넘긴다.
					if (map[ny][nx] == -1) {
						continue;
					}
					
					//위 두 경우에 해당하지 않을 때, 상하좌우에 나눈값 더하기
					diffMap[ny][nx] += diffNum;
					diffCnt++;
				}
				//주변에 확산한 값 빼기
				diffMap[i][j] += map[i][j] - (diffCnt*diffNum);
				
			}
		}
		
		for (int i=0; i<r; i++) {
			for (int j=0; j<c; j++) {
				map[i][j] = diffMap[i][j];
			}
		}
	}
	
	
	//순환
	private static void cycle() {
		//위, 아래 구분
		
		//위
		//1열
		//0,0 -> 1,0
		for (int i=upY-1; i>0; i--) {
			map[i][0] = map[i-1][0];
		}
		//1행
		//0,1 -> 0,0 ...
		for (int i=0; i<c-1; i++) {
			map[0][i] = map[0][i+1];
		}
		//8열
		//1,7 -> 0,7 ...
		for (int i=0; i<upY; i++) {
			map[i][c-1] = map[i+1][c-1];
		}
		//3행
		//2,1 -> 2,2
		for (int i=c-1; i>1; i--) {
			map[upY][i] = map[upY][i-1];
		}
		//공기청정기 옆 0만들기
		map[upY][1] = 0;
		
		//아래
		//1행
		//4,0 -> 3,0 ..
		for (int i=downY+1; i<r-1; i++) {
			map[i][0] = map[i+1][0];
		}
		//8행
		//7,1 -> 7,0 ...
		for (int i=0; i<c-1; i++) {
			map[r-1][i] = map[r-1][i+1];
		}
		//8열
		//6,8 -> 7,8
		for (int i=r-1; i>downY; i--) {
			map[i][c-1] = map[i-1][c-1];
		}
		//4헹
		//3,2 -> 3,3
		for (int i=c-1; i>1; i--) {
			map[downY][i] = map[downY][i-1];
		}
		//공기청정기 옆 0만들기
		map[downY][1] = 0;
	}
	
}

 

 

고려할 점

1. 상하좌우를 x, y배열을 따로 만들어 고려하는 것

2. upY에 초기값을 넣어 공기청정기 위칸인 것을 구분하는 것

3. 확산용 인접 행렬을 추가로 만들어 계산하는 것