[C++] Boj 15683 감시

문제 링크

15686 감시

---

접근(1)

int cctvCases[5][4] =
{
    { 0, 0, 0, 1 },
    { 0, 0, 1, 1 },
    { 0, 0, 1, 1 },
    { 0, 1, 1, 1 },
    { 1, 1, 1, 1 },
};

 

{위, 아래, 왼, 오른}순(바라보는 방향)으로 boolean 배열 규칙을 임의로 지정하고  CCTV의 모든 방향을 손으로 적어 봤더니 규칙을 찾을 수 있었다.

 

예를 들면 CCTV 1은 {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}으로 4C1의 경우의 수와 같다고 생각했다.

마찬가지로 CCTV2, CCTV3, CCTV4, CCTV5도 4Cn이라고 가정하고 문제를 풀이하였다.

이 과정에 next_permutation을 사용하였다. (하지만 이게 독이 됐다...)

 

따라서 알고리즘을 다음과 같이 짤 수 있었다.

1. CCTV의 위치를 따로 저장해 놓는다.
2. k번째 CCTV를 순서대로 순회하며 백트래킹한다.
3. k+1, k+2 ... CCTV까지 회전할 수 있는 모든 경우의 수를 조합한다.
4. 이후 과정을 다 마치면 bfs를 통해 사각지대의 넓이를 구한다.

CCTV2와 3은 내가 가정했던 대로 4C2의 형태로 값을 구하지만 각각 구별해야 하므로 예외 케이스를 두어 2와 3 케이스를 구분했다. 

// 2와 3 구별 위해
// 2의 경우의 수를 따로 지정
int exceptCase[2][4] =
{
    {1, 1, 0, 0},
    {0, 0, 1, 1},
};

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int map[10][10];
vector<pair<int, int>> cctvs;
queue<pair<int, int>> q;
bool visited[10][10];
bool isUsed[10];
int N;
int M;
int ans = 987654321;

int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

int cctvCases[5][4] =
{
    { 0, 0, 0, 1 },
    { 0, 0, 1, 1 },
    { 0, 0, 1, 1 },
    { 0, 1, 1, 1 },
    { 1, 1, 1, 1 },
};

// 2와 3 구별 위해
int exceptCase[2][4] =
{
    {1, 1, 0, 0},
    {0, 0, 1, 1},
};

void Capture(int k, int x, int y)
{
    switch (k)
    {
        // Up
    case 0:
        for (int i = x - 1; i >= 0; i--)
        {
            if (map[i][y] == 6) break;
            map[i][y] = '#';
        }
        break;

        // Down
    case 1:
        for (int i = x + 1; i < N; i++)
        {
            if (map[i][y] == 6) break;
            map[i][y] = '#';
        }
        break;

        // Left
    case 2:
        for (int i = y - 1; i >= 0; i--)
        {
            if (map[x][i] == 6) break;
            map[x][i] = '#';
        }
        break;

        // Right
    case 3:
        for (int i = y + 1; i < M; i++)
        {
            if (map[x][i] == 6) break;
            map[x][i] = '#';
        }
    }
}

int bfs(int x, int y)
{
    int cnt = 1;

    q.push({ x, y });
    visited[x][y] = true;

    while (!q.empty())
    {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx >= N || nx < 0 || ny >= M || ny < 0) continue;
            if (visited[nx][ny] || map[nx][ny] != 0) continue;

            q.push({ nx, ny });
            visited[nx][ny] = true;
            cnt++;
        }
    }

    return cnt;
}

int Solve()
{
    int ret = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (visited[i][j] || map[i][j] != 0)
                continue;

            ret += bfs(i, j);
        }
    }
    memset(visited, 0, sizeof(visited));
    return ret;
}

// k번째 cctv 탐색
void SearchAndRotate(int n)
{
    if (n == cctvs.size())
    {
        ans = min(Solve(), ans);
        return;
    }

    int x = cctvs[n].first;
    int y = cctvs[n].second;

    int curCctvCase[4];
    memcpy(curCctvCase, cctvCases[map[x][y] - 1], sizeof(curCctvCase));
    int curMap[10][10];
    memcpy(curMap, map, sizeof(map));

    do
    {
        bool flag = (equal(curCctvCase, curCctvCase + 4, exceptCase[0])
            || equal(curCctvCase, curCctvCase + 4, exceptCase[1]));

        if (map[x][y] == 2 && !flag)
            continue;

        if (map[x][y] == 3 && flag)
            continue;

        for (int k = 0; k < 4; k++)
        {
            if (curCctvCase[k] == 0) continue;
            Capture(k, x, y);
        }

        SearchAndRotate(n + 1);
        memcpy(map, curMap, sizeof(map));

    } while (next_permutation(curCctvCase, curCctvCase + 4));
}

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::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 && map[i][j] < 6)
                cctvs.push_back({ i, j });
        }
    }

    SearchAndRotate(0);
    cout << ans;

    return 0;
}

결과

 

두둥탁...

시간 초과가 나왔다.

질문 게시판을 찾아봤지만 나와 비슷한 풀이가 보이지 않아 gpt에게 물어보며 코드를 수정했다.

---

 

문제점(1) - memcpy의 남발이 문제인가?

memcpy는 전체 배열을 복사하는 함수이다.

일반적으로 NxM 크기의 배열을 복사하는 연산은 O(N*M)의 시간 복잡도를 가진다.

N, M은 8 이하로 매우 작지만 백트래킹이 계속 이어질 때, memcpy도 같이 남발하면 시간 복잡도에 영향을 줄 것 같아 이 부분을 수정해 보았다.

수정된 코드(1)

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int map[10][10];
bool isUsed[10];
int N, M;
int ans = 987654321;
vector<pair<int, int>> cctvs;
queue<pair<int, int>> q;
bool visited[10][10];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

int cctvCases[5][4] =
{
    { 0, 0, 0, 1 },
    { 0, 0, 1, 1 },
    { 0, 0, 1, 1 },
    { 0, 1, 1, 1 },
    { 1, 1, 1, 1 },
};

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


int bfs(int x, int y)
{
    int cnt = 1;
    q.push({ x, y });
    visited[x][y] = true;
    while (!q.empty())
    {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (nx >= N || nx < 0 || ny >= M || ny < 0) continue;
            if (visited[nx][ny] || map[nx][ny] != 0) continue;
            q.push({ nx, ny });
            visited[nx][ny] = true;
            cnt++;
        }
    }
    return cnt;
}

int Solve()
{
    int ret = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (visited[i][j] || map[i][j] != 0)
                continue;
            ret += bfs(i, j);
        }
    }
    memset(visited, 0, sizeof(visited));
    return ret;
}

// 변경된 셀만 기록하여 복원할 구조체
struct Change {
    int x, y;
    int prev;
};

// 변경된 좌표와 기존 값을 기록
vector<Change> CaptureWithRecord(int dir, int x, int y)
{
    vector<Change> changes;
    switch (dir)
    {
    case 0: // Up
        for (int i = x - 1; i >= 0; i--)
        {
            if (map[i][y] == 6) break;
            if (map[i][y] == 0)
            {
                changes.push_back({ i, y, map[i][y] });
                map[i][y] = '#';
            }
        }
        break;
    case 1: // Down
        for (int i = x + 1; i < N; i++)
        {
            if (map[i][y] == 6) break;
            if (map[i][y] == 0)
            {
                changes.push_back({ i, y, map[i][y] });
                map[i][y] = '#';
            }
        }
        break;
    case 2: // Left
        for (int j = y - 1; j >= 0; j--)
        {
            if (map[x][j] == 6) break;
            if (map[x][j] == 0)
            {
                changes.push_back({ x, j, map[x][j] });
                map[x][j] = '#';
            }
        }
        break;
    case 3: // Right
        for (int j = y + 1; j < M; j++)
        {
            if (map[x][j] == 6) break;
            if (map[x][j] == 0)
            {
                changes.push_back({ x, j, map[x][j] });
                map[x][j] = '#';
            }
        }
        break;
    }
    return changes;
}

// 변경 기록을 되돌림
void UndoChanges(const vector<Change>& changes)
{
    for (const auto& ch : changes)
        map[ch.x][ch.y] = ch.prev;
}

// n번째 CCTV를 처리
void SearchAndRotate(int n)
{
    if (n == cctvs.size())
    {
        ans = min(Solve(), ans);
        return;
    }

    int x = cctvs[n].first;
    int y = cctvs[n].second;

    int curCctvCase[4];
    memcpy(curCctvCase, cctvCases[map[x][y] - 1], sizeof(curCctvCase));

    do
    {
        bool flag = (equal(curCctvCase, curCctvCase + 4, exceptCase[0])
            || equal(curCctvCase, curCctvCase + 4, exceptCase[1]));

        if (map[x][y] == 2 && !flag)
            continue;
        if (map[x][y] == 3 && flag)
            continue;

        vector<Change> totalChanges;
        for (int d = 0; d < 4; d++)
        {
            if (curCctvCase[d] == 0) continue;
            vector<Change> changes = CaptureWithRecord(d, x, y);
            totalChanges.insert(totalChanges.end(), changes.begin(), changes.end());
        }

        SearchAndRotate(n + 1);
        UndoChanges(totalChanges);

    } while (next_permutation(curCctvCase, curCctvCase + 4));
}

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 && map[i][j] < 6)
                cctvs.push_back({ i, j });
        }
    }

    SearchAndRotate(0);
    cout << ans;

    return 0;
}

 

수정된 부분

// 변경된 셀만 기록하여 복원할 구조체
struct Change {
    int x, y;
    int prev;
};

// 변경된 좌표와 기존 값을 기록
vector<Change> CaptureWithRecord(int dir, int x, int y)
{
    vector<Change> changes;
    switch (dir)
    {
    case 0: // Up
        for (int i = x - 1; i >= 0; i--)
        {
            if (map[i][y] == 6) break;
            if (map[i][y] == 0)
            {
                changes.push_back({ i, y, map[i][y] });
                map[i][y] = '#';
            }
        }
        break;
    case 1: // Down
        for (int i = x + 1; i < N; i++)
        {
            if (map[i][y] == 6) break;
            if (map[i][y] == 0)
            {
                changes.push_back({ i, y, map[i][y] });
                map[i][y] = '#';
            }
        }
        break;
    case 2: // Left
        for (int j = y - 1; j >= 0; j--)
        {
            if (map[x][j] == 6) break;
            if (map[x][j] == 0)
            {
                changes.push_back({ x, j, map[x][j] });
                map[x][j] = '#';
            }
        }
        break;
    case 3: // Right
        for (int j = y + 1; j < M; j++)
        {
            if (map[x][j] == 6) break;
            if (map[x][j] == 0)
            {
                changes.push_back({ x, j, map[x][j] });
                map[x][j] = '#';
            }
        }
        break;
    }
    return changes;
}

// 변경 기록을 되돌림
void UndoChanges(const vector<Change>& changes)
{
    for (const auto& ch : changes)
        map[ch.x][ch.y] = ch.prev;
}

 

기존 memcpy를 사용해서 배열을 통째로 복사하여 복구하는 것보다, 바뀐 좌표만 다른 곳에 원래 값과 같이 저장하고, 나중에 이를 이용하여 복구하는 것이 조금 더 낫다 판단하여 위와 같이 수정하였다.

 

결과

 

맞긴 했다. 하지만 채점 현황에서 다른 분들(C++ user)의 걸린 시간과 비교해 봤더니... 내 풀이의 걸린 시간이 여전히 마음에 들지 않았다. 

 

또 시간 복잡도를 줄일 수 있는 방법은 뭐가 있을까?

---

문제점(2) - next_permutation이 과연 이 문제에서 효율적인가?

사실 얼마 전에 next_permutation에 대한 효율적인 문제 풀이 방법을 보아 괜히 써먹고 싶어 이 문제에 적용했다. 

그러나 next_permutation은 이 문제에서 효율적이지 못했다.

 

이유는 다음과 같다.

위 문제에서 next_permutation은 4개의 원소에 대해 최대 24가지의 순열을 생성한다.

하지만 실제로 각 CCTV 유형마다 필요한 회전 경우의 수는 종류에 따라 1, 2 또는 4가지로 제한된다.

즉, 불필요한 중복 순열을 생성해 불필요한 분기를 늘리고, 그에 따른 상태 복사와 복원 비용도 함께 증가시킨다. 

 

내가 아무리 예외 처리를 해서 중복된 순열의 일부를 건너뛰더라도, next_permutation은 여전히 4개의 원소에 대해 가능한 모든 순열(최악의 경우 24가지)을 모두 생성한다.

 

결론적으로,

• next_permutation은 모든 순열을 반복한다.
• 각 순열마다 백트래킹 호출과 맵 복사 혹은 상태 복원과 같은 추가 연산이 이루어지므로 전체 CCTV의 수가 많아지면 분기수가 지수적으로 늘어나게 되어 시간 초과가 발생할 수 있다.
• 중복 순열을 걸러내더라도 그 필터링은 상수 정도의 감소만 가져올 뿐, 근본적인 부분을 해결하지는 못한다.

따라서 next_permutation을 활용하지 않는 풀이법을 생각해 보았다.

수정된 코드(2)

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int map[10][10];
vector<pair<int, int>> cctvs;
int N, M;
int ans = 987654321;
queue<pair<int, int>> q;
bool visited[10][10];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

struct Change {
    int x, y;
    int prev;
};

vector<Change> CaptureWithRecord(int dir, int x, int y) {
    vector<Change> changes;
    switch (dir) {
    case 0: // Up
        for (int i = x - 1; i >= 0; i--) {
            if (map[i][y] == 6) break;
            if (map[i][y] == 0) {
                changes.push_back({ i, y, map[i][y] });
                map[i][y] = '#';
            }
        }
        break;
    case 1: // Down
        for (int i = x + 1; i < N; i++) {
            if (map[i][y] == 6) break;
            if (map[i][y] == 0) {
                changes.push_back({ i, y, map[i][y] });
                map[i][y] = '#';
            }
        }
        break;
    case 2: // Left
        for (int j = y - 1; j >= 0; j--) {
            if (map[x][j] == 6) break;
            if (map[x][j] == 0) {
                changes.push_back({ x, j, map[x][j] });
                map[x][j] = '#';
            }
        }
        break;
    case 3: // Right
        for (int j = y + 1; j < M; j++) {
            if (map[x][j] == 6) break;
            if (map[x][j] == 0) {
                changes.push_back({ x, j, map[x][j] });
                map[x][j] = '#';
            }
        }
        break;
    }
    return changes;
}

void UndoChanges(const vector<Change>& changes) {
    for (const auto& ch : changes)
        map[ch.x][ch.y] = ch.prev;
}

// 계산은 0의 개수를 세는 방식으로 간단히 처리 (0이 많을수록 블라인드 스팟)
int Solve() {
    int cnt = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (map[i][j] == 0)
                cnt++;
    return cnt;
}

// 각 CCTV 유형별 회전 경우 (방향은 0: Up, 1: Down, 2: Left, 3: Right)
vector<vector<vector<int>>> rotations(6);
void initRotations() {
    rotations[1] = { {0}, {1}, {2}, {3} };
    rotations[2] = { {0,1}, {2,3} };
    rotations[3] = { {0,3}, {3,1}, {1,2}, {2,0} };
    rotations[4] = { {2,0,3}, {0,3,1}, {3,1,2}, {1,2,0} };
    rotations[5] = { {0,1,2,3} };
}

// n번째 CCTV의 회전 방향을 선택하는 백트래킹 함수
void SearchAndRotate(int n) {
    if (n == cctvs.size()) {
        ans = min(ans, Solve());
        return;
    }

    int x = cctvs[n].first;
    int y = cctvs[n].second;
    int type = map[x][y]; // CCTV의 종류 (1~5)

    // 미리 정의한 회전 경우들을 순회
    for (auto& dirs : rotations[type]) {
        vector<Change> totalChanges;
        // 각 방향에 대해 변경된 셀만 기록하며 적용
        for (int d : dirs) {
            vector<Change> changes = CaptureWithRecord(d, x, y);
            totalChanges.insert(totalChanges.end(), changes.begin(), changes.end());
        }
        SearchAndRotate(n + 1);
        UndoChanges(totalChanges);
    }
}

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 && map[i][j] < 6)
                cctvs.push_back({ i, j });
        }
    }

    rotations.resize(6);
    initRotations();
    SearchAndRotate(0);
    cout << ans;
    return 0;
}

 

수정된 부분

각 CCTV가 회전할 수 있는 경우의 수를 그냥 배열로 지정해 두었다.

// 각 CCTV 유형별 회전 경우 (방향은 0: Up, 1: Down, 2: Left, 3: Right)
vector<vector<vector<int>>> rotations(6);
void initRotations() {
    rotations[1] = { {0}, {1}, {2}, {3} };
    rotations[2] = { {0,1}, {2,3} };
    rotations[3] = { {0,3}, {3,1}, {1,2}, {2,0} };
    rotations[4] = { {2,0,3}, {0,3,1}, {3,1,2}, {1,2,0} };
    rotations[5] = { {0,1,2,3} };
}

 

 

 

사각지대 계산도 bfs가 아닌 그냥 0인 곳을 세어나가는 식으로 간단하게 변경하였다.

// 계산은 0의 개수를 세는 방식으로 간단히 처리 (0이 많을수록 블라인드 스팟)
int Solve() {
    int cnt = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (map[i][j] == 0)
                cnt++;
    return cnt;
}

 

결과

 

나름 시간 복잡도가 괜찮게 줄어든 모습이다.

---

바킹독 님의 풀이

바킹독 강좌

[실전 알고리즘] 0x0D강 - 시뮬레이션

 

위에선 이 문제를 백트래킹을 사용하여 풀이하였다.

이 문제와 같이 변수들이 가질 수 있는 값이 여러개이고, 모든 조합을 다 확인해 보고 싶은데 변수들끼리는 서로 독립적일 땐 백트래킹 대신 더 쉬운 방법이 있다고 한다.

 

바로 진법을 이용한 방법이다.

 

---

진법으로 풀어보기

 

CCTV의 가능한 방향 종류가 4개이니 4진법을 쓰면 되고, 1번 카메라가 3개일 때, 0부터 63(4^3)까지의 수를 4진법으로 나타내면 000, 001, ... 332, 333까지 간다.

그리고 각각의 자리를 방향 3개에 대응시킨다.

중간의 39로 예를 들어보면 39는 4진수로 213이니까 방향을 (2, 1, 3)으로 둘 수 있다.

이렇게 하면 총 64가지의 모든 조합을 다 확인해 볼 수 있다.

 

 

그럼 0부터 63까지의 수를 4진수로 바꾸고 어떻게 각 자릿수를 얻을 수 있을까?

이건 10진수에서의 각 자릿수 문제를 얻는 것과 같은 방식으로 하면 된다. 이번에는 10진수가 아니라 4진수일 뿐이다.

의문

1, 3, 4번 CCTV는 가능한 방향이 4개인 건 맞는데, 2번 CCTV는 좌우 혹은 상하로 2개이고 5번 CCTV는 가능한 방향이 1개이다. 

 

Q.

그래서 만약 2번 CCTV가 2개이고 5번 CCTV가 1개라면 가능한 방향 조합의 수는 더 적은데 왜 무조건 4^k를 계산하는 걸까?

 

A.

물론 위 상황 때문에 중복되는 계산이 발생한다. 하지만 중복된 계산이 있어도 어차피 시간 내로 여유롭게 통과되기 때문에 예외 처리를 줄여 편하게 짜기 위해 CCTV의 종류를 가리지 않고 4^k개를 다 볼 것이다.

 

 

앞에서 4진법을 이용해 각 CCTV의 방향을 잡았다면 그 상황에서 사각 지대의 개수를 세면 된다.

 

코드

// http://boj.kr/c961e6bf6107428caf200c11c964f9e1
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 남쪽, 동쪽, 북쪽, 서쪽 순서
int n, m;
int board1[10][10]; // 최초에 입력받은 board를 저장할 변수
int board2[10][10]; // 사각 지대의 개수를 세기 위해 사용할 변수
vector<pair<int,int> > cctv; // cctv의 좌표를 저장할 변수

bool OOB(int a, int b){ // Out Of Bounds 확인
  return a < 0 || a >= n || b < 0 || b >= m;
}

// (x,y)에서 dir 방향으로 진행하면서 벽을 만날 때 까지 지나치는 모든 빈칸을 7로 바꿔버림
void upd(int x, int y, int dir){
  dir %= 4;
  while(1){
    x += dx[dir];
    y += dy[dir];
    if(OOB(x,y) || board2[x][y] == 6) return; // 범위를 벗어났거나 벽을 만나면 함수를 탈출
    if(board2[x][y] != 0) continue; // 해당 칸이 빈칸이 아닐 경우(=cctv가 있을 경우) 넘어감
    board2[x][y] = 7; // 빈칸을 7로 덮음
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  int mn = 0; // 사각 지대의 최소 크기 (=답)
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board1[i][j];
      if(board1[i][j] != 0 && board1[i][j] != 6)
        cctv.push_back({i,j});
      if(board1[i][j] == 0) mn++;
    }
  }
  // 1 << (2*cctv.size())는 4의 cctv.size()승을 의미.
  for(int tmp = 0; tmp < (1<<(2*cctv.size())); tmp++){ // tmp를 4진법으로 뒀을 때 각 자리수를 cctv의 방향으로 생각할 것이다.
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        board2[i][j] = board1[i][j];
    int brute = tmp;    
    for(int i = 0; i < cctv.size(); i++){
      int dir = brute % 4;
      brute /= 4;
      int x = cctv[i].X;
      int y = cctv[i].Y; // tie(x, y) = cctv[i];로 쓰면 1줄로 줄일 수 있음
      if(board1[x][y] == 1){
        upd(x,y,dir);
      }
      else if(board1[x][y] == 2){
        upd(x,y,dir);
        upd(x,y,dir+2);
      }
      else if(board1[x][y] == 3){
        upd(x,y,dir);
        upd(x,y,dir+1);
      }
      else if(board1[x][y] == 4){
        upd(x,y,dir);
        upd(x,y,dir+1);
        upd(x,y,dir+2);
      }
      else{ // board1[x][y] == 5
        upd(x,y,dir);
        upd(x,y,dir+1);
        upd(x,y,dir+2);
        upd(x,y,dir+3);
      }
    }
    int val = 0;
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        val += (board2[i][j]==0);
    mn = min(mn, val);
  }
  cout << mn;
}

 

주의할 점 - 정수의 정수 승을 계산할 때 pow 쓰지 말기

cmath 헤더에 있는 pow 함수는 인자로 실수를 받고, 또 실수를 반환하는 함수이기 때문에 오차가 생길 수도 있다.

차라리 for문을 도는 게 낫다.

 

오차가 생긴 예

 

위 코드의 시간 복잡도

 

느낀 점

진법을 활용한 풀이는 생각조차 못했는데, 내 힘으로 다시 구현해서 내 것으로 만들어야겠다!