[백준_17144번] 미세먼지 안녕!_삼성 SW 역량테스트

https://www.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)×(확산된 방향의 개수) 이다.

1. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

 

다음은 확산의 예시이다.

 

 

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

 

인접한 네 방향으로 모두 확산이 일어난다.

 

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

 

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

 

방의 정보가 주어졌을 때, 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번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

 

[코드]

import java.util.*;

public class BaekJoon_17144 {
	static int r,c,t;
	static int[] position=new int[2];
	static int[][] map;
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		r=sc.nextInt();
		c=sc.nextInt();
		t=sc.nextInt();
		
		map=new int[r][c];
		
		int index=0;
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				map[i][j]=sc.nextInt();
				
				// 공기청정기는 항상 1열에 설치되어 있기 때문에
				if(map[i][j]==-1)
					position[index++]=i;
			}
		}
		
		while(t-->0) {
			map=spreadDust();
			purifier();
		}
		
		System.out.println(calculation());
	}
	
	// 미세먼지가 퍼지는 함수
	static int[][] spreadDust() {
		int[][] temp=new int[r][c]; // 임시배열
		
		for(int x=0;x<r;x++) {
			for(int y=0;y<c;y++) {
				// 공기청정기 위치 표시
				if(map[x][y]==-1) {
					temp[x][y]=-1;
					continue;
				}
				
				/*
				 * temp에는 어떤 x,y에 의해 nx,ny 좌표에 확산된 미세먼지의 양이 저장되어 있다.
				 * 이후 nx,ny가 x,y가 되어 미세먼지가 확산될 때 다른 좌표에 의해 확산된 미세먼지의 양도
				 * 고려해야 하기 때문에 여기서 map 값과 temp 값을 더해주어야 한다. 
				 */
				temp[x][y]+=map[x][y];
				
				for(int k=0;k<4;k++) {
					int nx=x+dx[k];
					int ny=y+dy[k];
					
					// 배열의 범위를 벗어난 경우 넘어간다.
					if(nx>=r||ny>=c|nx<0||ny<0)
						continue;
					// 이동한 곳에 공기청정기가 있는 경우도 넘어간다.
					if(map[nx][ny]==-1)
						continue;
					
					temp[nx][ny]+=(map[x][y]/5); // 주변에 미세먼지 확산
					temp[x][y]-=(map[x][y]/5); // 확산된 만큼 미세먼지 양 감소
				}
			}
		}
		return temp;
	}
	
	/*
	 * 공기청정기에 의한 미세먼지의 이동은 바람의 순환뱡향으로 값을 이동시키면
	 * 방향이 바뀌는 부분이 복잡하기 때문에 바람의 흐름의 반대 방향으로 값을 
	 * 당겨주면 방향의 변화를 생각할 필요 없이 쉽게 이동시킬 수 있다.  
	 */
	static void purifier() {
		// 공기청정기의 위쪽은 반시계방향
		int top=position[0]; 
		
		for(int x=top-1;x>0;x--)
			map[x][0]=map[x-1][0]; // 왼쪽 세로, 아래로 끌어당기기
		
		for(int y=0;y<c-1;y++)
			map[0][y]=map[0][y+1]; // 윗쪽 가로, 왼쪽으로 끌어당기기
		
		for(int x=0;x<top;x++)
			map[x][c-1]=map[x+1][c-1]; // 오른쪽 세로, 위로 끌어당기기
		
		for(int y=c-1;y>1;y--)
			map[top][y]=map[top][y-1]; // 아랫쪽 가로, 오른쪽으로 끌어당기기
		
		map[top][1]=0;
		
		// 공기청정기의 아랫쪽은 시계방향
		int bottom=position[1];
		
		for(int x=bottom+1;x<r-1;x++) // 왼쪽 세로, 위로 끌어당기기
			map[x][0]=map[x+1][0];
		
		for(int y=0;y<c-1;y++)
			map[r-1][y]=map[r-1][y+1]; // 아랫쪽 가로, 왼쪽으로 끌어당기기
		
		for(int x=r-1;x>bottom;x--)
			map[x][c-1]=map[x-1][c-1]; // 오른쪽 세로, 아래로 끌어당기기
		
		for(int y=c-1;y>1;y--)
			map[bottom][y]=map[bottom][y-1]; // 윗쪽 가로, 오른쪽으로 끌어당기기
		
		map[bottom][1]=0;
	}
	
	// t초 후 미세먼지 양 계산
	static int calculation() {
		int sum=2;
		
		for(int i=0;i<r;i++)
			for(int j=0;j<c;j++)
				sum+=map[i][j];
		
		return sum;
	}
}

 

[고찰] 

 이번 문제는 시뮬레이션 문제로 우선 문제를 구조화 하는 것이 중요하다. 

 

1. map 정보를 입력받으면서 공기청정기의 행 위치 저장하기(공기청정기는 항상 1열에 있기 때문에 열은 고려하지 않는다.)

2. 미세먼지 확산(spreadDust 함수)

    -> 기존 배열 map에 바로 값을 수정하면 옆의 미세먼지로 인해 값이 변동된다. 미세먼지의 확산은 동시에 이루어지기 때문에 확산되기전 미세먼지의 양을 사용해야 함으로 임시 배열 temp를 사용하여 덮어쓰는 방식으로 해결

3. 공기청정기 작동(purifier 함수)

    -> 기존의 순환 방향으로 값을 이동시키면 방향이 전환되는 부분이 복잡하다. 따라서 방향의 흐름의 반대 방향으로 값을 당겨준다고 생각하면 방향의 전환을 고려할 필요 없이 값을 이동시킬 수 있다. 

 

 공기청정기에 의해 미세먼지를 이동시키는 과정이 어려워 다른 사람의 코드를 참고했는데 위와 같은 해결 방법이 있다는 것을 알았다. 다음에도 이렇게 배열의 값을 회전시켜야 하는 문제가 있다면 해당 방법을 이용해도 좋을 것 같다.