[15683👍] 감시

코드

#include <bits/stdc++.h>
int xdir[4] = {1,0,-1,0};    //    남 동 북 서
int ydir[4] = {0,1,0,-1};
int cdir[5] = {4,2,4,4,1};
int m,n;
int field1[15][15];
int field2[15][15];
int mn;
vector<pair<int,int>> camera;
void update(int x,int y,int dir)
{
    dir %= 4;
    while(1)
    {
        int xcur = x+xdir[dir];
        int ycur = y+ydir[dir];
        if(xcur<0||ycur<0||xcur>=n||ycur>=m||field2[xcur][ycur]==6) return;
        if(field2[xcur][ycur] != 0) continue;
        field2[xcur][ycur] = 7;
    }
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int ans = 0;
    int sum = 0;
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<m;j++)
        {
            cin >> field[i][j];
            if(field1[i][j] != 0 && field1[i][j] != 6)
            {
                camera.push_back({i,j}); 
                sum *= field[i][j] * (cdir[field[i][j]-1]);
            }
            if(field[i][j] == 0)
                ans++;
        }
    }
    for(int i =0;i<sum;i++)
    {
        for(int x = 0;x<n;x++)
        {
            for(int y = 0;y<m;y++)
            {
                field2[x][y] = field1[x][y];
            }
        }
        int temp = i % 4;
        for(int ca = 0;ca<camera.size();ca++)
        {
            int x = camera[ca].first;
            int y = camera[ca].second;
            if(field1[x][y] == 1)
            {
                update(x,y,temp);
            }
            else if(field1[x][y] == 2)
            {
                update(x,y,temp);
                update(x,y,temp+2);
            }
            else if(field1[x][y] == 3)
            {
                update(x,y,temp);
                update(x,y,temp+1);
            }
            else if(field1[x][y] == 4)
            {
                update(x,y,temp);
                update(x,y,temp+1);
                update(x,y,temp+2)
            }
            else if(field[x][y] == 5)
            {
                update(x,y,temp);
                update(x,y,temp+1);
                update(x,y,temp+2);
                update(x,y,temp+3);
            }
        }
        int val = 0;
        for(int x = 0;x<n;x++)
        {
            for(int y = 0;y<m;y++)
            {
                if(field[x][y] == 0)
                    val++;
            }
        }
        ans = min(val,ans);
    }
    cout << ans;
    
}

구현하지 못한 문제이다. 무엇이 문제였을까?

• 첫번째는 내가 고려한 풀이에 대한 시간복잡도가 너무 커 실패할까봐 이다.
  3중 반복문같이 매우 많은 연산이 필요해, 생각한 풀이 방법대신 다른 방법을 찾다가 구현조차 하지 못햇다...
  1초 정도라면 약 5억 의 연산이 가능하므로 N의 크기를 고려하여 해결방법을 고안해보도록 하자...
• 두번째는 회전 이다. 회전을 어떻게 구현해야 하는지 너무 어려웠다. 방향 배열 에 대한 이해도 조금 부족했다. 동서남북 을 이미 정의해두고 어떻게 해야할지 헷갈렸다.

---

회전 구현 방법 : 각 카메라는 최대 4개의 방향으로 회전이 가능하다. 또한 회전이 가능한 최대 개수가 1,2개인 카메라도 있지만 어쨋든 최대 4의k승 만큼 가능하다. 그렇다면 이 경우에서 어떻게 카메라가 회전하는 모든 경우의 수를 구할수 있을까?

이는 4로 나누고, 4로 나눈 나머지를 구하고... 방식으로 구현이 가능하다. 예를 들어 10진수 3461을 10으로 나누고, 10으로 나눈 나머지를 구하면 3,4,6,1 이라는 수가 나온다. 마찬가지로 4의 배수에 대해서도 이와같은 과정을 반복하는 것이다.

너무 어려운 문제다.. 그 만큼 얻어간 것도 많다..!