C - [백준 14502] 연구소 (feat. 시뮬레이션, 백트래킹, DFS, BFS)

참고 포스트

2024.12.22 - [Computer Science/알고리즘 문제] - C - [백준 1260] DFS와 BFS

C - [백준 1260] DFS와 BFS

2025.01.07 - [Computer Science/자료구조 & 알고리즘] - [알고리즘] 백트래킹과 DFS: 문제 요구사항에 맞춘 설계 방법 (feat. 알고리즘 문제 유형)

[알고리즘] 백트래킹과 DFS: 문제 요구사항에 맞춘 설계 방법 (feat. 알고리즘 문제 유형)

2025.01.09 - [Computer Science/자료구조 & 알고리즘] - [알고리즘] 시뮬레이션 문제는 왜 어려울까? (feat. 설계의 중요성)

[알고리즘] 시뮬레이션 문제는 왜 어려울까? (feat. 설계의 중요성)

 

 

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

 

BOJ_14502 연구소

 

연구소는 NxM 크기의 직사각형으로 이루어져 있으며, 빈 칸(0), 벽(1), 바이러스가 있는 칸(2)으로 구성되어 있습니다.
바이러스는 상하좌우로 인접한 빈 칸으로 계속 퍼져나갑니다.
새로 세울 수 있는 벽 3개를 추가로 세워서, 바이러스가 퍼질 수 없는 영역(안전 영역)을 최대화해야 합니다.

입력 형식

1. 첫 줄에 연구소의 크기 N, M이 주어집니다. (3 ≤ N, M ≤ 8)
2. 다음 줄부터 연구소의 지도 정보가 주어집니다.
   • 0: 빈 칸
   • 1: 벽
   • 2: 바이러스가 있는 칸

출력 형식

• 추가로 벽을 세운 뒤, 바이러스가 퍼지지 않은 영역의 최대 크기를 출력합니다.

---

Checkpoint

 

시뮬레이션 문제는 프로세스 과정을 절차적으로 분할해야합니다.

문제에서 요구하는 것이 맵에 새로운 벽 3개를 새웠을 때 안전한 구역의 최대값을 구하는 것이기 때문에

 

1. 벽을 3개 세운다.

2. 바이러스를 퍼뜨린다.

3. 안전구역의 갯수를 센다

4. 최대값과 비교한다.

 

와 같은 과정으로 프로세스를 나눌 수 있습니다. 그 후 각 프로세스를 어떤 알고리즘을 사용하여 구현할지 설계해야합니다.

 

1번 과정일 경우,

다른 요구 조건없이 전체 맵에서 벽을 3개 새로 새우는 것이기 때문에 안전구역(0)인 지역 3개를 뽑아 1로 바꿔주면 벽을 세우는 것이 됩니다. (1,0) (1,1) (1,2) 이렇게 뽑나, (1,2) (1,1) (1,1) 이렇게 뽑나 순서 상관없이 3개를 뽑으면 되기 때문에 중복없는 조합을 생성하는 것과 같습니다.  

 

중복없는 조합은 아래 두 문제에서 이미 학습을 했기 때문에 같은 알고리즘 구조를 설계하면 된다는 것을 알 수 있습니다.

 

2025.01.07 - [Computer Science/알고리즘 문제] - C - [백준 1941] 소문난 칠공주 (feat. 백트래킹, DFS)

2025.01.07 - [Computer Science/알고리즘 문제] - C - [백준 6603] 로또 (feat. 백트래킹)

 

2번 과정일 경우,

"바이러스가 상하좌우로 퍼진다"라는 문제의 조건을 보면 바로 BFS를 떠올릴 수 있습니다.  아래 문제는 상하좌우 + BFS로 설계된 문제고, 이미 학습 했기 때문에 수월하게 작성했습니다.

 

2024.12.25 - [Computer Science/알고리즘 문제] - C - [백준 1926] 그림 (feat. BFS, 연결요소, 방향)

2024.12.25 - [Computer Science/알고리즘 문제] - C - [백준 2178] 미로탐색 (feat. BFS & 최단거리 탐색)

 

3, 4번 과정일 경우

BFS 탐색이 끝난 후 반복문을 통해 안전구역(0)을 카운팅한 후 최대값과 비교하면 되기 때문에 비교적 간단합니다.

 

정리하면 다음과 같습니다. 

 

문제 해결 전략

1. 벽 세우기 (조합, 백트래킹, DFS)
   • 모든 빈 칸 중 3개를 선택하여 벽을 세웁니다.
2. 바이러스 퍼뜨리기 (BFS)
   • 벽을 세운 후, BFS를 사용하여 바이러스가 퍼지는 시뮬레이션을 수행합니다.
3. 안전 영역 계산
   • 바이러스가 퍼진 후, 남아 있는 안전 영역의 크기를 계산합니다.
4. 최대값 갱신
   • 모든 경우를 시뮬레이션하여 안전 영역의 최대 크기를 갱신합니다

 

---

구현 코드

/*
https://www.acmicpc.net/problem/14502
C_BOJ_14502_연구소


맵 , 바이러스 , 벽 입력 받기

1. 빈칸(0)인 곳 중에서 3개 중복없는 조합으로 뽑기 (DFS, 백트래킹)
    1.1 depth = 벽의 갯수
    1.2 기저조건 depth 가 3일 경우
    1.3 visited 역할 >> map[i][j] = 1 > DFS > map[i][j] = 0 / 벽을 설정, 해제
2. Depth가 3일 경우 바이러스 위치로 부터 BFS 탐색(바이러스 전파) (2<= 바이러스 <= 10)
    2.1. 현 바이러스가 이미  visited = 1 이라면 다른 바이러스에서 방문했다는 뜻 = 서로 연결되어 있으니 중복 검사 필요 X
    2.2. 상하좌우 & visited == 0 && map[i][j] == 1
            visited == 1
            map[i][j] = 2;
            enqueue()
        }
    2.3. bfs 탐색이 끝났다면 반복문을 통해 전파 안된(0)의 갯수 새기 > 최대값일 경우 최종 결과를 담는 result 변수 갱신
바이러스 합이 가장 작은 것
*/
#include <stdio.h>
#include <string.h> // memcpy를 사용하기 위해 필요

int N, M = 0; //(세로 N, 가로 M)
int map[8][8];
int viruses[10][2];
int virus_num = 0;
int dir_x[4] = {1, -1, 0, 0};
int dir_y[4] = {0, 0, 1, -1};
int result = 0;
int queue[64][2];
int rear = 0;
int front = 0;

void enqueue(int x, int y) {
    queue[rear][0] = x;
    queue[rear][1] = y;
    rear++;
}

void dequeue(int *x, int *y) {
    *x = queue[front][0];
    *y = queue[front][1];
    front++;
}

void bfs(int copiedmap[8][8]) {
    int visited[8][8] = {0};
    front = 0;
    rear = 0;

    for (int v = 0; v < virus_num; v++) {
        if (visited[viruses[v][1]][viruses[v][0]] == 1) {
            continue;
        }
        enqueue(viruses[v][0], viruses[v][1]);
        visited[viruses[v][1]][viruses[v][0]] = 1;

        while (front < rear) {
            int x, y = 0;
            dequeue(&x, &y);
            for (int i = 0; i < 4; i++) {
                int nx = x + dir_x[i];
                int ny = y + dir_y[i];
                if (0 <= nx && nx < M && 0 <= ny && ny < N && copiedmap[ny][nx] != 1 && visited[ny][nx] == 0) {
                    visited[ny][nx] = 1;
                    copiedmap[ny][nx] = 2;
                    enqueue(nx, ny);
                }
            }
        }
    }

    int count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (copiedmap[i][j] == 0) {
                count++;
            }
        }
    }
    if (count > result) {
        result = count;
    }
}

void combination(int depth, int idx) {
    // 3개의 위치를 선택한 경우
    if (depth == 3) {
        int copiedmap[8][8];
        memcpy(copiedmap, map, sizeof(int) * 8 * 8);
        bfs(copiedmap);
        return;
    }

    // map을 탐색하며 조합 생성
    for (int i = idx; i < N * M; i++) {
        int x = i % M; // 열 계산
        int y = i / M; // 행 계산

        // 해당 위치가 비어있는 경우
        if (map[y][x] == 0) {
            map[y][x] = 1; // 선택
            combination(depth + 1, i + 1); // 재귀 호출
            map[y][x] = 0; // 선택 해제
        }
    }
}

int main() {
    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) {
                viruses[virus_num][0] = j;
                viruses[virus_num][1] = i;
                virus_num++;
            }
        }
    }

    combination(0, 0);
    printf("%d", result);
    return 0;
}

 

주요 변수 및 데이터 구조

int N, M = 0; // 연구소 크기 (세로 N x 가로 M)
int map[8][8]; // 연구소 맵 (최대 크기 8x8)
int viruses[10][2]; // 바이러스 위치를 저장하는 배열 (최대 10개)
int virus_num = 0; // 바이러스의 총 개수
int dir_x[4] = {1, -1, 0, 0}; // BFS 탐색 방향 (x축 이동)
int dir_y[4] = {0, 0, 1, -1}; // BFS 탐색 방향 (y축 이동)
int result = 0; // 안전 영역의 최대 크기 결과값
int queue[64][2]; // BFS를 위한 큐 (최대 64칸)
int rear = 0; // 큐의 끝 부분을 나타내는 인덱스
int front = 0; // 큐의 시작 부분을 나타내는 인덱스

• map: 연구소의 상태를 나타냅니다.
  값은 0(빈 칸), 1(벽), 2(바이러스)로 이루어져 있습니다.
• viruses: 바이러스의 초기 위치를 저장하는 배열입니다. 각 바이러스의 (x, y) 좌표를 저장합니다.
• dir_x와 dir_y: BFS 탐색 시 상하좌우로 이동하기 위한 방향 배열입니다.
• queue: BFS를 구현하기 위한 큐입니다. (x, y) 좌표를 저장합니다.

---

주요 함수 설명

1. enqueue와 dequeue

역할: BFS에서 사용할 큐의 삽입과 삭제를 구현합니다.

void enqueue(int x, int y) {
    queue[rear][0] = x; // 큐의 끝에 x좌표 추가
    queue[rear][1] = y; // 큐의 끝에 y좌표 추가
    rear++; // 큐의 끝 위치 증가
}

void dequeue(int *x, int *y) {
    *x = queue[front][0]; // 큐의 시작 부분에서 x좌표 추출
    *y = queue[front][1]; // 큐의 시작 부분에서 y좌표 추출
    front++; // 큐의 시작 위치 증가
}

• enqueue: 큐의 끝에 새로운 (x, y) 좌표를 추가합니다.
• dequeue: 큐의 앞에서 데이터를 꺼내고, 큐의 시작 위치를 한 칸 이동시킵니다.

---

2. bfs

역할: 바이러스를 확산시키고, 안전 영역(빈 칸)의 크기를 계산합니다.

void bfs(int copiedmap[8][8]) {
    int visited[8][8] = {0}; // 방문 여부를 확인하기 위한 배열
    front = 0; // BFS 큐의 초기화
    rear = 0;

    // 모든 바이러스 위치를 큐에 삽입
    for (int v = 0; v < virus_num; v++) {
        if (visited[viruses[v][1]][viruses[v][0]] == 1) {
            continue; // 이미 방문한 바이러스는 무시
        }
        enqueue(viruses[v][0], viruses[v][1]); // 큐에 바이러스 위치 삽입
        visited[viruses[v][1]][viruses[v][0]] = 1; // 방문 표시

        // BFS 탐색 시작
        while (front < rear) {
            int x, y = 0;
            dequeue(&x, &y); // 현재 탐색할 위치 가져오기
            for (int i = 0; i < 4; i++) { // 상하좌우 탐색
                int nx = x + dir_x[i];
                int ny = y + dir_y[i];
                if (0 <= nx && nx < M && 0 <= ny && ny < N && copiedmap[ny][nx] != 1 && visited[ny][nx] == 0) {
                    visited[ny][nx] = 1; // 방문 표시
                    copiedmap[ny][nx] = 2; // 바이러스 확산
                    enqueue(nx, ny); // 큐에 추가
                }
            }
        }
    }

    // 안전 영역 크기 계산
    int count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (copiedmap[i][j] == 0) { // 빈 칸일 경우
                count++;
            }
        }
    }
    if (count > result) { // 최대값 갱신
        result = count;
    }
}

작동 방식:

1. 초기 바이러스 위치를 큐에 추가.
2. 큐에서 하나씩 좌표를 꺼내, 상하좌우로 확산.
3. 확산이 끝난 후 안전 영역(빈 칸)의 개수를 세어 최대값을 갱신.

---

3. combination

역할: 백트래킹을 사용해 빈 칸 중 3개의 벽 위치를 선택합니다.

void combination(int depth, int idx) {
    if (depth == 3) { // 벽 3개를 모두 선택한 경우
        int copiedmap[8][8];
        memcpy(copiedmap, map, sizeof(int) * 8 * 8); // 맵 복사
        bfs(copiedmap); // 바이러스 확산 시뮬레이션
        return;
    }

    for (int i = idx; i < N * M; i++) { // 2차원 배열을 1차원으로 순회
        int x = i % M; // 열 계산
        int y = i / M; // 행 계산

        if (map[y][x] == 0) { // 빈 칸일 경우
            map[y][x] = 1; // 벽 설치
            combination(depth + 1, i + 1); // 재귀 호출
            map[y][x] = 0; // 벽 제거
        }
    }
}

작동 방식:

1. depth는 현재 설치된 벽의 개수를 나타냅니다.
2. 벽을 설치한 뒤, 다음 빈 칸으로 이동.
3. 벽 3개가 설치되면 bfs를 호출해 안전 영역 계산.

---

4. main

역할: 입력을 받고, 조합 탐색을 시작합니다.

int main() {
    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) { // 바이러스 위치 저장
                viruses[virus_num][0] = j;
                viruses[virus_num][1] = i;
                virus_num++;
            }
        }
    }

    combination(0, 0); // 벽 3개 조합 탐색 시작
    printf("%d", result); // 최대 안전 영역 출력
    return 0;
}

 

예제 입력

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

 

예제 출력

27

 

---

핵심 아이디어 요약

1. 백트래킹: 빈 칸 중 3개의 벽 조합을 탐색합니다.
2. BFS: 바이러스 확산 시뮬레이션을 통해 안전 영역 크기를 계산합니다.
3. 최적화: 모든 경우를 탐색해 안전 영역의 최대 크기를 출력합니다.

 

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.