문제출처
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼
www.acmicpc.net
문제풀이
그냥 진짜 구현하는 문제다. 빡구현까지는 아니고 배열 조정을 하느라 약간 머리가 아픈 문제
문제에 나온대로 확산과 공기청정기 순환 2가지로 나눠서 구현하면 된다.
spreadDust() 메서드
확산은 tempMap배열을 이용해 구현했다. 확산은 queue를 이용해도 될것같다.
확산과 같은 경우 인접한 공간에 숫자가 있는경우 어떻게 처리하는지가 중요하다. 한 공간(y, x)를 기준으로 인접한 공간에 값이 없다면 그냥 4방향으로 확산시켜주면 되지만, 한 방향이라도 있는 경우 다음 탐색을 할때 영향을 주기 때문이다. 즉, 우리는 순차적으로 한 공간(y, x)에 대해 확산시키는 소스를 구현하지만 문제는 한순간에 확산하기 때문에 영향을 받기전의 값으로 확산을 시켜야 한다.
1. map을 tempMap에 복사하여 원래의 미세먼지 값들을 저장.
2. 확산될 먼지의 양은 원본map을 통해 계산
3. tempMap에서 먼지를 확산시킴
4. tempMap에서 확산시킨 것들 다시 map으로 옮김.
activateAirCleaner() 메서드
이 부분은 공기청정기를 작동시키는 메서드이다. 기존 입력을 받을때 따로 list에 저장해둔 공기청정기의 y좌표를 이용해 map배열의 값을 옮겨주면 된다. 공기청정기에 들어가는 먼지는 없어진다는 조건을 활용해서 없어지는 좌측부터 하나씩 값을 옮겨주었다. 여기서 주의할 점은 공기청정기가 위치한 y좌표의 x축을 이동시킬때 모두 이동시키고 공기청정기 다음x좌표를 0으로 다시 갱신해줘야 한다는 것이다.
소스코드
https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_17144/boj17144.java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
private static int r, c, t;
private static int dy[] = {0, -1, 0, 1};
private static int dx[] = {1, 0, -1, 0};
private static int map[][];
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static ArrayList<Integer> cleaner;
public static void main(String[] args) throws Exception {
init();
while (true) {
t--;
spreadDust();
activateAirCleaner();
if (t == 0) {
System.out.println(countDustVolumn());
break;
}
}
}
private static int countDustVolumn() {
int ret = 0;
for (int y=0; y<r; y++) {
for (int x=0; x<c; x++) {
if (map[y][x] != 0 && map[y][x] != -1) ret += map[y][x];
}
}
return ret;
}
private static void copyMap(int src[][], int dest[][]) {
for (int y=0; y<r; y++) {
for (int x=0; x<c; x++) {
dest[y][x] = src[y][x];
}
}
}
private static void activateAirCleaner() {
int upY = cleaner.get(0);
int downY = cleaner.get(1);
// 위쪽
for (int y=upY-1; y>0; y--) {
map[y][0] = map[y-1][0];
}
for (int x=0; x<c-1; x++) {
map[0][x] = map[0][x+1];
}
for (int y=0; y<upY; y++) {
map[y][c-1] = map[y+1][c-1];
}
for (int x=c-1; x>0; x--) {
map[upY][x] = map[upY][x-1];
}
map[upY][1] = 0;
// 아래쪽
for (int y=downY+1; y<r-1; y++) {
map[y][0] = map[y+1][0];
}
for (int x=0; x<c-1; x++) {
map[r-1][x] = map[r-1][x+1];
}
for (int y=r-1; y>=downY; y--) {
map[y][c-1] = map[y-1][c-1];
}
for (int x=c-1; x>1; x--) {
map[downY][x] = map[downY][x-1];
}
map[downY][1] = 0;
}
private static void spreadDust() {
int tempMap[][] = new int[r][c];
copyMap(map, tempMap);
for (int y=0; y<r; y++) {
for (int x=0; x<c; x++) {
if (map[y][x] != 0 && map[y][x] != -1) {
int count = 0;
int dust = map[y][x] / 5;
for (int i=0; i<4; i++) {
int ny = y+dy[i];
int nx = x+dx[i];
if (ny<0 || nx<0 || ny>=r || nx>=c || map[ny][nx] == -1) continue;
tempMap[ny][nx] += dust;
count++;
}
tempMap[y][x] -= (count * dust);
}
}
}
copyMap(tempMap, map);
}
private static void init() throws Exception {
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];
cleaner = new ArrayList<>();
for (int y=0; y<r; y++) {
st = new StringTokenizer(br.readLine(), " ");
for (int x=0; x<c; x++) {
map[y][x] = Integer.parseInt(st.nextToken());
if (map[y][x] == -1) cleaner.add(y);
}
}
}
}
'Algorithm' 카테고리의 다른 글
| [프로그래머스 17681 - 카카오 2018 1차] 비밀지도 (2) | 2020.04.29 |
|---|---|
| [BOJ 16234] 인구 이동 (0) | 2020.04.27 |
| [BOJ 14500] 테트노미로 (0) | 2020.04.24 |
| [BOJ 10819] 차이를 최대로 (0) | 2020.04.21 |
| [BOJ 16236] 아기상어 (0) | 2020.04.21 |