14502번 연구소

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

2가지 풀이 방법이 있다. 

접근 방법 등 모두 기억하자.

첫 번째, BackTracking 활용

두 번째, 3중 For 문 활용

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

<BackTracking>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0, M = 0;
 
int map[9][9] = { 0, };
 
int result = -1;
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
vector<pair<int, int> > virus;
 
void wall(int r, int c, int cnt)
{
    if (cnt == 3)
    {
        queue<pair<int, int> > q;
 
        bool visit[9][9] = { false, };
 
        int vSize = virus.size();
 
        for (int i = 0; i < vSize; i++)
        {
            q.push(virus[i]);
            visit[virus[i].first][virus[i].second] = true;
        }
 
        while (!q.empty())
        {
            int qSize = q.size();
 
            while (qSize--)
            {
                int row = q.front().first;
                int column = q.front().second;
 
                q.pop();
 
                for (int i = 0; i < 4; i++)
                {
                    int y = row + dy[i];
                    int x = column + dx[i];
 
                    if (0 <= y && y < N && 0 <= x && x < M && !visit[y][x] && map[y][x] == 0)
                    {
                        // map[y][x] = 2;
                        // 위에서 바꿔주면 안 된다. 바꾸게 되면, 다음 진행이 존재 할 때, 영향을 끼침.
                        q.push({ y, x });
                        visit[y][x] = true;
                    }
                }
            }
        }
 
        int zeroCount = 0;
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (map[i][j] == 0 && !visit[i][j]) ++zeroCount;
                // 따라서, 0인 곳을 방문하지 않은 곳을 세주면 된다.
            }
        }
 
        result = max(result, zeroCount);
 
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if ((i == r && j > c) || i > r)
            {
                if (map[i][j] == 0)
                {
                    map[i][j] = 1;
                    wall(i, j, cnt + 1);
                    map[i][j] = 0;
                }
            }
        }
    }
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
 
            if (map[i][j] == 2) virus.push_back({ i,j });
        }
    }
 
    wall(-1, -1, 0);
    
    printf("%d\n", result);
 
    return 0;
}

<3중 For문>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
int N = 0, M = 0;
pair<int, int> map[100];
vector<pair<int, int> > virus;
int BFS(int temp[][9])
{
    int Safe = 0;
    queue<pair<int, int> > q;
    int visit[9][9] = { 0, };
    int arr[9][9] = { 0, };
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            arr[i][j] = temp[i][j];
        }
    }
    for (int i = 0; i < virus.size(); i++)
    {
        q.push(virus[i]);
    }
    while (!q.empty())
    {
        int qSize = q.size();
        while (qSize--)
        {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            if (visit[y][x] == 1) continue;
            visit[y][x] = 1;
            arr[y][x] = 2;
            for (int i = 0; i < 4; i++)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if ((0 <= ny && ny < N) && (0 <= nx && nx < M) && arr[ny][nx] == 0)
                {
                    q.push({ ny, nx });
                }
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (arr[i][j] == 0)
            {
                ++Safe;
            }
        }
    }
    
    return Safe;
}
int main(void)
{
    int arr[9][9] = { 0, };
    int index = 0, result = 0;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &arr[i][j]);
            map[index++] = { i,j };
            if (arr[i][j] == 2)
            {
                virus.push_back({ i,j });
            }
        }
    }
    for (int point_1 = 0; point_1 < index - 2; point_1++)
    {
        for (int point_2 = point_1 + 1; point_2 < index - 1; point_2++)
        {
            for (int point_3 = point_2 + 1; point_3 < index; point_3++)
            {
                
                int y1 = map[point_1].first; int x1 = map[point_1].second;
                int y2 = map[point_2].first; int x2 = map[point_2].second;
                int y3 = map[point_3].first; int x3 = map[point_3].second;
                if (arr[y1][x1] == 0 && arr[y2][x2] == 0 && arr[y3][x3] == 0)
                {
                    arr[y1][x1] = arr[y2][x2] = arr[y3][x3] = 1;
                    int ret = BFS(arr);
                    result = max(result, ret);
                    arr[y1][x1] = arr[y2][x2] = arr[y3][x3] = 0;
                }
            }
        }
    }
    printf("%d\n", result);
    return 0;
}