작성한 질문수 13

0

항상 3개의 벽이 세워지도록 고쳐서 해결했습니다. 답변 도움되었습니다.

0

아 제 코드대로 하면 if(combi[i])에서 temp[y][x]==0이면 1로 바꾸지만 0이 아니면 바꾸지 않으므로, 항상 3개의 벽이 세워지는게 아니라 1개만, 혹은 2개만 세워질 수도 있게 되네요.

0

안녕하세요 희수님 ㅎㅎ 전반적으로 잘 짜셨네요. ㅎㅎ 다만, 주석달았는데 참고해주세요.

// https://www.acmicpc.net/problem/14502
#include <bits/stdc++.h>
using namespace std;

int n,m;
int board[9][9];
bool visited[9][9];

int temp[9][9];

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

//memcpy 사용해주세요.
void copy()
{
    for(int i = 0;i<n;i++)
        for(int j = 0; j<m;j++)
            temp[i][j] = board[i][j];
}

// good
bool OOB(int y, int x)
{
    return y <0 || y>=n || x<0 || x>=m;
}

void bfs(int y, int x)
{
    queue<pair<int,int>> q;
    q.push({y,x});

    while(!q.empty())
    {
        auto cur = q.front();
        q.pop();

        for(int dir = 0; dir<4;dir++)
        {
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];

            if(OOB(ny,nx))
                continue;
            
            if(temp[ny][nx] != 0)
                continue;
            temp[ny][nx] = 2;
            q.push({ny,nx});
        }
        
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    
    vector<pair<int,int>> coordinates;
    
    for(int i =0;i<n;i++)
    {
         for(int j = 0;j<m;j++)
        {
            cin >> board[i][j];
            coordinates.push_back({i,j});
        }   
    }   

    vector<int> combi;
    for(int i = 0; i< 3;i++)
        combi.push_back(1);
    for(int i =0;i<n*m-3;i++)
        combi.push_back(0);
    sort(combi.begin(), combi.end());


    int result = 0;
    //permutation이 아니라 combination으로 진행해주세요. 너무 느립니다.
    // 벽을 세우는 순서가 상관이 없기 때문에 combination으로 하는게 좋습니다.
    do
    {
        // restore the board
        copy();
        for(int i = 0;i<n;i++)
            fill(visited[i], visited[i], false);
        // establish the walls
        for(int i = 0;i<combi.size();i++)
        {
            if(combi[i] == 1)
            {
                // coordinates에다가 벽을 세우는 건데. 벽을 3개를 세워야 하지 않나요?
                // 이렇게 되면 벽을 3개를 세우는 경우의 수가 아니죠.
                // 벽을 세울 수 있는 후보지 3개를 정해서 진행해야 합니다. 
                // 즉, coordinates 는 벽을 세울 수 있는 후보지들을 담는 배열이 되어야 해요.
                int y = coordinates[i].first;
                int x = coordinates[i].second;
                if(temp[y][x] == 0)
                    temp[y][x] = 1;                           
            }
        }

        // BFS the virus
        for(int i = 0; i<n;i++)
        {
            for(int j = 0; j< m ; j++)
            {
                if(visited[i][j])
                    continue;
                if(temp[i][j] == 2)
                    bfs(i,j);
            }
        }

        // count the safezone
        int cnt = 0;
        for(int i =0;i<n;i++)
            for(int j = 0; j<m;j++)
                if(temp[i][j] == 0)
                    cnt+=1;
        result = max(result, cnt);
    } while (next_permutation(combi.begin(), combi.end()));
    

    cout << result;
}