17142번 연구소 3

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

정답 코드 2개를 올리겠다.

두 번째 코드는 dist 배열을 활용하여 0의 개수와 비교하여 정답을 찾는 코드이다.

연구소 2 문제의 코드와 크게 다를 것이 없다.

다만, 연구소 3 문제에서는 

Map[행][열]  일 경우에만 시간을 저장하고, Map[행][열]에 value를 부여하면 된다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
#define value 100
 
typedef struct info
{
    int y;
    int x;
    int time;
}info;
 
info temp;
 
int Map[55][55] = { 0, }, arr[55][55] = { 0, }, N = 0, M = 0, MIN_time = 0;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
vector<pair<int, int> > v;
 
bool zero()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (Map[i][j] == 0) return true;
 
    return false;
}
 
int spread(vector<pair<int, int> > vc)
{
    int ret = 0;
 
    bool visit[55][55] = { false, };
 
    queue<info> q;
 
    for (int i = 0; i < vc.size(); i++)
    {
        Map[vc.at(i).first][vc.at(i).second] = value;
        visit[vc.at(i).first][vc.at(i).second] = true;
        temp.y = vc.at(i).first;
        temp.x = vc.at(i).second;
        temp.time = 0;
        q.push(temp);
    }
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().y;
            int c = q.front().x;
            int t = q.front().time;
 
            q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= N || x < 0 || x >= N || visit[y][x] || Map[y][x] == 1) continue;
 
                temp.y = y;
                temp.x = x;
                visit[y][x] = true;
                temp.time = t + 1;
                q.push(temp);
 
                if (Map[y][x] == 0)
                {
                    Map[y][x] = value;
                    ret = temp.time;
                }        
            }
        }
    }
 
    if (zero()) return -1;
    else return ret;
}
 
void update()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            Map[i][j] = arr[i][j];
}
 
void simulation(vector<pair<int, int> > vc, int pos)
{
    if (vc.size() == M)
    {
        update();
 
        int mt = spread(vc);
 
        if (mt == -1) return;
 
        MIN_time = min(MIN_time, mt);
 
        return;
    }
 
    for (int i = pos; i < v.size(); i++)
    {
        vc.push_back(v.at(i));
 
        simulation(vc, i + 1);
 
        vc.pop_back();
    }
}
 
int main(void)
{
    MIN_time = 1e9;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &Map[i][j]);
 
            arr[i][j] = Map[i][j];
 
            if (Map[i][j] == 2) v.push_back({ i,j });
        }
 
    vector<pair<int, int> > vc;
 
    simulation(vc, 0);
 
    if (MIN_time == 1e9) MIN_time = -1;
 
    printf("%d\n", MIN_time);
 
    return 0;
}

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
#define value 100
 
int Map[55][55] = { 0, }, arr[55][55] = { 0, }, N = 0, M = 0, MIN_time = 0, z = 0;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
vector<pair<int, int> > v;
 
int spread(vector<pair<int, int> > vc)
{
    int time = 0, zc = 0;
 
    int dist[55][55] = { 0, };
 
    memset(dist, -1, sizeof(dist));
 
    queue<pair<int, int> > q;
 
    for (int i = 0; i < vc.size(); i++)
    {
        Map[vc.at(i).first][vc.at(i).second] = value;
        dist[vc.at(i).first][vc.at(i).second] = 0;
        q.push({ vc.at(i).first, vc.at(i).second });
    }
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= N || x < 0 || x >= N || Map[y][x] == 1) continue;
 
                if (dist[y][x] == -1)
                {                
                    dist[y][x] = dist[r][c] + 1;
 
                    if (Map[y][x] == 0)
                    {
                        ++zc;
                        time = dist[y][x];
                    }
 
                    q.push({ y,x });
                }
            }
        }
    }
 
    if (zc == z) return time;
    else return -1;
}
 
void update()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            Map[i][j] = arr[i][j];
}
 
void simulation(vector<pair<int, int> > vc, int pos)
{
    if (vc.size() == M)
    {
        update();
 
        int mt = spread(vc);
 
        if (mt == -1) return;
 
        MIN_time = min(MIN_time, mt);
 
        return;
    }
 
    for (int i = pos; i < v.size(); i++)
    {
        vc.push_back(v.at(i));
 
        simulation(vc, i + 1);
 
        vc.pop_back();
    }
}
 
int main(void)
{
    MIN_time = 1e9;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &Map[i][j]);
 
            if (Map[i][j] == 0) ++z;
 
            arr[i][j] = Map[i][j];
 
            if (Map[i][j] == 2) v.push_back({ i,j });
        }
 
    vector<pair<int, int> > vc;
 
    simulation(vc, 0);
 
    if (MIN_time == 1e9) MIN_time = -1;
 
    printf("%d\n", MIN_time);
 
    return 0;
}