팔랑귀

제한은 1초 512MB

맵의 크기는 8*8, 카메라를 4방향으로 돌릴 수 있고 카메라의 최대 갯수는 8개입니다.

카메라 8대 각각의 방향을 한 번씩 바꿔볼 때 나올 수 있는 경우의 수는 4^8 = 2^16 = 64k 번입니다. 카메라 각각은 고유함으로 중복은 없습니다. 각 경우에 사각 지역을 찾는 것은 8*8로 대충 100입니다. 64k * 100 = 6.4m 번입니다. 대충 1g 번 명령을 수행할 때 1초가 걸린다고 계산하면 6.4m 번은 0.01초(10ms) 이내에 수행될 수 있다고 생각합니다. 물론 카메라의 감시 영역을 체크하면서 수행될 명령문은 생각하지 않았지만 이를 차치하고서라도 시간은 충분해보입니다.

중복 순열은 재귀문으로 간단하게 작성할 수 있습니다.

void 중복순열(int 카메라 번호) {	/* 최대 카메라 갯수 = 8 */
	if 모든 카메라의 방향을 조정 ?
        맵의 사각 지역을 카운트
        return;
    
    for (감시 방향)			/* 방향 = 4 */
        감시 체크
        중복순열(이번 카메라 번호 + 1) 	// 다음 카메라로 넘어감
        감시 해제
}        

다음은 감시 체크와 해제를 하는 부분입니다. 우선 한 지점으로부터 한 방향으로 인자에 따라 감시 체크나 해제를 하는 함수를 만들었습니다. 감시 체크시에는 맵에서 -1을 하고 해제시엔 +1을 했습니다. 음의 정수의 크기로 중복 감시되는 지역을 표현했습니다.

int check(int x, int y) {
    if (x < 0 || N <= x || y < 0 || M <= y || map[x][y] == 6) return -1;
    if (0 < map[x][y] && map[x][y] < 6) return 0;
    return 1;
}

void observe(int x, int y, int d, bool f) {		// x,y 지점으로부터 d 방향으로 f (감시or해제)합니다.
    int xx = x + dir[d][0];
    int yy = y + dir[d][1];
    int c = check(xx, yy);

    while (c >= 0) {
        if (c) {
            map[xx][yy] += f ? -1 : 1;
        }
        xx += dir[d][0];
        yy += dir[d][1];
        c = check(xx, yy);
    }
}

카메라 특성에 맞게 observe() 함수를 호출할 수 있도록 각 카메라에 대한 정보를 배열에 담아 참조하도록 했습니다.

int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

int spec[5/*cctv*/][5/*time*/][4/*direction*/] = {
    { {1, 4},  {0}, {1}, {2}, {3} },
    { {2, 2},  {0, 1}, {2, 3}, {}, {} },
    { {2, 4},  {0, 3}, {0, 2}, {1, 2}, {1, 3} },
    { {3, 4},  {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3} },
    { {4, 1},  {0, 1, 2, 3}, {}, {}, {}}
};

3차원 배열이며 첫 번째는 카메라의 번호를 뜻합니다. 1번 카메라에 대한 정보는 spec[0] 번에 저장됩니다. 두 번째는 카메라 회전 횟수를 의미합니다. 동서남북 방향으로 4회가 최대입니다. 하지만, 특정 카메라의 경우엔 네 방향 모두 돌릴 필요가 없습니다. 예를 들어, 2번 카메라의 경우엔 가로, 세로 2번만 회전시키면 됩니다. 카메라마다 필요한 감시 횟수가 다름으로 이를 두 번째의 0번째 공간을 활용해 표현했습니다. 예를 들어 spec[0][0], {1, 4} 는 1번 카메라가 한 번에 1방향만 탐색하고 4회 회전해야함을 의미합니다. 마지막은 확인해야할 방향을 의미합니다. dir[][] 배열을 이용해서 0~3의 정수로 동서남북을 표현하였습니다.

전체 코드입니다.

#pragma warning(disable: 4996)
#include <stdio.h>
int N, M, map[10][10], ans = 0x7fffffff;
int cctv[10][2], K;
int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
int spec[5/*cctv*/][5/*time*/][4/*direction*/] = {
    { {1, 4},  {0}, {1}, {2}, {3} },
    { {2, 2},  {0, 1}, {2, 3}, {}, {} },
    { {2, 4},  {0, 3}, {0, 2}, {1, 2}, {1, 3} },
    { {3, 4},  {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3} },
    { {4, 1},  {0, 1, 2, 3}, {}, {}, {}}
};

int check(int x, int y) {
    if (x < 0 || N <= x || y < 0 || M <= y || map[x][y] == 6) return -1;
    if (0 < map[x][y] && map[x][y] < 6) return 0;
    return 1;
}

void observe(int x, int y, int d, bool f) {
    int xx = x + dir[d][0];
    int yy = y + dir[d][1];
    int c = check(xx, yy);

    while (c >= 0) {
        if (c) {
            map[xx][yy] += f ? -1 : 1;
        }
        xx += dir[d][0];
        yy += dir[d][1];
        c = check(xx, yy);
    }
}

void solve(int cctvn) {
    if (cctvn >= K) {
        int area = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                area += (map[i][j] == 0);
        if (area < ans)
            ans = area;
        return;
    }

    const int& x = cctv[cctvn][0];
    const int& y = cctv[cctvn][1];
    const int& cctvkind = map[x][y];
    const int& filltime = spec[cctvkind - 1][0][1];
    const int& fillcount = spec[cctvkind - 1][0][0];
    for (int i = 0; i < filltime; i++) {
        for (int j = 0; j < fillcount; j++)
            observe(x, y, spec[cctvkind - 1][i + 1][j], true);
        solve(cctvn + 1);
        for (int j = 0; j < fillcount; j++)
            observe(x, y, spec[cctvkind - 1][i + 1][j], false);
    }
}

int main(void) {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            scanf("%d", &map[i][j]);
            if (0 < map[i][j] && map[i][j] < 6)
                cctv[K][0] = i, cctv[K++][1] = j;
        }
    solve(0);
    printf("%d\n", ans);
    return 0;
}

다른 분들의 코드에선 5번 카메라는 회전에 관계없이 고정이므로 아예 처음에 감시 체크를 하고 중복 순열에서 제외시키는 모습을 볼 수 있었습니다. 확실히 5번은 회전에 따라 감시 해제할 필요가 없죠.

또, 각 카메라의 회전 방향만 별도의 배열에 저장하고 넘어간 뒤 모든 카메라의 회전 방향을 지정했을 때(중복 순열의 마지막에) 그 배열을 참조해서 감시 체크를 하고 답을 구하는 식의 코드도 있었습니다.

복기

처음엔 단순히 완전탐색 문제군 하고 시작했다가 몇 번이나 생각을 잘못해서 디버깅에 시간을 많이 허비했던 문제입니다. 그래도 다행히 잘못 생각한 부분들을 예제 입출력에서 다 잡아줘서 풀 수 있었네요. ㅋㅋ 처음 잘못 생각했던 건(사실 별 생각이 없었다는게 더 맞는 것 같지만) 동일한 거리의 물고기가 있을 때 먹을 물고기의 우선 순위(1번: 위에 있는 물고기, 2번: 왼쪽에 있는 물고기) 구현을 단순히 탐색 방향을 위, 왼쪽, 오른쪽, 아래 로 해놓고 됐다고 생각했던 건데요. 4번 예제에서 걸려서 디버깅 하다보니 중간에 잘못된 물고기를 먹더군요. 다시 생각해보니 아래 그림처럼 6번이 5번보다 위에 있어 우선 순위가 높지만 Queue엔 더 늦게 들어간다는걸 깨달았습니다.

두 번째 잘못 생각한 건 거리를 그냥 두 지점간 최단 거리로 구한건데 이러면 돌아가는 경우를 전혀 고려하지 않은게되죠. 변명을 해보자면...... 이때 많이 졸렸나봐요. 아래는 코드입니다.

#pragma warning(disable : 4996)
#include <stdio.h>
typedef struct _queue {
    int d[405][2];
    int f, r;
} Queue;
int N, M, sx, sy, ss, sc, ans;
int in[22][22], d[4][2] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };
bool vis[22][22];
Queue q1, q2, q3;

void enqueue(Queue* q, int x, int y) {
    q->d[q->r][0] = x;
    q->d[q->r][1] = y;
    (q->r)++;
}
void dequeue(Queue* q, int* px, int* py) {
    *px = q->d[q->f][0];
    *py = q->d[q->f][1];
    (q->f)++;
}
bool isEmpty(Queue* q) {
    return q->f == q->r;
}
void clear(Queue* q) {
    q->f = q->r = 0;
}
void solve(void) {
    Queue *cur = &q1;
    Queue *next = &q2;
    enqueue(cur, sx, sy);
    vis[sx][sy] = true;
    
    int dis = 0;
    while (M > 0 && !isEmpty(cur)) {
        while (!isEmpty(cur)) {
            int x, y, xx, yy;
            dequeue(cur, &x, &y);
            for (int i = 0; i < 4; i++) {
                xx = x + d[i][0];
                yy = y + d[i][1];
                if (xx < 1 || N < xx || yy < 1 || N < yy || vis[xx][yy]) continue;
                if (in[xx][yy] > ss) continue;
                
                vis[xx][yy] = true;
                if (in[xx][yy] == 0 || in[xx][yy] == ss)
                    enqueue(next, xx, yy);
                else
                    enqueue(&q3, xx, yy);
            }
        }
        dis++;
        if (isEmpty(&q3)) {
            Queue* tmp = cur;
            cur = next;
            next = tmp;
            clear(next);
        }
        else {
            int x, y, xx, yy;
            dequeue(&q3, &x, &y);
            while (!isEmpty(&q3)) {
                dequeue(&q3, &xx, &yy);
                if (x > xx || (x == xx && y > yy))
                    x = xx, y = yy;
            }
            clear(cur);
            clear(next);
            clear(&q3);
            enqueue(cur, x, y);
            in[x][y] = 0;
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    vis[i][j] = false;
            vis[x][y] = true;
            ans += dis;
            dis = 0;
            sx = x, sy = y;
            sc--;
            if (sc == 0)
                ss = sc = ss + 1;
            M--;
        }
    }
}

int main(void) {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) {
            scanf("%d", &in[i][j]);
            if (in[i][j] == 9) {
                sx = i;
                sy = j;
                ss = sc = 2;
                in[i][j] = 0;
            }
            else if (in[i][j]) {
                M++;
            }
        }
    solve();
    printf("%d\n", ans);
    return 0;
}

N의 최댓값이 20이라 대충 계산해서 물고기 찾는데 맵 다뒤져도 400, 물고기가 있어봐야 400마리, 합쳐도 160K 번 밖에 안되서 일단 마음은 편했습니다. 코드가 좀 지저분하지만 설명을 해보자면 우선 아기상어는 입력받을 때 맵에서 때어내서 변수 sx, sy, ss, sc 에 넣어 두었습니다. (변수명이 abc라 부연설명을 붙히자면 앞에 s는 shark, 뒤의 s는 size, c는 count) 맵안의 물고기 갯수는 변수 M에 저장해두었고요. solve() 함수를 보면 구현 방법은 BFS입니다. 큰 while문 안에 작은 while문 하나와 if else문 하나가 들어있습니다. 큰 while문은 먹을 물고기가 있고 이동이 가능한 상태면 계속 돕니다. 작은 while문은 실제 이동을 하는 부분입니다. step-by-step으로 이동하기위해 큐를 하나 더 사용했습니다. 이번 턴에 움직일 위치는 cur 큐에 들어있고 다음 이동할 위치는 next라는 다른 큐에 넣었습니다. 또, 이동중에 먹을 수 있는 물고기를 발견하면 그 물고기는 q3이라는 또다른 큐에 넣었습니다. 이번 턴의 이동을 마치면(작은 while문이 끝나면) if else문에서 먹을 수 있는 물고기를 발견했는지? 못했는지? 확인합니다. 발견 못했으면 next큐에 들어있는 좌표들이 새로운 턴에서 이동을 시작할 위치가 되기 때문에 cur큐와 next큐를 서로 바꿉니다. 발견했다면 q3안에 있는 물고기중 가장 우선 순위가 높은 물고기를 찾아서 먹고 아기 상어의 위치를 바꾼 후 새로운 탐색을 위한 준비를 하고 시작점으로 돌아갑니다.

문제를 풀고 다른 훌륭한 분들의 코드를 보니...... 작은 while문을 시작하기 전에 cur 큐의 사이즈를 아니까 딱 그만큼만 돌리면 어차피 한 step만큼만 돌기 때문에 굳이 큐를 여러개 쓸 필요는 없었네요. 대신 나머지 연산으로 큐를 환형으로 만들고요. 먹을 물고기를 저장했던 q3도 그냥 발견할 때마다 그때그때 확인해서 가장 우선순위 높은 놈으로 들고있으면 될 것 같습니다. 허허,, 이 것으로 오늘의 복기를 마칩니다.