All Articles

λ°±μ€€ 15683번

이 λ¬Έμ œλŠ” ν’€λ¨Όμ„œ κ΅ν›ˆμ΄ μžˆμ–΄μ„œ νŠΉλ³„νžˆ TIL에 남겨봄.

  • μ²˜μŒμ—λŠ” DP인쀄 μ•Œκ³  ν’€μ—ˆκ³ , κ·Έλ ‡κ²Œν•΄μ„œ 예제 6κ°œλŠ” λ§žμ•˜λŠ”λ° 채점을 돌리면 ν‹€λ Έλ‹€.
  • μ•žμ—μ„œ ν’€μ–΄λ³Έ 문제처럼 μ‚Όμ„±=DFS / BFS λΌλŠ” μ„ ν˜„λ“€μ˜ 말을 λ– μ˜¬λ¦¬κ³ μ„œ DFS둜 μ™„μ „ 탐색을 λŒλ Έλ”λ‹ˆ λ§žμ·„λ‹€.
  • λ‹€ν–‰νžˆ μΉ΄λ©”λΌμ˜ 경우의 μˆ˜μ™€, 그에 λ”°λΌμ„œ μ‚¬κ°μ§€λŒ€λ₯Ό κ²€μ‚¬ν•˜λŠ” μ½”λ“œλŠ” μž¬μ‚¬μš©μ΄ κ°€λŠ₯ν•΄μ„œ μˆ˜μ •μ΄ 크게 μ–΄λ ΅μ§€λŠ” μ•Šμ•˜λ‹€.
  • DPμž„μ„ ν™•μ‹ ν•˜μ§€ μ•ŠμœΌλ©΄ 괜히 κ·Έλ ‡κ²Œ 풀지 말자!
#include <iostream>
#include <vector>
#include <limits>

using namespace std;

int MAX_INT = numeric_limits<int>::max();

int camStatus[8] = {0};
vector<int> camType;
vector<pair<int, int>> camLoc;
vector<int> choices = {-1, 4, 2, 4, 4, 1};
int N, M, C;
vector<vector<int>> map;

int min_blind = MAX_INT;

vector<vector<int>> dirs = {
    {0, 1},  // 였λ₯Έμͺ½
    {-1, 0}, // μœ—μͺ½
    {0, -1}, // μ™Όμͺ½
    {1, 0}}; // μ•„λž«μͺ½

void mark(vector<vector<int>> &mm, int n, int m, int dir)
{
    // n,m을 기점으둜 λ°©ν–₯을 따라 μ­‰ κ°μ‹œκ°€λŠ₯ν•œ ꡬ간을 ν‘œμ‹œν•¨
    int cn = n + dirs[dir][0];
    int cm = m + dirs[dir][1];

    while (0 <= cn && cn < N && 0 <= cm && cm < M)
    {
        if (mm[cn][cm] == 6)
        {
            //벽을 λ§Œλ‚¬μœΌλ‹ˆ 멈좀
            break;
        }

        if (mm[cn][cm] == 0)
        {
            // 빈 κ³΅κ°„μ΄λ‹ˆκΉŒ κ°μ‹œκ°€ κ°€λŠ₯ν•˜λ‹€κ³  써쀌
            // λ§Œμ•½ 카메라면 μ•ˆκ±΄λ“œλ¦¬κ³  κ·Έλƒ₯ λ„˜μ–΄κ°
            mm[cn][cm] = 7; //7은 κ°μ‹œκ°€ λœλ‹€λŠ” 뜻
        }
        cn += dirs[dir][0];
        cm += dirs[dir][1];
    }

    return;
}

int calc(int until) // until번째 μΉ΄λ©”λΌκΉŒμ§€ λ°˜μ˜ν•΄μ„œ μ‚¬κ°μ§€λŒ€μ˜ 갯수λ₯Ό 계산
{
    vector<vector<int>> tmap = map; // copy

    for (int i = 0; i <= until; i++)
    {
        int ctype = camType[i];
        int cStatus = camStatus[i];
        int n = camLoc[i].first;
        int m = camLoc[i].second;

        if (ctype == 1)
        {
            mark(tmap, n, m, cStatus);
        }
        else if (ctype == 2)
        {
            if (cStatus == 0)
            {
                mark(tmap, n, m, 0);
                mark(tmap, n, m, 2);
            }
            else if (cStatus == 1)
            {
                mark(tmap, n, m, 1);
                mark(tmap, n, m, 3);
            }
        }
        else if (ctype == 3)
        {
            int dd = (cStatus + 1) % 4;
            mark(tmap, n, m, cStatus);
            mark(tmap, n, m, dd);
        }
        else if (ctype == 4)
        {
            for (int d = 0; d < 4; d++)
            {
                if (d == cStatus)
                {
                    continue;
                }
                mark(tmap, n, m, d);
            }
        }
        else if (ctype == 5)
        {
            for (int d = 0; d < 4; d++)
            {
                mark(tmap, n, m, d);
            }
        }
    }

    int bcnt = 0;
    for (int n = 0; n < N; n++)
    {
        for (int m = 0; m < M; m++)
        {
            if (tmap[n][m] == 0)
            {
                bcnt++;
            }
        }
    }

    return bcnt;
}

void dfs(int depth)
{
    if (depth == camLoc.size())
    {
        int cost = calc(depth - 1);
        if (cost < min_blind)
        {
            min_blind = cost;
        }
        return;
    }
    int type = camType[depth];
    for (int c = 0; c < choices[type]; c++)
    {
        // μΉ΄λ©”λΌμ˜ μ’…λ₯˜μ— 따라 κ°€λŠ₯ν•œ 경우의 수λ₯Ό ν•˜λ‚˜ κ³¨λΌμ„œ μ €μž₯ν•˜κ³  λ‹€μŒ λ‹¨κ³„λ‘œ λ„˜μ–΄κ°
        camStatus[depth] = c;
        dfs(depth + 1);
    }
}

int main()
{
    cin >> N >> M; // height, width

    map = vector<vector<int>>(N, vector<int>(M));

    for (int n = 0; n < N; n++)
    {
        for (int m = 0; m < M; m++)
        {
            int t;
            cin >> t;
            map[n][m] = t;
            if (0 < t && t < 6)
            {
                camLoc.push_back(make_pair(n, m));
                camType.push_back(t);
            }
        }
    }

    dfs(0);

    cout << min_blind;

    return 0;
}
Published 14 Oct 2018

If I keep marking the dots, someday they will πŸ”—πŸ”—
Hyeungshik Jung on Twitter