[백준]JAVA - 17144번: 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

풀이

문제에 이해하기 쉽게 설명이 잘 적혀있으니까 생략하겠다.

 

위 문제에서는 두 개의 일이 순서대로 이루어진다.

1. 미세먼지 확산: 4방향으로 먼지가 확산된다.
2. 공기청정기 작동: 위 칸과 아래 칸의 바람이 방향이 서로 다르며 한 칸씩 먼지를 밀어낸다.

 

미세먼지 확산은 dfs 혹은 bfs를 이해하고 있고 관련된 문제를 풀어봤다면 쉽게 해결할 수 있을 것이다.

public static void DustSpread() {
    while (!q.isEmpty()) {
        Position now = q.poll();
			
        if (now.v < 5) continue;
			
        int cnt = 0;
        int DustSpreadV = now.v / 5;
			
        for (int i=0; i<4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
				
            if (nx < 0 || ny < 0 || nx > R-1 || ny > C-1 || map[nx][ny] == -1) continue;
				
            map[nx][ny] += DustSpreadV;
            cnt++;
        }
			
        map[now.x][now.y] -= DustSpreadV * cnt; 
    }
}

4방향으로 한 번씩만 확산이 되기 때문에 visited 처리를 한다거나 queue에 넣을 필요는 없다. 범위를 벗어나는 부분만 신경써주면 된다.

 

공기청정기는 위 칸과 아래 칸의 바람 방향이 다르기 때문에 구분해서 실행해주면 된다. 

public static void AirCleaner() {
    // [위] 아래 
    for (int i=top-1; i>0; i--) {
        map[i][0] = map[i-1][0];
    }
		
    // [위] 왼쪽
    for (int i=0; i<C-1; i++) {
        map[0][i] = map[0][i+1];
    }
		
    // [위] 위
    for (int i=0; i<top; i++) {
        map[i][C-1] = map[i+1][C-1];
    }
		
    // [위] 오른쪽
    for (int i=C-1; i>1; i--) {
        map[top][i] = map[top][i-1];
    }
		
    // [아래] 위로
    for (int i=bot+1; i<R-1; i++) {
        map[i][0] = map[i+1][0];
    }
		
    // [아래] 왼쪽으로
    for (int i=0; i<C-1; i++) {
        map[R-1][i] = map[R-1][i+1];
    }
		
    // [아래] 아래로
    for (int i=R-1; i>bot; i--) {
        map[i][C-1] = map[i-1][C-1];
    }
		
    // [아래] 오른쪽으로
    for (int i=C-1; i>1; i--) {
        map[bot][i] = map[bot][i-1];
    }
		
    map[top][1] = 0;
    map[bot][1] = 0;
}

바람의 방향대로 미세먼지를 한 칸씩 밀어낸 후에 공기청정기 바람의 시작점을 0으로 초기화해주어야한다. 

 

두 개의 과정을 입력된 시간만큼 반복해서 돌려주면 된다. 한 번의 과정을 거쳤다면 다시 미세먼지의 위치를 queue에 입력해주고 반복한다. 문제가 길고 조건이 많은 것처럼 보이지만 별로 어렵지 않은 문제이다.

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int R, C, T, airM, top, bot;
    static int[][] map;
    static Queue<Position> q;
	
    public static class Position {
        int x;
        int y;
        int v;
		
        public Position (int x, int y, int v) {
            this.x = x;
            this.y = y;
            this.v = v;
        }
    }
	
    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];
		
        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][0] == -1) {
                    airM = i;
                }
            }
        }
		
        int time = 0;
        top = airM-1;
        bot = airM;
		
        while (time < T) {
            CheckDust();  // 미세먼지 위치 확인
            DustSpread(); // 미세먼지 확산
            AirCleaner(); // 공기청정기
            time++;
        }
		
        int ans = 0;
        for (int i=0; i<R; i++) {
            for (int j=0; j<C; j++) {
                if (map[i][j] > 0) {
                    ans += map[i][j];
                }
            }
        }
		
        System.out.println(ans);
    }
	
    public static void CheckDust() {
        q = new LinkedList<>();
		
        for (int i=0; i<R; i++) {
            for (int j=0; j<C; j++) {
                if (map[i][j] > 0) {
                    q.add(new Position(i, j, map[i][j]));
                }
            }
        }
    }
	
    public static void DustSpread() {
        while (!q.isEmpty()) {
            Position now = q.poll();
			
            if (now.v < 5) continue;
			
            int cnt = 0;
            int DustSpreadV = now.v / 5;
			
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
				
                if (nx < 0 || ny < 0 || nx > R-1 || ny > C-1 || map[nx][ny] == -1) continue;
				
                map[nx][ny] += DustSpreadV;
                cnt++;
            }
			
            map[now.x][now.y] -= DustSpreadV * cnt; 
        }
    }
	
    public static void AirCleaner() {
        // [위] 아래 
        for (int i=top-1; i>0; i--) {
            map[i][0] = map[i-1][0];
        }
		
        // [위] 왼쪽
        for (int i=0; i<C-1; i++) {
            map[0][i] = map[0][i+1];
        }
		
        // [위] 위
        for (int i=0; i<top; i++) {
            map[i][C-1] = map[i+1][C-1];
        }
		
        // [위] 오른쪽
        for (int i=C-1; i>1; i--) {
            map[top][i] = map[top][i-1];
        }
		
        // [아래] 위로
        for (int i=bot+1; i<R-1; i++) {
            map[i][0] = map[i+1][0];
        }
		
        // [아래] 왼쪽으로
        for (int i=0; i<C-1; i++) {
            map[R-1][i] = map[R-1][i+1];
        }
		
        // [아래] 아래로
        for (int i=R-1; i>bot; i--) {
            map[i][C-1] = map[i-1][C-1];
        }
		
        // [아래] 오른쪽으로
        for (int i=C-1; i>1; i--) {
            map[bot][i] = map[bot][i-1];
        }
		
        map[top][1] = 0;
        map[bot][1] = 0;
    }
}

내가 생각한 시간 복잡도: O(RCT)