[구름LEVEL] 제습제

난이도	정답률
★★★	-%

프리미엄 알고리즘 위클리 비타알고 시즌3 3주차

goorm

문제

격자판 위의 1은 제습제를, 0은 빈 공간을 나타낸다. 빈 공간에 맞닿아 있는 제습제는 1초 후 습기를 흡수하고 사라진다. 위의 격자판이 1초가 지나면 다음과 같은 모양이 된다.

제습제가 배치된 정보가 주어졌을 때, 모든 제습제가 사라지기까지 걸리는 시간을 구해보자!

모든 제습제가 사라지는데 걸리는 시간을 출력한다. 만약 제습제가 사라질 수 없는 경우라면 -1을 출력한다.

 

시행착오

1. 배열을 일일이 복사했다.

• arr과 tarr배열을 각각 만들었고 arr을 기준으로 그 다음 시간일 때 배열상태를 tarr에 저장해두고
• tarr값을 arr에 덮어쓴다.
• tarr을 초기화시킨다.

👉 방문했음을 체크하는 chk배열을 사용하면 매번 배열을 복사하지 않아도 된다.

2. queue도 일일이 복사했다.

• cq(current queue)와 (next queue)nq, q(비어있는 queue)가 있다.
• cq에 입력받을 당시 제습제 위치를 저장해 두었고
• cq를 확인하면서 cq에 있는 제습제 주변에 0을 못만나서 다음 시간에도 확인해야한다면
• nq에 넣어준다.
• cq를 모두 확인했다면 nq의 내용을 cq에 덮어쓴다. (cq = nq, =연산자로 가능)
• nq를 초기화 할 때 비어있는 queue를 사용한다. (nq = q)

👉 queue에 좌표와 함께 시간을 저장해두면 queue하나로 문제를 해결할 수 있다.

3. 출력조건을 깊게 생각하지 않았다.

• if문을 사용해서
• 만약 처음 제습기 위치를 저장해둔 cq의 크기가 n*n인 배열 크기와 같다면
• 제습제가 사라질 수 없는 경우이므로 0을 출력했다.

👉 이 경우는 제습제가 없을 때 0을 출력해야할 것 같아서 이렇게 묶었는데, 사실상 모든 배열이 0이든 1이든 제습제가 사라질 수 없는 경우이기 때문에 -1을 바로 출력하면 된다.

(다시 확인해보니 문제에서 명시를 안해줌. 0이든 -1이든 출력하면 정답)

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> p;
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0, };
int n, ans;
int arr[1005][1005], tarr[1005][1005];
queue<p> cq, nq;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j]) {
                cq.push({ i, j });
            }
        }
    }
    if (cq.size() != n * n) {
        queue<p> q;
        while (1) {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (arr[i][j])break;
                    else cnt++;
                }
            }
            if (cnt == n * n) break;
 
            while (!cq.empty()) {
                p front = cq.front();
                cq.pop();
                int x = front.first, y = front.second;
                int flg = 0;
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                    if (!arr[nx][ny]) {
                        flg = 1; break;
                    }
                }
                if (!flg) {
                    tarr[x][y] = 1;
                    nq.push({ x, y });
                }
            }
            ans++;
            cq = nq;
            nq = q;
            memcpy(arr, tarr, sizeof(arr));
            memset(tarr, 0, sizeof(tarr));
        }
        printf("%d", ans);
    }
    else {
        printf("-1");
    }
    return 0;
}

 

해결

key point,
1. queue에 좌표와 함께 시간을 저장해두면 queue하나로 문제를 해결할 수 있다.
2. 방문했음을 체크하는 chk배열을 사용하면 매번 배열을 복사하지 않아도 된다.
3. 격자판이 모두 0으로 채워진 경우, BFS가 진행되지 않았으므로 제습제는 사라질 수 없다.
  → -1을 출력하든 0을 출력하든 정답...(문제가 모호함)

1. 입력을 받을 때 제습제가 있다면 q에 시간과 제습제의 좌표를 저장한다.
2. 만약 q의 크기가 배열 크기와 같거나 q가 비어있다면 제습제가 사라질 수 없는 경우이므로 바로 -1 출력.
3. 그 외의 경우에는 BFS로 확인.
4. q가 비어질 때 까지 반복할 때, 해당 제습제 위치를 x, y로 보고 현재 시간을 d라고 하면
5. 정답은 최대인 d값이 된다.
6. 제습제의 인접한 위치에 빈 공간(0)이 있다면 chk배열에 현재 시간(d)을 저장하고 인덱스 값을 0으로 갱신한다.
7. 제습제의 인접한 위치에 빈 공간이 하나라도 없었다면, flg는 0이며 이 때 q에 현재시간+1(d+1)과 좌표를 함께 넣어준다.
8. 제습제의 인접한 위치를 탐색할 때 배열범위를 벗어나거나, 이미 방문한 위치의 시각이 현재 시각과 같다면 넘어간다.

이렇게 모든 q가 비어질 때까지 반복하면 모든 격자판은 0이 되고, 이 때 ans을 출력하면 정답이다.

코드

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> p;
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0, };
int n, ans;
int arr[1005][1005], chk[1005][1005];
queue<pair<int, p>> q;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j]) q.push({ 1, { i, j } });
        }
    }
    while (!q.empty() && q.size() != n*n) {
        pair<int, p> front = q.front();
        q.pop();
        int d = front.first, x = front.second.first, y = front.second.second;
        ans = max(ans, d);
        int flg = 0;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || chk[nx][ny] == d) continue;
            if (!arr[nx][ny]) {
                chk[x][y] = d;
                arr[x][y] = 0; flg = 1; break;
            }
        }
        if (!flg)q.push({ d + 1, { x, y } });
    }    
    printf("%d", ans ? ans : -1);
    return 0;
}

 

후기

해설을 보고난 후 깔끔하게 고칠 수 있었지만 정작 문제를 몇 번이고 틀렸던 이유는,

제습제가 사라질 수 없는 경우일 때 -1을 출력해야하는 것을 망각하고 문제를 풀었기 때문이다;; ㅋㅋㅋㅋ

문제를 잘 읽고 풀자!!