Algorithm/Problem
미세먼지 안녕!(BJ_G4_17144)
당진개발자
2024. 2. 27. 23:07
1. 문제 링크
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
2. 나의 코드
메모리: 118100KB
시간: 384ms
코드 길이: 4732B
시간 복잡도 : O(N^2)
설명
- 리스트에 미세먼지 정보들을 저장
- 사방탐색 후 확산
- 바람의 방향을 미리 저장하여 공기청정기 가동
- 마지막으로 다시 맵을 탐색하여 리스트에 미세먼지 정보를 넣는다.import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class BJ_17144 {
static class Dust {
int r, c, n;
public Dust(int r, int c, int n) {
this.r = r;
this.c = c;
this.n = n;
}
}
// 상 하 좌 우
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int[] topD = {0, 3, 1, 2}; // 위에 있는 공기청정기 방향
static int[] bottomD = {1, 3, 0, 2}; // 아래 있는 공기청정기 방향
static Point topM; // 위쪽 공기 청정기 좌표
static Point bottomM; // 아래쪽 공기 청정기 좌표
static int R, C, T, result;
static int[][] map;
static List<Dust> dustList;
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];
dustList = new ArrayList<>();
boolean flag = false;
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
int num = Integer.parseInt(st.nextToken());
if (num == -1 && !flag) {
map[i][j] = -1;
topM = new Point(i, j);
flag = true;
continue;
} else if (num == -1 && flag) {
map[i][j] = -1;
bottomM = new Point(i, j);
continue;
}
if (num != 0) {
dustList.add(new Dust(i, j, num));
} else {
map[i][j] = num;
}
}
}
while (T-- > 0) {
diffusion(); // 확산
wind(); // 공기 청정기 바람
findDust(); // 미세먼지 찾기
}
System.out.println(result);
}
private static boolean isValid(int r, int c) {
return 0 <= r && r < R && 0 <= c && c < C;
}
private static void wind() {
// 위쪽 바람 처리
int nowX = topM.x - 1;
int nowY = topM.y;
int nowD = 0;
while (true) {
int nr = nowX + dr[topD[nowD]];
int nc = nowY + dc[topD[nowD]];
if (!isValid(nr, nc) || nr > topM.x) {
nowD = (nowD + 1) % 4;
continue;
}
if (nr == topM.x && nc == topM.y) break;
map[nowX][nowY] = map[nr][nc];
nowX = nr;
nowY = nc;
}
map[topM.x][topM.y + 1] = 0;
// 아래쪽 바람 처리
nowX = bottomM.x + 1;
nowY = bottomM.y;
nowD = 0;
while (true) {
int nr = nowX + dr[bottomD[nowD]];
int nc = nowY + dc[bottomD[nowD]];
if (!isValid(nr, nc) || nr < bottomM.x) {
nowD = (nowD + 1) % 4;
continue;
}
if (nr == bottomM.x && nc == bottomM.y) break;
map[nowX][nowY] = map[nr][nc];
nowX = nr;
nowY = nc;
}
map[bottomM.x][bottomM.y + 1] = 0;
}
private static void diffusion() {
map = new int[R][C];
map[topM.x][topM.y] = -1;
map[bottomM.x][bottomM.y] = -1;
for (Dust now : dustList) {
int diffusionCnt = 0; // 확산한 수
for (int d = 0; d < 4; d++) {
int nr = now.r + dr[d];
int nc = now.c + dc[d];
if (isValid(nr, nc) && map[nr][nc] != -1 && now.n / 5 >= 1) {
map[nr][nc] += now.n / 5;
++diffusionCnt;
}
}
map[now.r][now.c] += now.n - now.n / 5 * diffusionCnt;
}
}
private static void findDust() {
dustList = new ArrayList<>();
int sumDust = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (map[i][j] != 0 && map[i][j] != -1) {
dustList.add(new Dust(i, j, map[i][j]));
sumDust += map[i][j];
}
}
}
result = sumDust;
}
}
3. 정답 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int R, C, T;
static int[] aircon;
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
static int[][] map;
public static void main(String[] args) throws Exception {
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];
aircon = new int[2];
int airconIdx = 0;
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 (map[i][j] == -1) {
aircon[airconIdx++] = i;
}
}
}
play();
int answer = calculate();
System.out.println(answer);
}
private static void play() {
for (int time = 0; time < T; time++) {
diffusion();
operate();
}
}
// 미세먼지가 확산된다
private static void diffusion() {
int[][] newMap = new int[R][C];
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
// 미세먼지가 있는 칸인 경우
if (map[r][c] > 0) {
int cnt = 0;
int dust = map[r][c] / 5;
for (int dir = 0; dir < 4; dir++) {
int nr = r + dr[dir];
int nc = c + dc[dir];
// 인접한 방향에 칸이 있고, 공기청정기가 없는 경우
if (isIn(nr, nc) && map[nr][nc] > -1) {
newMap[nr][nc] += dust;
cnt++;
}
}
newMap[r][c] += map[r][c] - dust * cnt;
}
}
}
newMap[aircon[0]][0] = -1;
newMap[aircon[1]][0] = -1;
map = newMap;
}
// 공기청정기가 작동한다
private static void operate() {
for (int idx = 0; idx < 2; idx++) {
int r = aircon[idx];
// 공기청정기 위쪽 작동
if (idx == 0) {
int dir = 0;
int nr = r + dr[dir];
int nc = dc[dir];
while (true) {
// 공기청정기로 돌아올 경우
if (nr == r && nc == 0) {
break;
}
// 맵 밖으로 방향을 벗어나는 경우 방향 전환
if (!isIn(nr, nc) || nr > r) {
nr -= dr[dir];
nc -= dc[dir];
dir += 1;
nr += dr[dir];
nc += dc[dir];
continue;
}
// 먼지의 이동 방향이 공기청정기가 아닌 경우
if (!(nr - dr[dir] == r && nc - dc[dir] == 0)) {
map[nr - dr[dir]][nc - dc[dir]] = map[nr][nc];
}
map[nr][nc] = 0;
// 먼지 탐색 이동
nr += dr[dir];
nc += dc[dir];
}
// 공기청정기 아래쪽 작동
} else {
int dir = 2;
int nr = r + dr[dir];
int nc = dc[dir];
while (true) {
// 공기청정기로 돌아올 경우
if (nr == r && nc == 0) {
break;
}
// 맵 밖으로 방향을 벗어나는 경우 방향 전환
if (!isIn(nr, nc) || nr < r) {
nr -= dr[dir];
nc -= dc[dir];
dir = (dir + 3) % 4;
nr += dr[dir];
nc += dc[dir];
continue;
}
// 먼지의 이동 방향이 공기청정기가 아닌 경우
if (!(nr - dr[dir] == r && nc - dc[dir] == 0)) {
map[nr - dr[dir]][nc - dc[dir]] = map[nr][nc];
}
map[nr][nc] = 0;
// 먼지 탐색 이동
nr += dr[dir];
nc += dc[dir];
}
}
}
}
// 미세먼지 총량 계산
private static int calculate() {
int sum = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (map[i][j] > 0) {
sum += map[i][j];
}
}
}
return sum;
}
private static boolean isIn(int r, int c) {
return r >= 0 && c >= 0 && r < R && c < C;
}
}
4. 배운 점
- 쓸데 없는 리스트는 만들지 않는게 더 좋을 것 같다. (메모리를 많이 잡아 먹는다.)
- 맵 복사를 사용하는 방법도 괜찮은 것 같다.