17144 - 미세먼지 안녕(G4)

블랑·2023년 3월 3일
0

BOJ

목록 보기
2/11

문제

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

풀이

시뮬레이션 문제로, 사방탐색을 제외하면 별도의 특별한 알고리즘은 사용하지 않았다.
대개 헷갈릴 부분이 '미세먼지의 확산'을 구현하는 것이라고 생각되는데, 완전탐색으로 해당 기능을 수행하면 확산이 동시에 일어나는 것이 아니라, 이전 확산 값에 영향을 받는다.

이러한 문제를 해결하기 위해
1. 미세먼지 클래스를 생성 후, 완전탐색으로 조건에 맞는 미세먼지 객체를 생성하여 큐에 저장한다.
2. map(2차원 배열)의 값들을 전부 0으로 초기화하였다. 영향을 받게 하지 않기 위함으로, Dust Class의 내부 메서드로 확산량을 계산 후 값을 더해주는 방식으로 영향을 받지 않게 하였다.
3. 이후 자체 메서드로 구현한 바람으로 인한 shift 기능을 수행한다.

자세한 내용은 소스 코드 주석을 읽으면 이해하기 쉬울 것이다.

소스 코드


import java.util.*;
import java.io.*;

/*
 * 1. 미세먼지 확산 구현 : 
 * 4방 탐색(OFI, 공기청정기 배제) 
 * 확산량 : n / 5
 * 원래 자리 : 기존값 - 확산량*(확산된 방향 개수)
 * -> 확산은 모든 위치에서 동시에 일어난다. queue에 좌표, 중앙값, (4방 체크 후)확산량을 집어넣어야 할 것이다
 * 
 * 2. 공기정청기 
 * 바람이 불면 미세먼지가 바람 방향대로 이동
 * 위쪽 : 시계방향 순환
 * 아래쪽 : 반시계방향 순환
 * 공기청정기로 이동한 먼지는 제거;
 * 바람 알고리즘 구현
 * 
 * 
 */

public class BOJ_17144_미세먼지안녕_G4 {
	static int R, C, T; //입력값
	static int[] cleaner = new int[2]; //0 = r, 1 = c
	static int map[][];
	static Queue<Dust> dustQ = new ArrayDeque<>();

	public static void main(String[] args) throws IOException {
		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());

		map = new int[R][C];
		boolean check = false;
		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(!check && map[i][j] == -1) { 
					cleaner[0] = i;
					cleaner[1] = j;
					check = !check;
				}
			}
		}
		
		//T초만큼 반복
		while(T-- > 0) {
			blowDust(); //확산
			//공기청정기 가동(위)
			wind(cleaner[0], cleaner[1], new int[][] {{0, 1}, {-1, 0}, {0, -1}, {1, 0}});	
			
			//공기청정기 가동(아래)
			wind(cleaner[0] + 1, cleaner[1], new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}});	
		}
		
		int res = 2; //공기청정기 두 칸(-2) 더할 것임.
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				res += map[i][j];
			}
		}
		System.out.println(res);
	}



	private static void wind(int r, int c, int[][] shift) {
		int cnt = 0;	//방향 스위치 및 종료 트리거
		int save = 0; 	//현재 미세먼지 값 저장
		int last = 0; 	//이전 미세먼지 값 저장
	
		while(cnt != 4) {
			r += shift[cnt][0];
			c += shift[cnt][1];
			
			//만약 이동한 칸이 존재하지 않거나, 공기청정기라면
			if(OutOfIdx(r, c)) {
				r -= shift[cnt][0]; //이전 인덱스로 복귀
				c -= shift[cnt][1];
				cnt += 1; //다음 방향으로 전환
				continue;
			}
			
			save = map[r][c]; //현재 좌표 값을 저장
			map[r][c] = last; //현재 좌표에 이전 값을 넣음
			last = save;	  //현재 값을 이전 값으로 변경
		}
	}



	private static void blowDust() {
		//값 읽어들임
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				int now = map[i][j];
				if(now == 0 || now == -1) continue;  	//빈 자리나 공기청정기일 경우 스킵
				dustQ.offer(new Dust(i, j, now)); 		//저장
				map[i][j] = 0;	//초기화
			}
		}
		
		//읽어들인 값을 기반으로 전파 실행
		while(!dustQ.isEmpty()) {
			dustQ.poll().dustSet();
		}
	}



	static class Dust {
		/*
		 * * 1. 미세먼지 확산 구현 : 4방 탐색(OFI, 공기청정기 배제) 
		 * 확산량 : n / 5 원래 자리 : 기존값 - 확산량*(확산된 방향 개수) 
		 * -> 확산은 모든 위치에서 동시에 일어난다. queue에 좌표, 중앙값, (4방 체크 후)확산량을 집어넣어야 할 것이다
		 */
		
		int r, c, value, moveVal;
		
		public Dust(int r, int c, int value) {
			this.r = r;
			this.c = c;
			this.value = value;
			moveVal = value / 5;
		}

		private void dustSet() {
			int shift[][] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
			int cnt = 0;
			for (int i = 0; i < shift.length; i++) {
				int nr = r + shift[i][0];
				int nc = c + shift[i][1];
				
				if(OutOfIdx(nr, nc)) continue;
				map[nr][nc] += moveVal; //미세먼지 전파
				cnt++;
			}
			value -= moveVal * cnt; //확산 후 남은 값
			map[r][c] += value; 	//원래 자리에 남은 값 더해줌.
		}
	}
	
	static boolean OutOfIdx(int r, int c) {
		if(r < 0 || c < 0 || r >= R || c >= C || map[r][c] == -1) {
			return true;
		}
		return false;
	}
}
profile
안녕하세요.

0개의 댓글