[BOJ]14502 연구소(G4, C++)

📋 개요 

골드문제를 도전해보려고 한다. 맨날 S5~S1만 푸니깐 전체적인 알고리즘을 모르고 학습하는거 같다. 그래프 이론이나 조합, BFS, DFS는 골드 수준에서 자주 나오는거 같다. 그리고 내 백준 레벨에 맞는 문제를 풀어야지 레벨이 빨리오르겠지!!!

 

인프런 인강으로 아주 쉬운문제도 2문제씩 풀며 뇌를 말랑말랑하게 하고 골드문제를 풀고 있다

---

🧩 문제

https://www.acmicpc.net/problem/14502

📝  형식 

📥 입력	📤 출력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다. 빈 칸의 개수는 3개 이상이다.	첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

💡  예제

*링크 참고

 

🥲  내 코드 및 정답코드

---

📖  해설 및 느낀점

문제를 읽으면서 몇가지 헤맸던 지점이 있었다.

물론 사이즈가 작긴하지만, 어떻게하면 적절한 위치에 벽을 세울 수 있을까에 대한 고민을 첫번째로 한거같다.

처음에 Grid를 그려두고 바이러스가 퍼뜨리는 것을 막는 최고의 방법이 뭐지?

 

틀린 생각이지만 조합으로 거듭나기까지의 나의 생각이였다.

1. "2" 바이러스 상하좌우로 벽을 세운다.
2. "1" 벽 기준으로 대각선 방향으로 세운다. ➡️ 대각선 방향으로 세우니깐 안전영역이 +1씩되었다.

문제를 저런 조건을 세우면 어차피 모든 칸에 다 1이 들어갈 수 있는 조건이 된다. 빠져봤자 1~2개....??

또한 문제에서 보았다 싶이 사이즈가 그렇게 크지 않다

 

 

그렇다면 어짜피 다 순회하면서 "1" 벽이 3번 세워질 수 있는 3번의 조합을 찾아서 다 넣고 안전영역을 구하면 되겠다고 생각했다.

 

그렇다면 조합식(중복X)으로 몇번 연산을 할 수 있는지가 나온다. 먼저 0의 위치에는 벽이 세워질 수 있다. 위치를 저장한다.

vector<pair<int, int> > loc;

for(int i = 0 ; i <n; i++){
        for(int j = 0 ; j <m; j++){
            cin >> board[i][j];
            if(board[i][j] == 0){
                loc.push_back(make_pair(i,j));
            }
        }    
    }

 

1번 예제에서 벽이 세워질 수 있는 0의 위치는 35개이다. 그렇다면 조합식을 계산해보자.

즉, 1번예제에서는 6,545번 연산을 수행한다는 이야기이다.

그러면 위의 조합하는 코드를 작성한다.

int r = 3; //벽의 갯수
vector<pair<int, int> > comb(r); //조합을 담을 자료구조

void Combination(vector<pair<int,int> > arr, vector<pair<int,int>> comb, int r, int index, int depth)
{
    if (r == 0){
        int result = calSafeZone(comb);
        if(ans < result){
            ans = result;
        }
    }
    else if (depth == arr.size()){
        return;
    }
    else{
        comb[index] = arr[depth];
        Combination(arr, comb, r - 1, index + 1, depth + 1);
        Combination(arr, comb, r, index, depth + 1);
    }
}

 

그러면 6545개의 조합들이 나온다. 다음 차례는 무엇일까?

우리가 구해야하는건 "바이러스가 감염된 뒤 안전영역의 갯수"이다.

 

다음차례인 바이러스 감염시키기다. 바이러스를 감염시키려면 bfs를 활용해야한다.

void bfs(){
    
    queue<pair<int, int>> q;
    for(int i = 0 ; i < n; i++){
        for(int j = 0 ; j < m; j++){
            if(cBoard[i][j] == 2) q.push({i,j});
        }
    }
    
    while(!q.empty()){
        pair<int,int> curr = q.front();
        q.pop();
        cBoard[curr.first][curr.second] =2;
        for(int i =0 ; i < 4 ;i++){
            int nextR = curr.first + dx[i];
            int nextC = curr.second + dy[i];
            if(nextR < 0 || nextC < 0 || nextR >= n || nextC >= m) continue;
            if(cBoard[nextR][nextC] ==0){
                cBoard[nextR][nextC] = 2;
                q.push({nextR, nextC});
            }
        }
    } 
}

 

Queue를 활용하여 "2" 바이러스있는 위치를 큐에 담고 하나씩 내면서 상하좌우 위로 바이러스를 감염시킨다.

 

int calSafeZone(vector<pair<int,int> > arr){
    cBoard[8][8] = {0, };
    memcpy(&cBoard , &board, sizeof(board));
    
    for(int i = 0 ; i< 3 ;i++){
        cBoard[arr[i].first][arr[i].second] = 1;
    }
    
    //바이러스 퍼뜨리기
    bfs();
    
    int cnt =0;
    for(int i = 0 ; i < n; i++){
        for(int j = 0 ; j < m; j++){
            if(cBoard[i][j] == 0) cnt++;
        }
    }
    
    return cnt;

}

 

그리고 안전영역을 계산하면 된다.