문제

17144번 : 미세먼지
Lv: 골드 4

문제를 요약하자면 아래 과정을 T만큼 반복하라는 것이다.
1. 미세먼지를 확장하고
2. 공기청정기를 돌린다.

초기 접근

이 문제를 처음 봤을 때는
1. 미세먼지 확장
미세먼지를 확장하는 것은 bfs로 돌면서 하면 된다고 생각하고,
2. 공기청정기 돌린다
공기청정기는 dfs로 돌리면 된다고 생각했다.

그러나 gpt에게 물어보니 둘 다 반복문을 돌면서 푸는 것이 더 효율적이라고 했다.

격자판의 범위와 T의 범위를 고려해보았을 때 완전탐색으로 해도 충분하다는 이야기였다.

코드 흐름

1. 미세먼지, 공기청정기를 T만큼 반복

		// T만큼 반복
		for (int t = 0; t < T; t++) {
			// 미세먼지 확산
			board = spread();

			// 공기청정기 작동
			airCleaner();
		}

2. 미세먼지 확장 메서드 : spread()

확장된 미세먼지를 저장할 새로운 이차원 배열 newBoard를 생성하고 이를 반환한다.

2차원 배열을 완전탐색으로 돌면서 미세먼지를 확장해나가는 로직이다.

	private static int[][] spread() {
		int[][] newBoard = new int[R][C];
		
		//공기청정기 위치 복사
		newBoard[air.get(0)[0]][air.get(0)[1]] = -1;
		newBoard[air.get(1)[0]][air.get(1)[1]] = -1;
	
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (board[i][j] > 0) {
					int spreadAmount = board[i][j] /5;
					int cnt = 0;
					
					//확산된 먼지를 newBoard에 누적
					for (int k = 0; k < 4; k++) {
						int nx = i + di[k];
						int ny = j + dj[k];
						if (nx >= 0 && nx < R && ny >= 0 && ny < C && board[nx][ny] != -1) {
							newBoard[nx][ny] += spreadAmount;
							cnt += 1;
						}
					}
					//남은 미세먼지를 newBoard에 더함
					newBoard[i][j] += board[i][j] - spreadAmount * cnt;
				}

			}
		}
		return newBoard;

	}

3. 공기청정기 메서드 : airCleaner()

상단 공기청저기는 반시계방향으로,
하단 공기청정기는 시계방향으로 돌기 때문에
로직을 따로따로 처리하다보니 코드가 굉장히 길어졌다.

로직은 간단하게 for문으로 방향을 돌리면서 미세먼지를 한 칸 씩 이동시키면 된다.

이때, 주의해야할 부분은 한 칸 씩 밀리다보면 제일 끝 칸의 미세먼지가 덮어씌워지기 때문에 이를 temp로 저장하고, 다음 방향 때 넘겨주어야 한다.

	private static void airCleaner() {
	    int x1 = air.get(0)[0]; // 상단 공기청정기 행
	    int x2 = air.get(1)[0]; // 하단 공기청정기 행

	    // 1. 상단 공기청정기 (반시계 방향: 우 -> 상 -> 좌 -> 하)
	    
	    // 1-1. 오른쪽 이동 (x1 행)
	    // (x1, C-1) 값을 저장
	    int temp = board[x1][C - 1]; 
	    for (int j = C - 1; j > 1; j--) {
	        board[x1][j] = board[x1][j - 1];
	    }
	    // (x1, 1)은 정화된 바람이 들어옴. (x1, 0)은 -1로 유지
	    board[x1][1] = 0; 
	    
	    // 1-2. 위쪽 이동 (C-1 열)
	    // (0, C-1) 값을 저장
	    int temp2 = board[0][C - 1];
	    for (int i = 0; i < x1 - 1; i++) {
	        board[i][C - 1] = board[i + 1][C - 1];
	    }
	    // 이전 단계 (x1, C-1) 값이 (x1-1, C-1)로 이동
	    board[x1 - 1][C - 1] = temp;
	    temp = temp2; // 다음 단계에서 (0, C-1) 값을 사용
	    
	    // 1-3. 왼쪽 이동 (0 행)
	    // (0, 0) 값을 저장 (0, 0)은 -1이 아님! (0, 0)이 경계
	    temp2 = board[0][0]; 
	    for (int j = 0; j < C - 2; j++) { // j=0부터 C-3까지 (C-2칸 이동)
	        board[0][j] = board[0][j + 1];
	    }
	    // 이전 단계 (0, C-1) 값이 (0, C-2)로 이동
	    board[0][C - 2] = temp;
	    temp = temp2; // (0, 0) 값을 다음 단계에서 사용

	    // 1-4. 아래쪽 이동 (0 열)
	    // (x1-1, 0) 값을 저장 (이동의 끝 지점)
	    temp2 = board[x1 - 1][0]; 
	    for (int i = x1 - 1; i > 1; i--) { // i=x1-1부터 2까지 (x1-2칸 이동)
	        board[i][0] = board[i - 1][0];
	    }
	    // 이전 단계 (0, 0) 값이 (1, 0)으로 이동
	    board[1][0] = temp; 
	    // 공기청정기 (-1)로 미세먼지가 들어간 것은 정화되므로, (x1-1, 0)에 있던 값은 사라짐.

	    // 2. 하단 공기청정기 (시계 방향: 우 -> 하 -> 좌 -> 상)

	    // 2-1. 오른쪽 이동 (x2 행)
	    temp = board[x2][C - 1]; 
	    for (int j = C - 1; j > 1; j--) {
	        board[x2][j] = board[x2][j - 1];
	    }
	    board[x2][1] = 0; 
	    
	    // 2-2. 아래쪽 이동 (C-1 열)
	    temp2 = board[R - 1][C - 1];
	    for (int i = R - 1; i > x2 + 1; i--) { 
	        board[i][C - 1] = board[i - 1][C - 1];
	    }
	    board[x2 + 1][C - 1] = temp;
	    temp = temp2; 
	    
	    // 2-3. 왼쪽 이동 (R-1 행)
	    temp2 = board[R - 1][0];
	    for (int j = 0; j < C - 2; j++) {
	        board[R - 1][j] = board[R - 1][j + 1];
	    }
	    board[R - 1][C - 2] = temp;
	    temp = temp2; 

	    // 2-4. 위쪽 이동 (0 열)
	    // (x2+1, 0) 값을 저장 (이동의 끝 지점)
	    temp2 = board[x2 + 1][0]; 
	    for (int i = x2 + 1; i < R - 1; i++) {
	        board[i][0] = board[i + 1][0];
	    }
	    board[R - 2][0] = temp;
	    // 공기청정기 (-1)로 미세먼지가 들어간 것은 정화되므로, (x2+1, 0)에 있던 값은 사라짐.
	}

배운 점

입력값의 범위를 고려하여 알고리즘을 선택할 것.
bfs, dfs에만 사로잡히지 말고 완전탐색으로도 가능한지를 고려해볼 것

전체코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

//처음에는 bfs로 접근 -> ㄴㄴ 반복문으로 하셈
//공기청정기 튼 거 dfs로 접근 -> ㄴㄴ 반복문으로 하셈
public class backjoon_17144_미세먼지 {

	static int R, C, T;
	static int[][] board;
	static int[] di = { -1, 1, 0, 0 };
	static int[] dj = { 0, 0, -1, 1 };
	static List<int[]> air;

	// 첫번째 공청 방향 우, 상, 좌, 하
	static int[] airDi_1 = { 0, -1, 0, 1 };
	static int[] airDj_1 = { 1, 0, -1, 0 };

	// 두번째 공청 방향 우, 하, 좌, 상
	static int[] airDi_2 = { 0, 1, 0, -1 };
	static int[] airDj_2 = { 1, 0, -1, 0 };

	public static void main(String[] args) throws IOException {

		// R,C,T의 범위를 고려해보았을 때 완전탐색으로 하는 게 나음
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());

		board = new int[R][C];
		air = new ArrayList<>();

		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());
				if (board[i][j] == -1) {
					air.add(new int[] { i, j });
				}
			}
		}

		// T만큼 반복
		for (int t = 0; t < T; t++) {
			// 미세먼지 확산
			board = spread();

			// 공기청정기 작동
			airCleaner();
		}

		// 남아있는 미세먼지의 양을 구하기
		int rest = 0;

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (board[i][j] > 0) {
					
					rest += board[i][j];
				}
				
			}
		}

		System.out.println(rest);

	}

	private static void airCleaner() {
	    int x1 = air.get(0)[0]; // 상단 공기청정기 행
	    int x2 = air.get(1)[0]; // 하단 공기청정기 행

	    // 1. 상단 공기청정기 (반시계 방향: 우 -> 상 -> 좌 -> 하)
	    
	    // 1-1. 오른쪽 이동 (x1 행)
	    // (x1, C-1) 값을 저장
	    int temp = board[x1][C - 1]; 
	    for (int j = C - 1; j > 1; j--) {
	        board[x1][j] = board[x1][j - 1];
	    }
	    // (x1, 1)은 정화된 바람이 들어옴. (x1, 0)은 -1로 유지
	    board[x1][1] = 0; 
	    
	    // 1-2. 위쪽 이동 (C-1 열)
	    // (0, C-1) 값을 저장
	    int temp2 = board[0][C - 1];
	    for (int i = 0; i < x1 - 1; i++) {
	        board[i][C - 1] = board[i + 1][C - 1];
	    }
	    // 이전 단계 (x1, C-1) 값이 (x1-1, C-1)로 이동
	    board[x1 - 1][C - 1] = temp;
	    temp = temp2; // 다음 단계에서 (0, C-1) 값을 사용
	    
	    // 1-3. 왼쪽 이동 (0 행)
	    // (0, 0) 값을 저장 (0, 0)은 -1이 아님! (0, 0)이 경계
	    temp2 = board[0][0]; 
	    for (int j = 0; j < C - 2; j++) { // j=0부터 C-3까지 (C-2칸 이동)
	        board[0][j] = board[0][j + 1];
	    }
	    // 이전 단계 (0, C-1) 값이 (0, C-2)로 이동
	    board[0][C - 2] = temp;
	    temp = temp2; // (0, 0) 값을 다음 단계에서 사용

	    // 1-4. 아래쪽 이동 (0 열)
	    // (x1-1, 0) 값을 저장 (이동의 끝 지점)
	    temp2 = board[x1 - 1][0]; 
	    for (int i = x1 - 1; i > 1; i--) { // i=x1-1부터 2까지 (x1-2칸 이동)
	        board[i][0] = board[i - 1][0];
	    }
	    // 이전 단계 (0, 0) 값이 (1, 0)으로 이동
	    board[1][0] = temp; 
	    // 공기청정기 (-1)로 미세먼지가 들어간 것은 정화되므로, (x1-1, 0)에 있던 값은 사라짐.

	    // 2. 하단 공기청정기 (시계 방향: 우 -> 하 -> 좌 -> 상)

	    // 2-1. 오른쪽 이동 (x2 행)
	    temp = board[x2][C - 1]; 
	    for (int j = C - 1; j > 1; j--) {
	        board[x2][j] = board[x2][j - 1];
	    }
	    board[x2][1] = 0; 
	    
	    // 2-2. 아래쪽 이동 (C-1 열)
	    temp2 = board[R - 1][C - 1];
	    for (int i = R - 1; i > x2 + 1; i--) { 
	        board[i][C - 1] = board[i - 1][C - 1];
	    }
	    board[x2 + 1][C - 1] = temp;
	    temp = temp2; 
	    
	    // 2-3. 왼쪽 이동 (R-1 행)
	    temp2 = board[R - 1][0];
	    for (int j = 0; j < C - 2; j++) {
	        board[R - 1][j] = board[R - 1][j + 1];
	    }
	    board[R - 1][C - 2] = temp;
	    temp = temp2; 

	    // 2-4. 위쪽 이동 (0 열)
	    // (x2+1, 0) 값을 저장 (이동의 끝 지점)
	    temp2 = board[x2 + 1][0]; 
	    for (int i = x2 + 1; i < R - 1; i++) {
	        board[i][0] = board[i + 1][0];
	    }
	    board[R - 2][0] = temp;
	    // 공기청정기 (-1)로 미세먼지가 들어간 것은 정화되므로, (x2+1, 0)에 있던 값은 사라짐.
	}

	private static int[][] spread() {
		int[][] newBoard = new int[R][C];
		
		//공기청정기 위치 복사
		newBoard[air.get(0)[0]][air.get(0)[1]] = -1;
		newBoard[air.get(1)[0]][air.get(1)[1]] = -1;
	
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (board[i][j] > 0) {
					int spreadAmount = board[i][j] /5;
					int cnt = 0;
					
					//확산된 먼지를 newBoard에 누적
					for (int k = 0; k < 4; k++) {
						int nx = i + di[k];
						int ny = j + dj[k];
						if (nx >= 0 && nx < R && ny >= 0 && ny < C && board[nx][ny] != -1) {
							newBoard[nx][ny] += spreadAmount;
							cnt += 1;
						}
					}
					//남은 미세먼지를 newBoard에 더함
					newBoard[i][j] += board[i][j] - spreadAmount * cnt;
				}

			}
		}
		return newBoard;

	}

}