팔랑귀

제한은 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번은 회전에 따라 감시 해제할 필요가 없죠.

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

저의 경우 취직하고 부모님 집하고 회사간 거리가 왕복 5시간 정도였고 교통비와 시간을 생각하면 고시원이라도 들어가는게 낫겠다 싶어서 고시원 생활을 시작했습니다. 처음들어간 고시원에서 10개월 정도 살았고 중간에 근무지가 바뀌면서 다른 고시원으로 옮겨서 8개월 가량을 더 살았습니다. 이 글은 약 1년 반의 고시원 생활을 마치고 작성하는 추억팔이 겸 후기입니다. 제가 살았던 시기는 2018년 7월부터 2019년 12월까지 입니다.

고시원의 장점은 몇 백 몇 천 하는 보증금이 필요없고 관리비나 공과금이 들어가지 않으며 다달이 월세만 내면 된다는 겁니다. 또, 언제든 원할 때 쉽게 방을 뺄 수 있습니다. 단점은 낯선 사람들과 세탁기, 화장실, 샤워실 등을 같이 써야하고 좁고 다닥다닥 붙은 방에서 산다는게 불편할 수 있다는 겁니다. 시설이 낙후되어 지저분한 곳도 있습니다. 하지만 이제 막 사회생활을 시작해서 모아둔 돈이 없을 때 들어갈 수 있는 곳은 고시원 밖에 없지않나 싶습니다 ㅠㅠ.

고시원의 한 달 월세는 22만원부터 45만원까지 다양합니다. 가격은 고시원의 전체적인 청결도나 제공하는 물품과 내부 시설에 따라 달라집니다. 제공 물품에는 밥이나 김치, 라면, 휴지, 세제 등이 있습니다. 시설에는 방의 넓이, 옷장, 옷걸이 봉, 책상, 냉장고, 내창, 외창 여부와 방 내부에 화장실이 있는지 등이 있습니다. 내창은 복도와 연결된 창문이고 외창은 밖과 연결된 창문입니다. 보통 다른건 없어도 옷장, 옷걸이 봉, 책상은 있습니다. 그만큼 없으면 불편합니다. 30만원 중후반에서 40만원대의 비싼 방은 대부분 더 넓고 안에 샤워가 가능한 화장실이나 에어컨이 있습니다. 도저히 공용 화장실, 샤워실을 못쓰겠다 하시는 분은 조금 더 금액을 내더라도 이런 방을 선택할 수 있습니다. 하지만, 시설에 따라서 물이 잘안내려가고 역류한다던지 하수구 냄새가 올라오거나 관리하기에 따라서 곰팡이가 생길 수 있다고 하니 잘 알아보고 선택하시길 바랍니다.

저는 화장실이나 샤워실을 공용으로 쓰는데 전혀 불편함을 느끼지 않아서 비싼 방은 선택지로 두지 않았습니다. 어차피 돈도 없었습니다 ㅋㅋ. 먼지랑 냄새에 예민한 편이라 외창이 있는방을 구했고 방을 구할 때 사장님과 흥정해서 2만원을 깎을 수 있었습니다. 그렇게 외창방 28만원으로 고시원 생활을 시작했습니다. 벌레도 없고 나름 깨끗한 고시원이었고 밥과 김치, 세제가 제공됐습니다. 저는 밥을 사먹고 들어가는 편이라 사는 동안 밥이나 김치는 전혀 먹지 않았지만 정수기와 세제는 있는동안 잘 썼습니다. 방 안에는 옷장, 옷걸이봉, 책상, 책꽂이, 냉장고, 랜선이 제공됐습니다. 외창방에는 단점이 하나있는데 겨울이 되면 굉장히 춥습니다. 창문이 냉기를 차단하지 못하기 때문입니다. 생긴게 원래 부실한 창문이라 방한지를 붙혀도 소용이 없었고 겨울엔 내창방으로 바꿨습니다. 값은 26만원으로 줄었고 살다보니 외창없어도 괜찮아서 있는동안 계속 그 방에서 살았습니다. 첫번째 고시원에선 살면서 방 사진을 찍어둔게 없어서 고시원 홈페이지에 있는 사진을 가져왔습니다.

두 번째로 살게된 고시원은 그 지역에서 고르고 골랐지만 시설이 좋지 않았습니다. 1층과 2층이 있었는데 1층은 전체적으로 습하고 잠깐 봤는데도 바퀴벌레가 많이 보여서 2층으로 골랐습니다. 외창방으로 구했고 24만원에 들어갔습니다. 공용 정수기와 냉장고가 있었고 방 안에는 옷장, 책상, 랜선이 있었습니다.

옷걸이 봉은 없어서 근처 생활용품점에서 사서 달았습니다. 봉은 사진처럼 빨래후 건조대 또는 옷걸이용으로 사용하며 굉장히 편리합니다. 여름에 모기가 너무 많아서 잡아도 소용이 없다면 모기장을 추천합니다. 약간 아늑한 느낌도 들고 꿀잠을 잘 수 있습니다. 사진의 방은 여름에 비가 많이오면 천장에서 비가 샙니다. 주말에 부모님 집에 갔다왔더니 방이 물바다가 되서 기겁을 했던 기억이 나네요. 노트북 말리고 물퍼내고 방 건조시키느라 힘들었었죠.

여름엔 샤워하러 들어가면 곱등이가 벽이나 바닥에서 기다리고 있는데 먼저 건드리지않고 무시하고 샤워하면 튀어 오르거나 하지않습니다. 전 쫄보라 해보지 않았지만 뜨거운 물을 한 바가지 뿌리고 씻는 방법도 있다고 하네요. 세탁기도 관리가 안된건지 빨고나면 퀘퀘한 냄새도 나고 뭔지 모를 검갈색 먼지같은것도 묻어나오고 했었죠... 참.. 눈물이 앞을 가렸던 시절입니다 ㅎㅎ.

처음 고시원에 살게 되면서 친구 소개로 타인은 지옥이다라는 웹툰을 보고 겁도 많이나고 걱정도 했지만 살아보면 적응도되고 다 사람 사는 곳입니다. 다만 너무 싼 곳은 시설이 안좋고 너무 비싼 곳은 비싸니 자신의 적응력과 주머니 사정을 생각해서 적당한 고시원을 선택하시길 바랍니다. 물론, 살려는 지역에 고시원이 몇군데 없어서 선택의 폭이 좁아지는건 어쩔 수 없지만요. 애지간하면 부모님 집에서 출퇴근합시다. 집나가면 개고생이란 말은 맞는 말입니다. :)

평상시 밥먹다가 혀나 볼을 많이 깨무는 편이긴한데 이번엔 좀 세게 깨물었는지 많이 쓰라렸습니다. 보통 넘어지거나 어디 쓸려서 살 껍데기가 한 쪽은 붙어있고 한 쪽은 떠있는 경우가 있는데 혀 살 껍데기가 그렇게 됐죠... ;_; 아래는 살 껍데기가 떨어진 사진입니다. 밥을 몇 번 먹었더니 떨어졌네요.

시간 좀 지나면 낫겠지 싶어서 되도록 반대편으로 밥먹고 조심하면서 지냈는데 일주일이 지나도 나아질 기미가 안보였습니다. 쓰라리니까 계속 신경쓰이고 신경쓰니까 더 아파지는 것 같더라고요.

그래서 쫄보인 저는 바로 집에서 가까운 병원에 갔습니다. 찾아보니 혀 깨물었을 땐 이비인후과에 가라고 하더군요. 병원에선 눈으로만 딱 보더니 이상없이 잘 낫고 있다고 소독 한 번 해주고 끝났네요. 병원비는 9,400원, 가글 1,800원 해서 총 11,200원 나왔습니다. 의사 선생님 말로는 혀가 원래 회복하는데 시간이 오래 걸린다고 합니다. 깨문 정도에 따라 다르겠지만 보통 3주까지는 기다려 본다고 하네요. 3주가 지나도 회복이 안되면 조직 검사등 확인을 해야한다고 하니 알아두시면 좋을 것 같습니다.

약은 가글형으로 병원갔다오자마자 딱 한 번 사용했는데 하루가 지난 지금은 다 나은 건지 통증이 전혀 느껴지지 않습니다. 가글했다고 안 아픈건진 확실하지 않지만 어쨋던 통증이 없으니 좋네요. 3주가 지나진 않았지만 통증으로 신경이 쓰이신다면 약국에서 약만 구매해서 사용하셔도 좋을 것 같습니다.

복기

처음엔 단순히 완전탐색 문제군 하고 시작했다가 몇 번이나 생각을 잘못해서 디버깅에 시간을 많이 허비했던 문제입니다. 그래도 다행히 잘못 생각한 부분들을 예제 입출력에서 다 잡아줘서 풀 수 있었네요. ㅋㅋ 처음 잘못 생각했던 건(사실 별 생각이 없었다는게 더 맞는 것 같지만) 동일한 거리의 물고기가 있을 때 먹을 물고기의 우선 순위(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도 그냥 발견할 때마다 그때그때 확인해서 가장 우선순위 높은 놈으로 들고있으면 될 것 같습니다. 허허,, 이 것으로 오늘의 복기를 마칩니다.