[ BOJ 17144 ] 미세먼지 안녕! (Java)

문제

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

• 계절 별미 미세먼지~

• 이차원 배열 회전 관련 문제 : 🔗 행렬 테두리 회전하기

문제 풀이

1. 미세먼지와 공기 청정기 위치를 나타낼 클래스 pos 생성

public static class pos{
	int x, y;

	public pos(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

	@Override
	public String toString() {
		return "pos [x=" + x + ", y=" + y + "]";
	}
}

2. 공기 청정기 회전 방향 고려

• 공기 청정기 위쪽 방향, 아래쪽 방향이 다른 방향으로 회전하기 때문에 배열을 따로 만들어 줌

public static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};	// 시계방향
public static int[][] antidir = {{-1,0},{0,1},{1,0},{0,-1}}; // 반시계 방향

3. map[i][j] 입력 받기

• 공기청정기 -1 인지 미세먼지 >0 인지 판단해서 입력 받기

4. T초 동안 로직 반복

• [미세먼지 확산 - 먼지 확인 - 청소 - 먼지 확인]
  • 미세먼지 확산 : spread()
  • 먼지 확인 : getDust()
  • 청소 : clean(공기청정기, 회전 방향, x 바운더리)

4-1. spread 함수

• 🔥 미세먼지는 동시에 퍼짐!
  • 기존 map을 복사한 newmap에서 로직 처리 후, 매핑하는 방식으로 처리
• ❌ 4방향 중 확산 불가능한 경우 고려
  • map의 범위를 넘어갈 때
  • 현재 미세먼지 양이 5보다 적을 때
  • 다음 위치에 공기 청정기가 위치할 때
• 주변으로 확산, 남은 미세먼지 양 처리

for (pos newdust: isAvailable) {
	int dx = newdust.x;
	int dy = newdust.y;
	newmap[dx][dy] += currD / 5;	// 미세먼지가 주변으로 퍼짐
}
// 남은 미세먼지 양
newmap[cx][cy] -= (currD / 5) * isAvailable.size();

4-2. clean 함수
void clean(pos position, int[][] direction, int bx)

• position : 위쪽, 아래쪽 공기 청정기
• direction : 시계 방향, 반시계 방향
• bx : x의 바운더리

• 현재 위치 (cx, cy) / 다음 위치 (nx, ny)
  • 현재 위치가 공기청정기이면, 미세먼지가 사라지기 때문에 다음 위치는 0으로 초기화 됨
  • 공기 청정기가 아닐 땐, 다음 위치를 현재 위치로 한칸씩 땡겨오면서 회전함
• 경계를 만나면 회전 방향 바꿔줌
  • 시계 방향 : 상 -> 우 -> 하 -> 좌
  • 반시계 방향 : 하 -> 우 -> 상 -> 좌
• 회전을 마쳤다면 시작점 오른쪽 칸에 0 대입
  • 미세먼지 념념굿

4-3. getDust 함수

• 미세먼지 위치를 체크하기 위한 함수
• 맵 요소가 0보다 크면, 미세먼지라는 의미
• ArrayList에 담아서 리턴

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_17144_미세먼지안녕 {
	public static class pos{
		int x, y;

		public pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "pos [x=" + x + ", y=" + y + "]";
		}
	}
	
	public static int R, C;
	
	public static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};	// 시계방향
	public static int[][] antidir = {{-1,0},{0,1},{1,0},{0,-1}}; // 반시계 방향
	
	public static int[][] map;
	public static ArrayList<pos> dusts;
	
	public static pos up, down; // up : 위쪽 공기청정기 위치, down : 아래쪽 공기청정기 위치
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];			// map : 격자판의 입력을 받기위한 리스트
		dusts = new ArrayList<>();		// dusts : 미세먼지 위치를 저장할 리스트
		
		for (int i=0; i<R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				if (map[i][j] == -1) {			// 공기 청정기 위치 저장
					if (up == null) {			// up : 위쪽 공기 청정기
						up = new pos(i,j);
					} else {
						down = new pos(i,j);	// down : 아래쪽 공기 청정기
					}
				} 
				else if (map[i][j] > 0) {		// 미세먼지 위치 저장
					dusts.add(new pos(i,j));
				}
			}
		}
		
		while (T-- > 0) {	
			spread();	// 미세먼지 확산
			getDust();
			
			clean(up, antidir, 0);	// 위쪽 공기 청정기 
			clean(down, dir, R-1);	/// 아래쪽 공기 청정기
			getDust();	
		}
		
		int answer = count();	// 남아있는 미세먼지 양 출력
		bw.write(answer+"\n");
		bw.flush();
	}

	private static void getDust() {
		// [미세먼지 위치 체크]
		dusts = new ArrayList<>();
		
		for (int i=0; i<R; i++) {
			for (int j=0; j<C; j++) {
				if (map[i][j] > 0) {
					dusts.add(new pos(i,j));
				}
			}
		}
	}

	private static void spread() {   
		// [미세먼지 동시에 퍼짐]
		int[][] newmap = new int[R][C];
		for (int i=0; i<R; i++) {
			newmap[i] = Arrays.copyOf(map[i], map[i].length);
		}
		
		for (pos dust : dusts) {
			ArrayList<pos> isAvailable = new ArrayList<>();
			int cx = dust.x, cy = dust.y, currD = map[cx][cy];
			for (int d=0; d<4; d++) {
				int nx = cx + dir[d][0];
				int ny = cy + dir[d][1];
				
				if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
				if (currD < 5 || map[nx][ny] == -1) continue;	
				// 현재 위치 미세먼지 양이 5보다 적거나, 확산될 위치가 공기청정기가 있는 곳이면 확산이 일어나지 않음
				
				isAvailable.add(new pos(nx, ny));
				// 확산 가능한 경우 체크
			}
			
			for (pos newdust: isAvailable) {
				int dx = newdust.x;
				int dy = newdust.y;
				newmap[dx][dy] += currD / 5;	// 미세먼지가 주변으로 퍼짐
			}
			// 남은 미세먼지 양
			newmap[cx][cy] -= (currD / 5) * isAvailable.size();
		}
		// 기존 map에 적용
		map = newmap;
	}

	private static void clean(pos position, int[][] direction, int bx) {
		// [공기청정기 작동]
		// position : 위쪽, 아래쪽 공기 청정기
		// direction : 시계 방향, 반시계 방향
		// bx : x의 바운더리
		
		int di = 0;
		int cx = position.x, cy = position.y;
		int nx = cx + direction[di][0], ny = cy + direction[di][1];
		
		while (true) {
			if (map[cx][cy] == -1) map[nx][ny] = 0;
			else {
				map[cx][cy] = map[nx][ny];
			}
			
			// 경계에 도착하면 방향 바꿔줌
			if ((nx == bx && ny == 0) || (nx == bx && ny == C-1) || (nx == position.x && ny == C-1)) { di++; cx = nx; cy = ny; }
			else {
				cx += direction[di][0];
				cy += direction[di][1];
			}
			
			nx = cx + direction[di][0];
			ny = cy + direction[di][1];
			
			
			if (nx == position.x && ny == position.y) { map[nx][ny+1] = 0; break; }
		}
	}

	private static int count() {
		// [남은 미세먼지 양 체크]
		int cnt = 0;
		for (pos d: dusts) {
			cnt += map[d.x][d.y];
		}
		return cnt;
	}
	
	
	private static void printmap() {
		for (int[] row: map) {
			for (int col: row) {
				System.out.printf("%2d ",col);
			}
			System.out.println();
		}
		System.out.println();
	}
}