문제
17144번: 미세먼지 안녕! (acmicpc.net)
해결방법
- 미세먼지의 확산과 공기청정기 바람의 회전 두가지를 구현하는 문제이다.
- 미세먼지의 확산
- 미세먼지가 있는 위치에서 주변 4방향으로 미세먼지를 확산시킨다.
- 이 때 기존의
map에 미리 더해버리게 되면 기존의 값에서 확산을 시키는게 아니라 더해진 값에서 확산을 시키므로 더한 값들은tmp에 저장해 놓고 모든 확산을 마친 후tmp의 값을map에 더해준다.
- 공기청정기 바람의 회전
- 공기청정기 위쪽 부분은 반시계 방향, 아래쪽 부분은 시계 방향으로 단순히 회전 시키기만 하면 된다.
- 눈에 보이는 단순한 구현 문제라서 크게 어려움은 없다.
동작과정
map에 입력된 정보들을 저장하며 이 때 공기청정기의 위쪽 부분의i값을 기억해 놓는다.T만큼 반복문을 수행하며 먼저 미세먼지를 확산시키고 바람에 의해 미세먼지를 회전시킨다.- 미세먼지 확산은 배열을 완전 탐색하며 미세먼지가 있는 곳에서 확산 할 수 있는 곳으로 확산시킨다.
- 미세먼지 회전은 정해진 방향대로 미세먼지를 회전시키고 공기청정기 부분에는 영향을 주지 않도록 한다.
- 마지막에 배열을 모두 탐색하여 값을 더하는데 이 때 공기청정기를 나타내는 부분이 총 -2를 시키므로
sum의 초기 값을 2로한다.
코드
package com.ssafy.ws.problem;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
/*
* 단순한 구현 문제
* 미세먼지의 확산과 회전 두가지만 구현하면 된다.
*/
public class Main {
private final static int[][] D = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static int R, C, T;
private static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(in.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
map = new int[R][C];
int cleaner = -1;
// 입력을 받으며 공기청정기의 위치중 위의 i 값을 저장한다.
for(int i = 0; i < R; i++) {
st = new StringTokenizer(in.readLine());
for(int j = 0; j < C; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == -1 && cleaner == -1)
cleaner = i;
}
}
// T만큼 확산, 회전을 반복함
for(int i = 0; i < T; i++) {
spread();
rotate(cleaner);
}
// 공기청정기 위치를 나타내는 -1이 두개 있으므로 초기 값을 2로 하고 배열의 모든 값을 더해줌
int sum = 2;
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++)
sum += map[i][j];
}
out.write(sum+"");
out.flush();
}
// 미세먼지 확산
private static void spread() {
// 확산된 값들을 가지고 있을 tmp
int[][] tmp = new int[R][C];
// map을 완전 탐색
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++) {
// 미세먼지가 존재할 경우
if(map[i][j] > 0) {
// 확산된 먼지들을 빼주기 위한 sum, 확산될 값 value
int sum = 0;
int value = map[i][j] / 5;
// 4방향을 탐색하여 범위 안이고 공기청정기가 아니라면 미세먼지 확산
for(int d = 0; d < 4; d++) {
int dy = i + D[d][0];
int dx = j + D[d][1];
// map에 바로 반영을 하면 해당 칸에서 확산을 할 때 원래 값으로 하지않고 확산된 먼지가 추가된 값으로 확산을 진행하기 때문에 tmp에 저장해놓음
if(isInBound(dy, dx) && map[dy][dx] != -1) {
tmp[dy][dx] += value;
sum += value;
}
}
// i, j에 해당하는 값은 더이상 확산이 없기 때문에 나가는 먼지는 바로 반영
map[i][j] -= sum;
}
}
}
// tmp 에 저장되어 있는 확산된 값들을 모두 더해준다.
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++)
map[i][j] += tmp[i][j];
}
}
// 공기청정기 바람에 의해 미세먼지들을 회전
private static void rotate(int p) {
// 위쪽 회전 진행
// p의 위치에서 순서대로 오른쪽 끝까지, 위쪽 끝까지, 왼쪽 끝까지, 공기청정기 바로 위쪽 까지 회전을 진행한다.
int y = p;
int x = 1;
// 처음 값은 공기청정기 바로 오른쪽 이므로 0
int tmp = map[y][x];
map[y][x] = 0;
// 오른쪽으로
while(x+1 < C) {
int next = map[y][++x];
map[y][x] = tmp;
tmp = next;
}
// 위로
while(y-1 >= 0) {
int next = map[--y][x];
map[y][x] = tmp;
tmp = next;
}
// 왼쪽으로
while(x-1 >= 0) {
int next = map[y][--x];
map[y][x] = tmp;
tmp = next;
}
// 아래로
while(y+1 < p) {
int next = map[++y][x];
map[y][x] = tmp;
tmp = next;
}
// 아래쪽 회전 진행
// p의 위치에서 순서대로 오른쪽 끝까지, 아래쪽 끝까지, 왼쪽 끝까지, 공기청정기 바로 아래쪽 까지 회전을 진행한다.
y = p+1;
x = 1;
// 처음 값은 공기청정기 바로 오른쪽 이므로 0
tmp = map[y][x];
map[y][x] = 0;
// 오른쪽으로
while(x+1 < C) {
int next = map[y][++x];
map[y][x] = tmp;
tmp = next;
}
// 아래으로
while(y+1 < R) {
int next = map[++y][x];
map[y][x] = tmp;
tmp = next;
}
// 왼쪽으로
while(x-1 >= 0) {
int next = map[y][--x];
map[y][x] = tmp;
tmp = next;
}
// 위로
while(y-2 > p) {
int next = map[--y][x];
map[y][x] = tmp;
tmp = next;
}
}
// 경계 확인
private static boolean isInBound(int y, int x) {
return y >= 0 && y < R && x >= 0 && x < C;
}
}
성장 중