반응형

* 핵심 개념

시험 당시에는 17143번 낚시왕 문제보다 복잡해보여서 풀지 않았는데,

다시 풀어보니 역시 풀만한 문제였다. 

특별한 알고리즘 기법이 필요없이 단순히 새로운 크기의 맵을 하나 더 만들어서

새로운 맵에 시뮬레이션한 결과를 저장하고 이를 다시 원래맵에 돌려주기만 하면 된다.

* 문제

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

  1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
    • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
    • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
    • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
    • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
  2. 공기청정기가 작동한다.
    • 공기청정기에서는 바람이 나온다.
    • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
    • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
    • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static Cleaner[] cleaner_pos = new Cleaner[2];   //공기청정기 위치 저장
    public static int r, c, t;
    public static int[][] map;
    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        r = Integer.parseInt(stk.nextToken());
        c = Integer.parseInt(stk.nextToken());
        t = Integer.parseInt(stk.nextToken());
        map = new int[r][c];
        int idx = 0;
        for (int i = 0; i < r; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == -1) {
                    cleaner_pos[idx++] = new Cleaner(i, j);
                }
            }
        }
        for (int i = 0; i < t; i++) {
            spreadStart(new int[r][c]);
            cleanerStart(new int[r][c]);
        }
        getAns();
    }
 
    public static void spreadStart(int[][] nmap) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                nmap[i][j] += map[i][j];
                if (map[i][j] < 5) continue;
                int spreadCnt = map[i][j] / 5;
                for (int k = 0; k < 4; k++) {
                    int ny = i + dy[k];
                    int nx = j + dx[k];
                    //해당 맵에 퍼트릴 수 있는지 확인
                    if (ny >= 0 && ny < r && nx >= 0 && nx < c && map[ny][nx] != -1) {
                        nmap[i][j] -= spreadCnt;
                        nmap[ny][nx] += spreadCnt;
                    }
                }
            }
        }
        spreadCopy(nmap);
    }
 
    public static void cleanerStart(int[][] nmap) {
        for (int idx = 0; idx < 2; idx++) {
            Cleaner curr = cleaner_pos[idx];
            int ny = curr.r;
            int nx = curr.c + 1;
            //오른쪽으로 끝까지
            while (nx < c - 1) {
                nmap[ny][nx + 1] = map[ny][nx];
                nx++;
            }
            //상하로 끝까지
            if (idx == 0) {
                while (ny > 0) {
                    nmap[ny - 1][nx] = map[ny][nx];
                    ny--;
                }
            } else {
                while (ny < r - 1) {
                    nmap[ny + 1][nx] = map[ny][nx];
                    ny++;
                }
            }
            //좌측으로 끝까지
            while (nx > 0) {
                nmap[ny][nx - 1] = map[ny][nx];
                nx--;
            }
            //공기청정기 위치 전까지
            if (idx == 0) {
                while (ny < curr.r - 1) {
                    nmap[ny + 1][nx] = map[ny][nx];
                    ny++;
                }
            } else {
                while (ny > curr.r + 1) {
                    nmap[ny - 1][nx] = map[ny][nx];
                    ny--;
                }
            }
        }
        cleanerCopy(nmap);
    }
 
    public static void spreadCopy(int[][] nmap) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                map[i][j] = nmap[i][j];
            }
        }
    }
 
    public static void cleanerCopy(int[][] nmap) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (i == 0 || i == r - 1 || j == 0 || j == c - 1 || i == cleaner_pos[0].r || i == cleaner_pos[1].r) {
                    map[i][j] = nmap[i][j];
                }
            }
        }
        map[cleaner_pos[0].r][cleaner_pos[0].c] = -1;
        map[cleaner_pos[1].r][cleaner_pos[1].c] = -1;
    }
 
    public static void getAns() {
        int ans = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] <= 0) continue;
                ans += map[i][j];
            }
        }
        System.out.println(ans);
    }
 
    public static class Cleaner {
        int r, c;
 
        public Cleaner(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글

[Algorithm] 백준/17143 :: 낚시왕  (0) 2019.04.15
[Algorithm] 백준/17136 :: 색종이 붙이기  (1) 2019.04.13
[Algorithm] 백준/17135 :: 캐슬 디펜스  (0) 2019.04.06
[Algorithm] 백준/15685 :: 드래곤 커브  (0) 2019.04.05

티스토리툴바