BOJ 15683 - 감시

문제 링크

구현이 복잡해서 좀 골치아팠다. 문제 자체가 엄청 복잡하지는 않다. CCTV 들의 위치를 기억해 뒀다가, CCTV 가 감시할 수 있는 모든 방향 조합에 따라 감시가 되는 구역을 조사하고, 감시 되지 않는 곳을 세어주면 된다.

아래 내용이 처음으로 정답을 받은 코드이다.

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int one[1] = {0}, two[2] = {0, 2}, three[2] = {0, 1}, four[3] = {0, 1, 2}, five[4] = {0, 1, 2, 3};
vector<pii> cctv;
vector<vector<int>> mp;
int n, m;

void mark(vector<vector<int>>& mp, int x, int y, int state);

void nextState(vector<int>& s) {
    int len = cctv.size() - 1;
    s[len]++;
    for(; len >= 0; --len) {
        if(s[len] == 4 && len != 0) {
            s[len] = 0;
            s[len - 1]++;
            if(s[len - 1] != 4) break;
        }
    }
    if(s[0] == 4) s[0] = -1;
}

bool checkRange(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    mp.resize(n);
    for(int i = 0; i < n; ++i) {
        mp[i].resize(m);
        for(int j = 0; j < m; ++j) {
            cin >> mp[i][j];
            if(mp[i][j] != 0 && mp[i][j] != 6)
                cctv.push_back({i, j});
        }
    }
    int len = cctv.size(), ans = 0x7fffffff;
    if(len == 0) {
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(mp[i][j] == 0) cnt++;
            }
        }
        cout << cnt;
        return 0;
    }
    vector<int> state(len, 0);
    while(state[0] != -1) {
        vector<vector<int>> curr(n);
        copy(mp.begin(), mp.end(), curr.begin());
        for(int idx = 0; idx < cctv.size(); ++idx) {
            pii tv = cctv[idx];
            int x = tv.first, y = tv.second;
            int st = state[idx];
            mark(curr, x, y, st);
        }
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(curr[i][j] == 0) cnt++;
            }
        }
        ans = min(ans, cnt);
        nextState(state);
    }
    cout << ans;
    return 0;
}

void mark(vector<vector<int>>& mp, int x, int y, int state) {
    switch(mp[x][y]) {
        case 1:
            for(int d : one) {
                int nx = x + dx[(d + state) % 4], ny = y + dy[(d + state) % 4];
                while(checkRange(nx, ny) && mp[nx][ny] != 6) {
                    if(mp[nx][ny] <= 0) mp[nx][ny] = -1;
                    nx += dx[(d + state) % 4];
                    ny += dy[(d + state) % 4];
                }
            }                
            break;
        case 2:
            for(int d : two) {
                int nx = x + dx[(d + state) % 4], ny = y + dy[(d + state) % 4];
                while(checkRange(nx, ny) && mp[nx][ny] != 6) {
                    if(mp[nx][ny] <= 0) mp[nx][ny] = -1;
                    nx += dx[(d + state) % 4];
                    ny += dy[(d + state) % 4];
                }
            }      
            break;
        case 3:
            for(int d : three) {
                int nx = x + dx[(d + state) % 4], ny = y + dy[(d + state) % 4];
                while(checkRange(nx, ny) && mp[nx][ny] != 6) {
                    if(mp[nx][ny] <= 0) mp[nx][ny] = -1;
                    nx += dx[(d + state) % 4];
                    ny += dy[(d + state) % 4];
                }
            }   
            break;
        case 4:
            for(int d : four) {
                int nx = x + dx[(d + state) % 4], ny = y + dy[(d + state) % 4];
                while(checkRange(nx, ny) && mp[nx][ny] != 6) {
                    if(mp[nx][ny] <= 0) mp[nx][ny] = -1;
                    nx += dx[(d + state) % 4];
                    ny += dy[(d + state) % 4];
                }
            }   
            break;
        case 5:
            for(int d : five) {
                int nx = x + dx[(d + state) % 4], ny = y + dy[(d + state) % 4];
                while(checkRange(nx, ny) && mp[nx][ny] != 6) {
                    if(mp[nx][ny] <= 0) mp[nx][ny] = -1;
                    nx += dx[(d + state) % 4];
                    ny += dy[(d + state) % 4];
                }
            }   
            break;
    }
}

4019B 라니 말도 안된다...

우선 문제의 입력을 받으며 CCTV 가 들어오면 그 좌표를 vector<pii> cctv 에 저장해 둔다. 이제 cctv.size() 만큼의 vector<int> state 를 선언하여 CCTV 들의 감시 방향을 관리한다. i 번째 CCTV 의 감시 방향은 state[i] 에 \(0, 1, 2, 3\) 의 값으로 저장되어 있다. \(0\) 인 경우에는 문제 설명에 있는 기본 상태이고, \(1\) 씩 증가할 때마다 \(90^\circ\) 씩 반시계 방향으로 돌아간 상태이다.

이러한 state 들을 계산해주기 위해 nextState() 를 구현했다. \(4\)진법 정수를 구현한 셈이다. 맨 앞 자리 숫자가 \(4\)가 되면 state 들을 모두 조사한 것으로 판단하고 첫 자리를 \(-1\) 로 바꿔주어 while 문에서 판단할 수 있도록 했다.

while 문은 state 를 모두 조사할 때 까지 실행된다. while 내부는 간단하다. 우선 지도를 복사하고, 각 CCTV 의 위치와 감시 방향 정보를 이용해 감시되는 구역을 지도에 표시해준다. 이를 mark 함수가 처리해 줄 것이다. 이 과정이 끝나면 감시 되지 않는 구역의 개수만 세어 최솟값을 구해주면 끝난다.

mark 함수 때문에 고민을 참 많이 했다. mark 에서는 현재 지도, CCTV 의 위치, state 를 이용해 지도에 감시되는 곳을 표시할 것이다. 우선 CCTV 의 종류를 판별하고, 지도를 벗어나지 않는 동안 감시된 곳은 \(-1\) 로 바꿔주었다. 첫 구현은 대략 이런 모양이었다.

int nx = x + dx[(d + state) % 4], ny = y + dy[(d + state) % 4];
while(checkRange(nx, ny)) {
    mp[nx][ny] = -1;
    nx += dx[(d + state) % 4];
    ny += dy[(d + state) % 4];
}

 

이렇게 돌려보니 당연히 벽을 뚫고 감시해버렸다. 그래서 while 안에 mp[nx][ny] <= 0 이라는 조건을 추가해서 이미 감시된 구역이나 감시 되지 않은 구역에 대해서만 while 이 실행되도록 했다. (이 과정에서 mp[ny][ny] <= 0 으로 적은 오타를 발견하지 못해 시간이 많이 소요되었다...) 이렇게 했더니 예제는 맞길래, 제출해 봤더니 틀렸다.

나중에 알고보니 CCTV 는 벽을 넘어서는 감시를 못하지만 CCTV 를 넘어서는 감시할 수 있다는 사실을 깨닫고 while 의 조건을 수정했다.

int nx = x + dx[(d + state) % 4], ny = y + dy[(d + state) % 4];
while(checkRange(nx, ny) && mp[nx][ny] != 6) {
    if(mp[nx][ny] <= 0) mp[nx][ny] = -1;
    nx += dx[(d + state) % 4];
    ny += dy[(d + state) % 4];
}

 

이렇게 제출하니 런타임 에러를 받았고 (ㅋㅋ) CCTV 가 한 개도 들어오지 않는 경우를 처리하지 않았다는 사실을 알았다. 이 부분을 처리해 주니 맞았습니다를 받았고, 코드는 4019B 였다. 줄이자!

우선 각 CCTV 의 종류에 따라 감시 방향을 \(5\)개의 다른 배열에 저장했었는데, 이를 vector<vector<int>> 하나로 합쳤다. 그리고 mark 함수를 호출하기 전에 CCTV 의 종류를 판단하도록 하여 중복되는 코드를 싹 제거했다. 최종 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
vector<vector<int>> dir = {{0}, {0, 2}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}};
vector<pii> cctv;
vector<vector<int>> mp;
int n, m;

void mark(vector<vector<int>>& mp, int x, int y, int state) {
    int nx = x + dx[state], ny = y + dy[state];
    while(checkRange(nx, ny) && mp[nx][ny] != 6) {
        if(mp[nx][ny] <= 0) mp[nx][ny] = -1;
        nx += dx[state];
        ny += dy[state];
    }
}

void nextState(vector<int>& s) {
    int len = cctv.size() - 1;
    s[len]++;
    for(; len >= 0; --len) {
        if(s[len] == 4 && len != 0) {
            s[len] = 0;
            s[len - 1]++;
            if(s[len - 1] != 4) break;
        }
    }
    if(s[0] == 4) s[0] = -1;
}

bool checkRange(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    mp.resize(n);
    for(int i = 0; i < n; ++i) {
        mp[i].resize(m);
        for(int j = 0; j < m; ++j) {
            cin >> mp[i][j];
            if(mp[i][j] != 0 && mp[i][j] != 6)
                cctv.push_back({i, j});
        }
    }
    int cnt = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(mp[i][j] == 0) cnt++;
        }
    }
    int len = cctv.size(), ans = cnt;
    if(len == 0) {
        cout << ans;
        return 0;
    }
    vector<int> state(len, 0);
    while(state[0] != -1) {
        vector<vector<int>> curr(n);
        copy(mp.begin(), mp.end(), curr.begin());
        for(int idx = 0; idx < cctv.size(); ++idx) {
            pii tv = cctv[idx];
            int x = tv.first, y = tv.second;
            int st = state[idx];
            for(int d : dir[mp[x][y] - 1]) 
                mark(curr, x, y, (d + st) % 4);
        }
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(curr[i][j] == 0) cnt++;
            }
        }
        ans = min(ans, cnt);
        nextState(state);
    }
    cout << ans;
    return 0;
}

 

여기서 조금 더 최적화를 하고 싶다면, \(5\) 번 CCTV 에 대해 굳이 state 를 관리하지 않는 방법이 있을 것이다. 현재 구현 상으로는 무조건 \(4\) 번 조사를 하니, \(5\)번 CCTV 의 비율이 높은 경우에는 실행 시간이 꽤 줄어들 것이다.

시간 복잡도

CCTV 가 \(k\) 개 인 경우, 모든 state 의 개수는 \(4^k\) 개 이고, 각 state 마다 한 CCTV 의 감시 구역을 mark 하는 비용은 많아야 지도에서 가로, 세로 각각 한 줄 씩이므로 \(M+N\) 이다.

따라서 각 state 마다 지도에 mark 하는 총 비용은 \(\mathcal{O}(k(M + N))\) 이므로, 최종 시간 복잡도는

\[\mathcal{O}(k\cdot{4^k}\cdot(M+N))\]

이 된다. \(k\leq 8\) 이므로 시간 내에 잘 작동한다.