백준 17144 미세먼지 안녕! - 삼성 SW 역량 테스트 기출

백준 17144 미세먼지 안녕! - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

17144번: 미세먼지 안녕!

 

2. 문제 해결에 대한 아이디어

1. 공기 청정기가 위 아래에서 각각 공기를 정화한다. 따라서 위와 아래를 따로 구현했다.

2. 먼지 확산은 copyBoard에 기록하고 다시 원래 board에 대입했다. (copyBoard에 공기청정기 표시해야함)

3. 먼지의 이동(공기 청정)은 먼지의 이동 방향과 역방향으로 접근해서 한 칸씩 이동시켰다.

   . 한 칸씩 이동 시킬 때, 바람이 나오는 위치에서 이동해오는 경우를 신경 써야 한다.

   . 이동해오는 칸이 공기청정기(-1)인 경우, 빈칸(0)으로 두었다.

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static class Pair {
		int y, x;

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

	}

	static int[][] board;
	static int[][] copyBoard;
	static int R, C, T;
	static Pair upPuri;
	static Pair downPuri;
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static int totalDust = 0;

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

//		BufferedReader br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\미세먼지안녕_17144\\input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] rct = br.readLine().split(" ");
		R = Integer.parseInt(rct[0]);
		C = Integer.parseInt(rct[1]);
		T = Integer.parseInt(rct[2]);

		board = new int[R][C];

		for (int i = 0; i < R; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < C; j++) {
				board[i][j] = Integer.parseInt(line[j]);
				if (board[i][j] == -1) {
					if (upPuri == null) {
						upPuri = new Pair(i, j);
					} else {
						downPuri = new Pair(i, j);
					}
				}
			}
		}

		while (T-- > 0) {
			// 먼지 확산 후의 상태 저장
			makeCopy();
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if (board[i][j] != 0 && board[i][j] != -1) {
						dustSpread(i, j);
					}
				}
			}
			// 원래 보드로 돌려놓기
			copyToOrigin();
			// 공기 청정
			upWind();
			downWind();

		}
		count();
		System.out.println(totalDust);

	}

	public static void makeCopy() {
		copyBoard = new int[R][C];
		copyBoard[upPuri.y][upPuri.x] = -1;
		copyBoard[downPuri.y][downPuri.x] = -1;
	}

	public static void dustSpread(int y, int x) {
		// copy에다 해야함
		int dirCnt = 0;
		int originDust = board[y][x];
		int partDust = originDust / 5;
		for (int i = 0; i < 4; i++) {
			int yy = y + dirY[i];
			int xx = x + dirX[i];

			if (yy >= R || xx >= C || yy < 0 || xx < 0 || board[yy][xx] == -1)
				continue;

			++dirCnt;
			copyBoard[yy][xx] += partDust;
		}
		copyBoard[y][x] += board[y][x] - dirCnt * partDust;
	}

	public static void downWind() {
		// 공기청정기로 사라지는 먼지부터 계산
		int y = downPuri.y;
		int x = downPuri.x;

		while (true) { // 아래에서 공청 행으로
			if (y == R - 1) {
				break;
			}
			if (board[y][x] != -1) { // 현재칸이 공청기가 아닐때만 먼지 옮김
				board[y][x] = board[y + 1][x];
			}
			++y;
		}

		// (R - 1, 0)에서 시작
		while (true) { // 오른쪽에서 왼쪽으로
			if (x == C - 1) {
				break;
			}
			board[y][x] = board[y][x + 1];
			++x;
		}

		// (R - 1, c - 1)
		while (true) { // 공청 행에서 아래로
			if (y == downPuri.y) {
				y = downPuri.y;
				break;
			}
			board[y][x] = board[y - 1][x];
			--y;

		}

		// (downPuri.y, C - 1)
		while (true) { // 왼쪽에서 오른쪽으로
			if (x == downPuri.x) {
				break;
			}
			if (board[y][x - 1] != -1)
				board[y][x] = board[y][x - 1];
			else
				board[y][x] = 0;
			--x;
		}

	}

	public static void upWind() {
		// 공기청정기로 사라지는 먼지부터 계산
		int y = upPuri.y;
		int x = upPuri.x;

		while (true) { // 위에서 공청으로
			if (y == 0) {
				break;
			}
			if (board[y][x] != -1) { // 정화가 아닐때만 다음칸의 먼지 옮김
				board[y][x] = board[y - 1][x];
			}
			--y;
		}

		// (0, 0)에서 시작
		while (true) { // 오른쪽에서 왼쪽으로
			if (x == C - 1) {
				break;
			}
			board[y][x] = board[y][x + 1];
			++x;
		}

		// (0, c - 1)
		while (true) { // 공청에서 위로
			if (y == upPuri.y) {
				y = upPuri.y;
				break;
			}
			board[y][x] = board[y + 1][x];
			++y;

		}

		// (upPuri.y,C - 1)
		while (true) { // 왼쪽에서 오른쪽으로
			if (x == upPuri.x) {
				break;
			}
			if (board[y][x - 1] != -1)
				board[y][x] = board[y][x - 1];
			else
				board[y][x] = 0;
			--x;
		}

	}

	public static void copyToOrigin() {
		board = new int[R][C];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				board[i][j] = copyBoard[i][j];
			}
		}
	}

	public static void count() {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (board[i][j] != 0 && board[i][j] != -1)
					totalDust += board[i][j];
			}
		}

	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 먼지의 움직임을 구현하는데 시간이 살짝 걸린 느낌이다. 아직 익숙하지 않은 것 같다.

2. 삼성 유형에서는 board, copyBoard를 이용하는 많이 나오는 것 같다. 이를 잘 판단해야겠다.