시뮬레이션 문제입니다. 문제를 파악하고, 정확하게 구현하는 것이 중요합니다.

1. R, C 행과 열의 크기 (6 ≤ R, C ≤ 50)
2. T초 동안 반복 (1 ≤ T ≤ 1,000)
3. -1 공기 청정기가 있는 칸
4. 1 이상의 값 미세먼지가 있는 칸
5. 1초동안 아래의 일이 순서대로 일어납니다.
6. 미세먼지
   1) 미세먼지가 상하좌우 4방향으로 확산합니다.
   2) 인접한 방향에 공기청정기가 있거나, 칸이 없으면 확산되지 않습니다.
   3) 확산되는 양은 미세먼지의 양 / 5
   4) 남은 미세먼지의 양 a[r][c] - a[r][c] /5 * (확산된 방향의 개수)
7. 공기 청정기
   1) 공기청정기는 1열에 있으며, 움직이지 않으며, 2행을 차지합니다.
   2) 공기청정기 2개의 칸에서 바람이 나옵니다.
   3) 위쪽 바람은 반시계 방향, 아래쪽 바람은 시계방향
   4) 바람의 방향대로 미세먼지 한칸씩 이동
   5) 공기청정기로 들어간 미세먼지는 없어집니다.

T 초 후 남은 미세먼지의 수를 구하세요.

시간제한: 1초
문제 링크

---

1. 첫인상

구현문제 하기싫어

복잡해, 할 수 있을까...

우리 모두 할 수 있어요!

2. 접근과정

문제를 작게 쪼개봅시다.

1) 입력
2) 미세먼지 확산
3) 바람의 이동
4) 미세먼지 수 계산

1, 4) 번은 일반적인 2중 for문 사용.

고려해야할 부분은 2) 미세먼지 확산, 3) 바람의 이동

2개를 중점적으로 파악해봅시다.

3. 미세먼지 확산

1) 4방향 확산

이러한 알고리즘에서 4방향 확산(이동)은 정형화 되어 있습니다.

/*
    0~3 인덱스 값에 따라서
    0은 왼쪽
    1은 오른쪽
    2는 아래쪽
    3은 위쪽
*/
// 리듬감 있게 외우면 좋아요 0, 0, 1, -1
int dx[4] = {0, 0, 1, -1};
// 위에것 반대로
int dy[4] = {-1, 1, 0, 0};

    // x, y는 현재의 위치
    int x = 0;
    int y = 0;
    
    // 4개의 인접한 칸 4방향으로 생성
    for(int i=0; i<4; i++){
        // nx, ny는 다음 위치
        int nx = x + dx[i];
        int ny = y + dy[i];
    }

방향 벡터 라고 부릅니다. 물리시간은 아니니까 용어는 잊어버리고요~

2) 칸 검사

확산 되는 다음칸이 지도를 벗어나거나, -1 인 경우 확산 개수(최대 4)에서 감소를 시켜줍니다.

4. 바람의 이동

바람의 이동, 사실 여기가 핵심이기는 한데,

반시계, 시계 방향 회전하는것은 if, else if 반복하는것이어서 처음부터 정리하고 짜는것이 중요한것 같습니다.

한가지 고려한 것은 이동 방향입니다.

1) 이동 방향

아래의 그림처럼 1~6 6개의 칸을 이동방향대로 한칸씩 움직여야 한다면,

만약 나보고 손으로 하라면 오히려 거꾸로 했을거 같아서

그게 더 편할거 같아서, 거꾸로 구현했습니다.

위쪽 바람 - 반시계 -> 시계방향
아래족 바람 - 시계 -> 반시계

5. 시간 복잡도 계산

시간 복잡도: t초 지도 전체 탐색 (2중 for문) = tnm = 1000 50 * 50 = 2500000 = 250만

1억이 1초니까 시간안에 충분히 풀 수 있습니다.

코드

1) c++

#include <iostream>

#define max_int 51
using namespace std;


/*
    n - 행의 크기
    m - 열의 크기
    t - 시간
    head_x, head_y - 공기 청정기의 위쪽 좌표
    tail_x, tail_y - 공기 청정기의 아래쪽 좌표
 */
int n, m, t, head_x = -1, head_y = -1, tail_x = -1, tail_y = -1, result = 0;

/*
    미세먼지의 정보를 저장할 2차원 배열 a
    미세먼지 확산 정보를 임시로 저장할 2차원 배열 dust_temp
 */
int a[max_int][max_int], dust_temp[max_int][max_int];

/*
    0~3 인덱스 값에 따라서
    0은 왼쪽
    1은 오른쪽
    2는 아래쪽
    3은 위쪽
*/
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};


// 미세먼지 확산
void dust_move() {
    
    for(int x=1; x<=n; x++){
        for(int y=1; y<=m; y++){
            
            // 미세먼지만 이동합니다. 공기청정기 칸은 건너 뜁니다.
            if(x == head_x && y == head_y) continue;
            if(x == tail_x && y == tail_y) continue;

            // 현재 칸 미세먼지의 크기
            int dust_size = a[x][y];
            int spread_size = dust_size / 5;
            // 확산 방향
            int move_cnt = 0;
            
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 지도 밖으로 벗어나면 건너 뜁니다.
                if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
                
                // 미세먼지 칸이면 건너 뜁니다.
                if(a[nx][ny] == -1) continue;
                
                // 확산 방향을 1증가시킵니다.
                move_cnt++;
                // 확산 되는 크기를 임시 저장합니다. 겹칠 수 있기 때문에 += 으로 처리합니다.
                dust_temp[nx][ny] += spread_size;
            }
            
            // 확산 방향의 개수만큼 미세먼지 양을 감소시킵니다.
            a[x][y] = dust_size - spread_size * move_cnt;
        }
    }
    
    
    // 미세먼지 확산 임시저장한 값 원래 지도에 더해주기
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            a[i][j] += dust_temp[i][j];
            dust_temp[i][j] = 0;
        }
    }
}

// 바람의 이동
void wind() {
    
    // 공기청정기 - type 0 위쪽, type 1 아래족
    for(int type=0; type<=1; type++){

        int x, y, dir = 0;
        // 공기청정기 위쪽일때 시작방향은 위쪽
        if(type == 0){
            x = head_x;
            y = head_y;
            dir = 3;
        }
        // 공기청정기 아래쪽일때 시작방향은 아래족
        else{
            x = tail_x;
            y = tail_y;
            dir = 2;
        }
        
        // 한바퀴 돌아서 원래대로 돌아올때까지 반복
        while(true){
            // 다음 방향
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            // 원래의 위치면 중단합니다.
            if(nx == head_x && ny == head_y) break;
            if(nx == tail_x && ny == tail_y) break;
            
            // 오른쪽 끝
            if(ny > m) {
                if(type == 0) dir = 2;
                else dir = 3;
                continue;
            }
            // 위쪽 끝
            else if(nx < 1){
                dir = 1;
                continue;
            }
            // 아래쪽 끝
            else if(nx > n){
                dir = 1;
                continue;
            }
            
            // 위쪽인데 아래쪽으로 넘어가려고 하면 방향을 왼쪽으로 바꿔줍니다.
            if(type == 0 && nx > head_x && ny == m){
                dir = 0;
                continue;
            }
            
            // 아래족인데 위쪽으로 넘어가려고 하면 방향을 왼쪽으로 바꿔줍니다.
            if(type == 1 && nx < tail_x && ny == m){
                dir = 0;
                continue;
            }
            
            // 다음칸이 공기청정기가 아닐때
            if(a[x][y] != - 1){
                a[x][y] = a[nx][ny];
                a[nx][ny] = 0;
            }


            // 이동
            x = nx;
            y = ny;
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &t);
    
    // 1. 입력
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d", &a[i][j]);
            
            // 공기 청정기의 위치
            if(a[i][j] == -1){
                // 위쪽 좌표 저장
                if(head_x == -1 && head_y == -1){
                    head_x = i;
                    head_y = j;
                }
                // 아래쪽 좌표 좌정
                else {
                    tail_x = i;
                    tail_y = j;
                }
            }
        }
    }
    
    // 2. t초 동안 반복 수행
    for(int i=1; i<=t; i++){
        // 3. 미세먼지 확산
        dust_move();
        
        // 4. 바람의 이동
        wind();
    }
    
    // 5. 결과 계산 및 출력
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j] != -1 ) result += a[i][j];
        }
    }
    printf("%d\n", result);
}

2) java

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

public class Main{

    static int n, m, t, head_x = -1, head_y = -1, tail_x = -1, tail_y = -1, a[][], dust_temp[][];
    static int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        a = new int[n+1][m+1];
        dust_temp = new int[n+1][m+1];

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1; j<=m; j++){
                a[i][j] = Integer.parseInt(st.nextToken());
                if(a[i][j] == -1){
                    if(head_x == -1 && head_y == -1){
                        head_x = i;
                        head_y = j;
                    }else {
                        tail_x = i;
                        tail_y = j;
                    }
                }
            }
        }

        for(int seconds = 1; seconds <= t; seconds++){
            dust_move();

            wind();
        }

        int result = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(a[i][j] != -1 ) result += a[i][j];
            }
        }
        System.out.println(result);
    }

    public static void dust_move() {

        for(int x=1; x<=n; x++){
            for(int y=1; y<=m; y++){

                if(x == head_x && y == head_y) continue;
                if(x == tail_x && y == tail_y) continue;

                int dust_size = a[x][y];
                int move_cnt = 0;

                for(int i=0; i<4; i++){
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    if(nx < 1 || nx > n || ny < 1 || ny > m) continue;

                    if(a[nx][ny] == -1) {
                        continue;
                    }

                    move_cnt++;
                    dust_temp[nx][ny] += dust_size / 5;
                }

                a[x][y] = dust_size - (dust_size / 5) * move_cnt;
            }
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                a[i][j] += dust_temp[i][j];
                dust_temp[i][j] = 0;
            }
        }
    }

    public static void wind() {

        // type 0 head, type 1 tail
        for(int type=0; type<=1; type++){

            int x, y, dir = 0;
            if(type == 0){
                x = head_x;
                y = head_y;
                dir = 3;
            }
            else{
                x = tail_x;
                y = tail_y;
                dir = 2;
            }

            while(true){
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if(nx == head_x && ny == head_y) break;
                if(nx == tail_x && ny == tail_y) break;

                // 오른쪽 끝
                if(ny > m) {
                    if(type == 0) dir = 2;
                    else dir = 3;
                    continue;
                }
                // 위쪽 끝
                else if(nx < 1){
                    dir = 1;
                    continue;
                }
                // 아래쪽 끝
                else if(nx > n){
                    dir = 1;
                    continue;
                }

                if(type == 0 && nx > head_x && ny == m){
                    dir = 0;
                    continue;
                }

                if(type == 1 && nx < tail_x && ny == m){
                    dir = 0;
                    continue;
                }

                if(a[x][y] != - 1){
                    a[x][y] = a[nx][ny];
                    a[nx][ny] = 0;
                }

                x = nx;
                y = ny;
            }
        }
    }
}