[삼성SW테스트] 백준 14502번 - 연구소 (정답률 54%)

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

14502번: 연구소

삼성 SW 테스트 기출문제다.

풀 수 있는 방법은

1. 백트래킹으로 놓을 수 있는 공간에 벽 세 개 설치하고 결과 구하기

2. 순열 (next_permutation함수와 플래그)로 풀기

정도가 있다.

 

두 방법 모두 활용해 풀어보았으며, 코드는 아래와 같다.

1. 백트래킹 (68ms)

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
int N, M;
int global_Answer = -INF;
vector<pair<int, int> > virus_pos;
vector<vector<int> > map;
bool start_next = false;
struct dir{
    int dr, dc;
};
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void dfs(int r, int c, int installed){
    if (installed == 3){
        queue<pair<int, int> > q;
        vector<vector<bool> > check;
        check.assign(N, vector<bool>(M, false));
        for (int i = 0; i < virus_pos.size(); i++){
            int cur_r = virus_pos[i].first, cur_c = virus_pos[i].second;
            check[cur_r][cur_c] = true;
            q.push(make_pair(cur_r, cur_c));
        }
        while (!q.empty()){
            int f_r = q.front().first;
            int f_c = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++){
                int n_r = f_r + direction[i].dr;
                int n_c = f_c + direction[i].dc;
                if (n_r >= 0 && n_r < N && n_c >= 0 && n_c < M){
                    if (!check[n_r][n_c] && map[n_r][n_c] == 0){
                        check[n_r][n_c] = true;
                        q.push(make_pair(n_r, n_c));
                    }
                }
            }
        }
        int local_Answer = 0;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                if (!check[i][j] && map[i][j] == 0)
                    local_Answer++;
            }
        }
        global_Answer = max(global_Answer, local_Answer);
        return;
    }
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            if (i > r || (r == i && j > c)){
                if (map[i][j] == 0){
                    map[i][j] = 1;
                    dfs(i, j, installed + 1);
                    map[i][j] = 0;
                }
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
 
    cin >> N >> M;
    map.assign(N, vector<int>(M, 0));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            cin >> map[i][j];
            if (map[i][j] == 2)
                virus_pos.push_back(make_pair(i, j));
        }
    }
    dfs(-1, -1, 0);
    cout << global_Answer << '\n';
    return 0;
}

 

2. 브루트포스 (52ms)

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#define INF 987654321
 
using namespace std;
 
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
int global_answer = -INF;
int N, M;
deque<pair<int, int> > dq;
 
vector<vector<bool> > check; // 
vector<vector<int> > map, map_cpy; // map 고정. map_cpy 매번 map으로 재초기화.
 
vector<pair<int, int> > virus, blank;
// blank 원소 수만큼 flag 선언한 뒤, 그 중 3개만 1로, 나머지 0으로 설정.
vector<int> flag;
 
void reset(){
    dq.clear();
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            map_cpy[i][j] = map[i][j];
            check[i][j] = false;
        }
    }
    for (int i = 0; i < virus.size(); i++){
        int cur_r = virus[i].first;
        int cur_c = virus[i].second;
        check[cur_r][cur_c] = true;
        dq.push_back(make_pair(cur_r, cur_c));
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N >> M;
    check.assign(N, vector<bool>(M, false));
    map.assign(N, vector<int>(M, 0));
    map_cpy.assign(N, vector<int>(M, 0));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            cin >> map[i][j];
            map_cpy[i][j] = map[i][j];
            if (map[i][j] == 0){
                blank.push_back(make_pair(i, j));
            }
            else if (map[i][j] == 2){
                virus.push_back(make_pair(i, j));
            }
        }
    }
 
    flag.assign(blank.size(), 0);
    for (int i = 0; i < 3; i++)
        flag[i] = 1;
    sort(flag.begin(), flag.end());
 
    do{
        reset(); // 바이러스 체크, 지도 초기화.
 
        int local_answer = 0;
        for (int i = 0; i < flag.size(); i++){
            if (flag[i]){
                //i번째 blank 당첨~
                int towall_r = blank[i].first;
                int towall_c = blank[i].second;
                map_cpy[towall_r][towall_c] = 1;
            }
        }
        // 지도에 새로운 1 지정 완료. check 완료. 
        while (!dq.empty()){
            int cur_r = dq.front().first;
            int cur_c = dq.front().second;
            dq.pop_front();
            for (int i = 0; i < 4; i++){
                int nr = cur_r + direction[i].dr;
                int nc = cur_c + direction[i].dc;
                if (nr >= 0 && nr < N && nc >= 0 && nc < M){
                    if (!check[nr][nc] && map_cpy[nr][nc] == 0){
                        // 내부, 방문x, 빈 공간이면 방문.
                        check[nr][nc] = true;
                        dq.push_back(make_pair(nr, nc));
                    }
                }
            }
        }
 
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                if (map_cpy[i][j] == 0 && !check[i][j]){
                    local_answer++;
                }
            }
        }
        global_answer = max(global_answer, local_answer);
    } while (next_permutation(flag.begin(), flag.end()));
    cout << global_answer << '\n';
    return 0;
}

백트래킹 관련 문제를 좀 더 풀어봐야 겠다.