2-P 연구소 문제 질문있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

2-P

작성

235

다음은 제 풀이인데요.

http://boj.kr/40c0b7e643f04d319e867fb46381b92c

조합에도 사용할 수 있도록 next_permutation을 응용해서 풀려고 했습니다.

combi을 초기화하고 정렬하는 부분은 조합을 수행하기 위한 준비과정이고요.

do-while문에서 이제 각 경우에 대해 BFS를 수행하는 코드입니다.

return to the original board 부분은 원래의 맵으로 재초기화하는 부분입니다

establish the walls 부분은 벽을 세울 좌표에 벽을 세우는 부분입니다.

next_permutation으로 좌표 3개를 뽑아서 각 좌표에 해당하는 맵의 값을 1로 세우는 것(벽세우는것)입니다

그리고 이제 바이러스로 BFS를 수행하고 최종적으로 안전영역의 개수를 구하게 되는데요.

37%에서 멈추고 실패합니다가 뜨네요. 어떤 부분이 틀렸는지 알고 싶습니다.

강사님 풀이도 좋지만, 최대한 여러 풀이를 알고자하여 질문드립니다.

코테 준비 같이 해요! C++

답변 3

김희수

질문자

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

김희수

질문자

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

큰돌

지식공유자

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

// 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;
}

인프런 커뮤니티 질문&답변

2-P 연구소 문제 질문있습니다.