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

호흡이 길었던 문제라서 따로 정리해보려 한다.

문제 설명 및 입출력

그래프 그림이 많지만 핵심적인 정보만 추려보자.
문제에서 추출할 수 있는 정보는 다음과 같다.

• 0은 공간, 6은 벽이며, 1-5는 타입별 CCTV이다.
• 1~5까지의 CCTV는 탐색하는 방향에 대한 규칙이 각각 주어진다.
• 각 CCTV는 상하좌우 4가지 방향을 갖는다.
• 각 CCTV는 충돌과 같은 사고 없이 특정 방향에 서 있는 다른 CCTV 너머를 바라볼 수 있다. (통과할 수 있다.)
• 단 벽(6)은 통과할 수 없다.
• 가장 적은 크기의 사각지대가 만들어졌을 때 그 크기를 출력한다.

해결 과정

크게 3가지로 나눌 수 있다.

• 백트래킹: 모든 CCTV의 각 좌표를 저장하고, 각 CCTV에 대응하는 방향(0~3)을 백트래킹으로 계산한다. CCTV가 8개라면 경우의 수는 4^8개가 될 것이다.
• 탐색: 방향을 모두 정했다면 각 케이스마다 CCTV를 활성화하여 공간을 감시한다.
• 감시당하는 빈칸의 총 갯수를 계산하여 이 중 최솟값을 출력한다.

먼저 백트래킹은 아래와 같다.

void dfs(int idx, int cnt){
    if(cnt == pos.size()){
        cctv();
        return;
    }

    for(int j=0; j<4; j++){
        dir.push_back(j);
        dfs(idx+1, cnt+1);
        dir.pop_back();
    }
}

다음으로 BFS

void copy(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            tmp[i][j] = map[i][j];
        }
    }
}

void cctv(){
    copy();
    for(int i=0; i<pos.size(); i++){
        int nowdir = dir[i]; // i번째 CCTV의 방향(0~3)
        int type = map[pos[i].first][pos[i].second]; // CCTV의 타입(1~5)
        activate(nowdir, type, pos[i]);
    }
    
    int cnt = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(tmp[i][j] == 0){
                cnt++;
            }
        }
    }
    answer = min(answer, cnt);
}

나는 tmp라는 임시 2차원 배열을 매 케이스마다 선언하여, 감시당하는 빈칸을 배열 내에서 일반 빈칸인 0과 차별화하기 위해 -1로 표현해주었다.

이후 activate 함수를 통해 CCTV를 활성화하고 그 결과 남은 0의 총 갯수를 계산하여 최솟값을 갱신하였다.

void draw(int x, int y, int dir){
    while(1){
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(nx < 0 || ny < 0 || nx >= n || ny >= m || tmp[nx][ny] == 6) 
            break;
        if(tmp[nx][ny] == 0){
            tmp[nx][ny] = -1;
        }
        x = nx;
        y = ny;
    }
}

void activate(int dir, int type, pair<int, int> pos){
    int x = pos.first;
    int y = pos.second;
    if(type == 1){
        draw(x, y, dir);
    } else if(type == 2){
        draw(x, y, dir);
        draw(x, y, (dir+2)%4);
    } else if(type == 3){
        draw(x, y, dir);
        draw(x, y, (dir+1)%4);
    } else if(type == 4){
        draw(x, y, dir);
        draw(x, y, (dir+1)%4);
        draw(x, y, (dir+2)%4);
    } else {
        draw(x, y, dir);
        draw(x, y, (dir+1)%4);
        draw(x, y, (dir+2)%4);
        draw(x, y, (dir+3)%4);
    }
}

나는 while문을 통해 CCTV의 감시를 구현하였으며, 앞서 언급한 대로 감시당하는 빈칸은 -1로 처리했다.

개인적으로 호흡이 꽤 길어 코드를 고치는 시간이 오래 걸렸다.
호흡이 길어 보이는 문제는 정확하게 어떻게 구현할지 써놓고 시작하는 게 도움이 될 듯 하다.

소스 코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
int n, m;
int map[9][9];
int tmp[9][9];
int totalzero = 0;
int answer = 0;
vector<pair<int, int> > pos;
vector<int> dir;
int dx[4] = {0, -1, 0, 1}; // 우상좌하 반시계
int dy[4] = {1, 0, -1, 0};

void copy(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            tmp[i][j] = map[i][j];
        }
    }
}

void draw(int x, int y, int dir){
    while(1){
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(nx < 0 || ny < 0 || nx >= n || ny >= m || tmp[nx][ny] == 6) 
            break;
        if(tmp[nx][ny] == 0){
            tmp[nx][ny] = -1;
        }
        x = nx;
        y = ny;
    }
}

void activate(int dir, int type, pair<int, int> pos){
    int x = pos.first;
    int y = pos.second;
    if(type == 1){
        draw(x, y, dir);
    } else if(type == 2){
        draw(x, y, dir);
        draw(x, y, (dir+2)%4);
    } else if(type == 3){
        draw(x, y, dir);
        draw(x, y, (dir+1)%4);
    } else if(type == 4){
        draw(x, y, dir);
        draw(x, y, (dir+1)%4);
        draw(x, y, (dir+2)%4);
    } else {
        draw(x, y, dir);
        draw(x, y, (dir+1)%4);
        draw(x, y, (dir+2)%4);
        draw(x, y, (dir+3)%4);
    }
}

void bfs(){
    copy();
    for(int i=0; i<pos.size(); i++){
        int nowdir = dir[i]; // i번째 CCTV의 방향
        int type = map[pos[i].first][pos[i].second]; // CCTV의 성향
        activate(nowdir, type, pos[i]);
    }
    
    int cnt = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(tmp[i][j] == 0){
                cnt++;
            }
        }
    }
    answer = min(answer, cnt);
}

void dfs(int idx, int cnt){
    if(cnt == pos.size()){
        bfs();
        return;
    }

    for(int j=0; j<4; j++){
        dir.push_back(j);
        dfs(idx+1, cnt+1);
        dir.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
            if(map[i][j] == 0) totalzero++;
            else if(map[i][j] > 0 && map[i][j] < 6){ // 1부터 5는 CCTV
                pos.push_back(make_pair(i, j));
            }
        }
    }
    answer = totalzero;
    dfs(0, 0);
    cout << answer;
    return 0;
}

교훈

• 반복되는 코드가 많아질 것 같으면 반드시 분리한다.
• 특히 그래프 탐색의 진행 방향 변화가 핵심인 문제에서는 더욱 신경쓰자.