백준 14502 : 연구소

문제 링크입니다 https://www.acmicpc.net/problem/14502

14502번: 연구소

1. 모든 빈 칸들 중에서 3개를 골라서 벽을 만듭니다.

2. bfs를 통해 바이러스를 확산 시킵니다.

3. 안전 영역의 개수를 세어줍니다.

 

1번~3번을 반복하여 안전영역의 최대 개수를 찾는 문제였습니다.

 

 

[주석 + 소스코드]

 

// [백준] 삼성 SW 역량 테스트 기출 문제 : 연구소(14502)
 
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 8 + 10;
 
// 좌표를 저장하기 위한 구조체
struct p {
    int y, x;
};
vector <p> Virus;    // 바이러스의 좌표들을 담을 벡터
vector <p> Empty;    // 빈 칸의 좌표들을 담을 벡터
bool check[MAX*MAX];
int n, m, ret, map[MAX][MAX], mapCopy[MAX][MAX], result[MAX*MAX];
 
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, -1, 0, 1 };
 
// 좌표를 인자로 받아서 p type으로 바꿔주는 함수
p make_p(int y, int x) {
    p temp;
 
    temp.y = y, temp.x = x;
    return temp;
}
 
// 입력을 받는 함수
void input(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]);
            mapCopy[i][j] = map[i][j];
            if (map[i][j] == 2) {
                Virus.push_back(make_p(i, j));    // 바이러스의 좌표를 저장
            }
            else if (map[i][j] == 0) {
                Empty.push_back(make_p(i, j));    // 빈 칸의 좌표를 저장
            }
        }
    }
}
 
// 모든 바이러스를 큐에 집어넣고 각각의 바이러스로부터 bfs를 통해 바이러스를 퍼트리는 함수
int bfs(void) {
 
    // 먼저 result에 저장되어있는 빈칸의 좌표를 벽으로 바꾼다
    for (int i = 0; i < 3; i++) {
        // getResult에서 고른 인덱스에 해당하는 빈 칸 좌표를 벽으로 바꾼다
        map[Empty[result[i]].y][Empty[result[i]].x] = 1;
    }
    bool visit[MAX][MAX] = { 0, };
    queue <p> q;
 
    // 큐에 바이러스의 좌표들을 push하고 방문했다고 표시해준다
    for (int i = 0; i < Virus.size(); i++) {
        q.push(make_p(Virus[i].y, Virus[i].x));
        visit[Virus[i].y][Virus[i].x] = true;
    }
 
    int cnt = 0;    // bfs를 통해 빈 칸에 바이러스가 퍼진 횟수를 count
    while (!q.empty()) {
        p cur = q.front();
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = cur.y + dy[i];
            int xx = cur.x + dx[i];
 
            if (map[yy][xx] || visit[yy][xx] || yy < 0 || yy >= n || xx < 0 || xx >= m) {
                continue;    // 다음칸이 0이 아니거나 이미 방문했거나 맵을 벗어났으면
            }
            
            cnt++;
            map[yy][xx] = 1;
            visit[yy][xx] = true;
            q.push(make_p(yy, xx));
        }
    }
    return cnt + 3;    // 벽 3개와 바이러스가 몇 칸이나 퍼졌는지 return
}
 
// 모든 빈 칸 중에서 3개의 칸을 골라서 bfs를 돌려보고 안전영역의 개수를 ret에 저장하는 함수
void getResult(int count, int start) {
    if (count == 3) {
        int temp = Empty.size() - bfs();    // 빈 칸의 개수 - bfs가 반환한 값 = 안전영역의 개수
        if (ret < temp) ret = temp;
        memcpy(map, mapCopy, sizeof(mapCopy));    // map을 원상복구
    }
    else {
        for (int i = start; i < Empty.size(); i++) {
            if (!check[i]) {
                check[i] = true;
                result[count] = i;    // 빈 칸 벡터에 좌표가 있으므로 index를 고른다
                getResult(count + 1, i + 1);
                check[i] = false;
            }
        }
    }
}
 
void solve(void) {
    input();
    getResult(0, 0);
    printf("%d", ret);
}
 
int main(void) {
    solve();
    return 0;
}

 

[주석 없는 소스코드]

 

#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 8 + 10;
 
struct p {
    int y, x;
};
vector <p> Virus;   
vector <p> Empty;  
bool check[MAX*MAX];
int n, m, ret, map[MAX][MAX], mapCopy[MAX][MAX], result[MAX*MAX];
 
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, -1, 0, 1 };
 
p make_p(int y, int x) {
    p temp;
 
    temp.y = y, temp.x = x;
    return temp;
}
 
void input(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]);
            mapCopy[i][j] = map[i][j];
            if (map[i][j] == 2) {
                Virus.push_back(make_p(i, j));    
            }
            else if (map[i][j] == 0) {
                Empty.push_back(make_p(i, j));    
            }
        }
    }
}
 
int bfs(void) {
    for (int i = 0; i < 3; i++) {
        map[Empty[result[i]].y][Empty[result[i]].x] = 1;
    }
    bool visit[MAX][MAX] = { 0, };
    queue <p> q;
 
    for (int i = 0; i < Virus.size(); i++) {
        q.push(make_p(Virus[i].y, Virus[i].x));
        visit[Virus[i].y][Virus[i].x] = true;
    }
 
    int cnt = 0;  
    while (!q.empty()) {
        p cur = q.front();
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = cur.y + dy[i];
            int xx = cur.x + dx[i];
 
            if (map[yy][xx] || visit[yy][xx] || yy < 0 || yy >= n || xx < 0 || xx >= m) {
                continue;
            }
            cnt++;
            map[yy][xx] = 1;
            visit[yy][xx] = true;
            q.push(make_p(yy, xx));
        }
    }
    return cnt + 3;   
}
 
void getResult(int count, int start) {
    if (count == 3) {
        int temp = Empty.size() - bfs();  
        if (ret < temp) ret = temp;
        memcpy(map, mapCopy, sizeof(mapCopy));  
    }
    else {
        for (int i = start; i < Empty.size(); i++) {
            if (!check[i]) {
                check[i] = true;
                result[count] = i;   
                getResult(count + 1, i + 1);
                check[i] = false;
            }
        }
    }
}
 
void solve(void) {
    input();
    getResult(0, 0);
    printf("%d", ret);
}
 
int main(void) {
    solve();
    return 0;
}