[백준(BOJ)] 14520번 연구소 C++

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

14502번: 연구소

 

 

어떤 문제인가?

빈칸, 벽, 바이러스 총 세 종류로 맵을 채울 수 있다.

이때, 임의의 벽을 추가로 3개 세운다.

추가로 세운 벽의 위치에 따라 안전한 공간의 개수가 바뀐다.

임의의 벽을 세웠을 때 안전한 공간의 최대 개수를 출력하면 된다.

 

접근 방법

코드를 먼저 보면 복잡하고 이해하기 어려울 것 같으니

대략적인 문제풀이의 방향을 보고 코드를 보자!

 

1. map에 입력받기

이때, 바이러스의 위치와 빈칸(0)의 위치를 기억하기!(virus 벡터, blank 벡터)

바이러스의 위치는 탐색 시작 위치를 알기 위해

빈칸의 위치는 벽을 세울 위치를 알기 위해!

 

2.  그러면 blank벡터에 빈칸의 (x, y) 좌표를 저장했으니 우리는 이 중 벽을 세울 위치 3개를 뽑으면 된다.

map의 크기가 최대 8*8이어서 조합을 사용해도 시간 초과가 발생하지 않는다.

 

3. copyMap에 입력받은 map을 복사한다 + 뽑은 3개 벽의 위치에 대해 copyMap의 인덱스 값을 1(벽)로 바꿔준다.

 

4. bfs 함수를 실행한다

 

5. copyMap에 남아있는 0의 개수를 측정한다.

 

모든 조합의 경우에 대해 2~5의 과정을 반복하며

가장 큰 0의 개수를 구한다.

 

이제 코드를 보자.

 

 

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int map[9][9];
int copyMap[9][9];
int n, m;

이동에 필요한 dx, dy배열

입력을 저장할 map배열

map의 복사본 + 새로운 벽 3개를 저장할 copyMap배열

map의 크기 n, m

 

 

queue<pair<int, int>> virus;

vector<pair<int, int>> blank;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> map[i][j];

        if (map[i][j] == 2) {
            virus.push({i, j});
        } else if (map[i][j] == 0) {
            blank.push_back({i, j});
        }

    }
}

설명했듯이, 지도를 입력받으면서 2이면 바이러스 벡터에 추가하고, 0이면 blank벡터에 추가한다.

당연히 x, y좌표를 저장해야 하니 벡터와 pair를 사용했다.

 

 

vector<bool> temp(blank.size(), false);

for (int i = 0; i < 3; i++) {
    temp[i] = true;
}

do {
    reset();

    for (int i = 0; i < blank.size(); i++) {
        if (temp[i]) {
            copyMap[blank[i].first][blank[i].second] = 1;
        }
    }

   bfs();
} while (prev_permutation(temp.begin(), temp.end()));

이 부분은 조합을 사용하는 부분이다. blank의 크기만큼 생성된 temp배열을 false로 선언해주고, 뽑을(세울 벽) 수의 개수(3)만큼 true로 해준다.

 

do-while문을 돌며 조합의 경우의 수를 확인할 것이다.

prev_permutaion함수를 통해 temp의 true가 섞이게 된다.

 

 

void reset() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            visited[i][j] = false;
            copyMap[i][j] = map[i][j];
        }
    }
}

 

do구문에서는 먼저 reset함수를 통해 사용했던 배열들을 초기화해준다.

 

그리고, blank의 크기만큼 반복문을 돌며

i 번째 인덱스가 true라면 copyMap의 인덱스(blank에 저장된 좌표) 값을 1로 바꿔준다. = 벽 세우기

 

이제 벽이 3개가 추가로 세워진 copyMap을 갖고 bfs를 실행하면 된다.

 

 

int maxNum = 0;

0의 최대 개수를 저장할 maxNum이다.

 

void bfs() {

    queue<pair<int, int>> q = virus;

    while (!q.empty()) {
        int y1 = q.front().first;
        int x1 = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int y2 = y1 + dy[i];
            int x2 = x1 + dx[i];

            if (x2 < 0 || y2 < 0 || x2 >= m || y2 >= n) {
                continue;
            }

            if (copyMap[y2][x2] == 1) {
                continue;
            }

            if (copyMap[y2][x2] == 0) {
                copyMap[y2][x2] = 2;
                q.push({y2, x2});
            }
        }
    }
    int cnt = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (copyMap[i][j] == 0) {
                cnt++;
            }
        }
    }

    maxNum = max(maxNum, cnt);

}

bfs함수이다.

탐색해나갈 큐를 미리 입력받은 virus벡터로 복사받는다.

그리고 다른 그래프 탐색 문제와 다를 것 없이

이동한 좌표가 n*m의 범위를 벗어 낫는지, 이동한 좌표가 벽인지 예외 처리해준다.

만약 빈칸(0)이라면 바이러스에 감염시켜 2로 바꿔준다.

 

 

이제 모든 탐색이 끝났다면(while문 종료)

 

copyMap에 남아있는 0의 개수를 세어준다.

그리고 maxNum과 비교해 더 큰 값을 maxNum으로 할당해준다.

 

조합의 모든 경우의 수를 돌며 bfs를 끝냈다면

maxNum의 0의 최대 개수가 저장되어 있을 것이다.

 

 

cout << maxNum;

마지막으로 maxNum을 출력해주면 끝!

 

 

무엇이 어려웠는가?

벽을 세우는 것 외에는 어려울 것이 없었다.

하지만 벽을 세우는 방법을 생각하는 것이 정말 어려웠다....

 

처음엔 재귀 형식으로도 해봤지만 코드가 너무 복잡해져서 다른 방법을 찾았다.

근데 아무리 생각해도 효율적인 방법이 떠오르지 않아 결국 차선책으로 조합을 사용하기로 했다.

 

이 문제는 n, m의 범위가 최대 8이어서 조합을 사용할 수 있었지만

범위가 더 컸다면 시간 초과로 풀지 못했을 것이다..

 

풀었음에도 아쉬움이 남는 문제였다.

 

배운 점

이제 어느 정도 기초적인 그래프 탐색은 가능해졌다고 생각했다.

그런데 조금만 조건이 복잡해지자 바로 막혀버리니까.. 슬프다...

 

iOS도 같이 공부하느라 알고리즘에 투자하는 시간이 상대적으로 적어지고,

고민할 시간이 적어지다 보니 해답이 잘 안 보이는 것도 당연한 게 아닌가 싶다..

 

이 문제 말고도 심화된 그래프 탐색 문제 몇 문제를 더 풀었는데,

테스트 케이스는 전부 통과하는데 틀리는 것도 있고, 시간제한을 맞추지 못한 문제들도 있다.

반례를 찾지도 못하겠고,, 시간을 줄이면서 풀이할 방법도 잘 떠오르지 않는다ㅠㅠ,,

 

더 열심히 합시다...

 

전체 코드

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/DFS%EC%99%80%20BFS/14502.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.