BOJ 15812

27 May 2020 • ProblemSolving

침략자 진아

문제출처

문제 해석

독주머니를 두개 설치해서 모든 마을에 중독시키는데 걸리는 최소시간을 구하는 문제입니다.

설계(5)

완전탐색으로 구현이 가능한 문제입니다.

빈칸에 독주머니를 놓을 수 있는 경우의 수는 400C2로 79600가지입니다.

독주머니를 놓고 bfs탐색으로 모든 마을이 중독되는데 걸리는 시간을 구합니다O(NM)

최악의 경우에 O(NM)x79600 = 400x79600 = 3.1x107로 시간안에 구현이 가능합니다.

공개코드된 처리된 분들의 코드를 보면 굳이 bfs를 탐색하지 않아도 구현이 가능한 것을 볼 수 있습니다.

첫번째,두번째 독주머니와 마을사이의 거리정보를 이용하여 더 빠르게 마을이 전부 중독되는 시간을 알 수 있습니다.

구현(10)

코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 20
#define INF 987654321
int N,M,total_cnt;
int ans = INF;
vector<pair<int,int>>vt;
int arr[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
pair<int,int> install[2];
queue<pair<int,int>> q;
int bfs(){
    memset(visited,false,sizeof(visited));
    while(!q.empty()) q.pop();
    for (int i =0 ; i<2;i++){
        visited[install[i].first][install[i].second]=true;
        q.push(install[i]);
    }
    int time=0;
    int cnt=0;
    while (!q.empty()){
        int q_size = q.size();
        if (cnt==total_cnt) return time;
        while (q_size--){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int k=0;k<4;k++){
                int nx = x +dx[k];
                int ny = y + dy[k];
                if (nx<0||ny<0||nx>=N||ny>=M||visited[nx][ny])continue;
                if (arr[nx][ny]) cnt++;
                visited[nx][ny]=true;
                q.push({nx,ny});
            }
        }
        time++;
    }
}
void backtrack(int cur, int cnt){
    if (cnt==2){
        int time = bfs();
        if (ans>time)ans=time;
        return;
    }
    for (int i = cur; i<vt.size();i++){
        install[cnt]=vt[i];
        backtrack(i+1,cnt+1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i <N; i++){
        for (int j =0; j <M; j++){
            char tmp;
            cin >> tmp;
            arr[i][j]=tmp-'0';
            if(arr[i][j]==0)vt.push_back({i,j});
            else total_cnt++;
        }
    }
    backtrack(0,0);
    cout << ans<<"\n";
    return 0;
}
디버깅
제출결과

200 ms

마무리

완전탐색문제였습니다. 개인적으로 삼성기출문제인 연구소3과 굉장히 비슷한 유형인 것 같습니다.

 BOJ

Related Posts