백준 15683번: 감시 [C]

문제 링크

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

 

문제

정수로 구성된 2차원 맵을 준다.

맵의 오브젝트는 다음과 같다.

0: 빈 칸

1~5: cctv 종류

6: 벽

 

cctv의 종류별 감시 유형은 다음과 같다.

 

cctv는 각 방향에 대하여 벽을 만나거나 맵의 끝에 다다르기 전까지 일직선으로 감시할 수 있다.

cctv의 감시망은 벽(6)을 뚫지 못한다.

또한 cctv는 90도씩 회전할 수 있다.

cctv의 최대 개수는 8개다.

자세한 설명은 링크를 보는 게 좋다. 예시도 친절하게 제시한다.

 

cctv가 맵에서 감시하지 못하는 부분을 사각지대라고 하는데, cctv를 적절히 회전하여 최소 사각지대의 개수를 찾아 출력하는 문제다.

 

 

설계

어차피 cctv의 최대 개수는 8개이고, 회전 각도는 90도씩 4번이므로, 난 바로 비트연산자와 for문으로 편하게 brute force를 사용하면 되겠다고 생각했다.

간단하다.

그냥 다음의 코드를 보면 된다. 

void Solve() {
    . . .
    int try = 1;
    for(int i = 0; i < cctv; i++) {
    try *= 4;
    }
    for(int i = 0; i < try; i++) {
        . . .
        int bit = 0x3;
        for(int j = 0; j < cctv; j++) {
            int pos = (i >> (j*2)) & bit;
            SetRange(pos, j, map_case);
        }
    }
    . . .
}

예를 들어, cctv가 4개라면, try는 0b11111111 + 0b1일 것이다. (0b는 이진수를 의미한다.)

두번째 for문의 i는 0b0부터 0b11111111 까지 순회할 것이다.

잠깐 색칠 놀이를 하면 다음과 같다.

11111111

11: 4번째 cctv를 위한 공간

11: 3번째 cctv를 위한 공간

11: 2번쨰 cctv를 위한 공간

11: 1번째 cctv를 위한 공간

즉, i가 0b0부터 0b11111111까지 순차적으로 증가하는 동안, 각 cctv가 회전하는 모든 경우에 대해서 검사할 수 있다.

 

비트연산자로만 브루트 포스를 짜다보니 재귀문으로 백트래킹하는 방법을 까먹을 것 같다.

 

이외의 부분은 그냥 구현이라서 .. 그냥 하면 된다.

 

나는 최대한 가독성 좋게 짜고 싶어서 다음과 같은 함수를 정의했다. 

int rm[4] = {0, 1, 0, -1};
int cm[4] = {1, 0, -1, 0};

. . .

bool Watchable(int rr, int cc, int map_case[][8])
{
    return 0 <= rr && rr < r && 0 <= cc && cc < c && map[rr][cc] != 6;
}

bool Passable(int rr, int cc, int map_case[][8])
{
    return 1 <= map_case[rr][cc] && map_case[rr][cc] <= 5 || map_case[rr][cc] == '#';
}

void DrawLine(int rr, int cc, int pos, int map_case[][8])
{
    rr += rm[pos];
    cc += cm[pos];

    while (Watchable(rr, cc, map_case)) {
        if(!Passable(rr, cc, map_case)) {
            map_case[rr][cc] = '#';
        }
        rr += rm[pos];
        cc += cm[pos];
    }
}

void SetRange(int pos, int idx, int map_case[][8])
{
    int rr = cctvs[idx][0];
    int cc = cctvs[idx][1];
    DrawLine(rr, cc, pos, map_case);
    
    switch(cctvs[idx][2]) {
        case 1:
            break;
        case 2:
            DrawLine(rr, cc, (pos+2)%4, map_case);
            break;
        case 3:
            DrawLine(rr, cc, (pos+1)%4, map_case);
            break;
        case 4:
            DrawLine(rr, cc, (pos+1)%4, map_case);
            DrawLine(rr, cc, (pos+2)%4, map_case);
            break;
        case 5:
            DrawLine(rr, cc, (pos+1)%4, map_case);
            DrawLine(rr, cc, (pos+2)%4, map_case);
            DrawLine(rr, cc, (pos+3)%4, map_case);
            break;
        default:
            while(1);
            break;
    }
}