16988

백준 16988번

Link: 16988번: Baaaaaaaaaduk2 (Easy)

---

문제 설명

아주 오랫만에 BFS 문제.

삼성 역량테스트 대비한 특강에서 내준 문제였는데, 보자마자 예전에 풀었던 연구소 문제가 생각났다.

거기까지는 좋았다. 거기까지는.

여기까지 떠올리고 DFS를 활용하여 2개의 돌을 놓는 위치를 정하는데까지는 성공했는데, 이제 죽일 수 있는 돌이 몇개인지 세는게 가장 큰 문제였다.

이거 해결해보려고 정말 많은 고민을 해봤고 시도해봤는데 전부 허사였다.

결국 답을 물어봐가면서 풀긴 했는데, 풀고 나니 내가 생각했던 방법이랑 크게 차이는 없는것 같지만 내가 생각지도 못한 부분들이 여럿 보였다.

난 map에서 2로 표기된 점들에 대해 BFS를 통해 주변에 0이 없어 더 나갈 곳이 있는지 없는지만 파악하는 방법을 생각했는데, 더 나갈 수 없다는 걸 파악하는건 좋지만 가장 중요한 갯수 세는건 못한다.

주변에 이 문제를 BFS로 푼 사람이 있어 물어봐가면서 풀었는데, 방법은 다음과 같다.

1) DFS를 통해 2개의 착수점을 찾는다.

2) 2개의 점을 찾았으면, 전역변수로 설정된 visit 배열을 초기화한다.

3) map의 각 점들에 대해 값이 2이고 방문하지 않았다면 그 점을 방문했다고 표시하고, 그 점에 대해 BFS를 실행한다.

4) 현재 찾은 착수점에 돌을 놓은 상태로 map을 갱신한다. (memcpy 함수 사용)

5) BFS에 들어가면, 우선 현재 탐색하고 있는 점은 방문한 점이므로 count 값을 1 늘린다.

6) for문을 순회하며 다음 BFS로 탐색할 점을 찾는다. 이때, 다음 지점이 방문하지 않은 지점이며 map의 다음 방문 지점 값이 2일 때에만 진행한다. 또, 현재 죽은 돌의 갯수를 세기 위해 count 값을 1 늘린다.

7) 만약 다음 지점의 map 값이 0이라면 이는 돌들이 완벽하게 포위된 상태가 아님을 의미한다. 전역변수로 설정된 finish 값을 true로 바꿔준다.

8) BFS를 완료한 후, finish 값이 true라면 탐색한 돌과 그 주변 돌들은 죽은 것이 아니므로, 0을 리턴한다. 반대의 경우 BFS를 통해 늘려준 count 값을 리턴한다.

9) map 값이 2이며 방문하지 않은 모든 점들에 대해 탐색을 진행해야 하므로, 현재까지의 BFS 결과를 따로 누적한다. 나머지 점들에 대해서 반복한다.

10) 모든 방문이 끝났다면 현재까지 누적된 BFS 결과와 이전 최대값을 비교해 최대값을 갱신한다.

11) 이 과정을 모든 착수 가능한 경우에 대해 반복한다.

이런 과정을 통해 최대값을 구하는 방법이다.

BFS를 사용하는것까지는 떠올렸는데 디테일하게 BFS를 통해 합까지 구하는 방법을 생각하지 못한 점이 매우 아쉬웠다.

또 처음에 돌릴때는 memcpy 대신 이중 for문 돌며 map값을 설정해줬는데 그러니 시간초과나더라.

혹시나 해서 memcpy로 바꿔봤더니 바로 통과됐다.

BFS에 대해서는 자신있다고 생각했는데 아직도 부족한점이 너무 많다.

진짜로 마음잡고 다시 하루에 하나이상 풀어가며 실력 더 키워야겠다.

---

정답 코드

//
// Created by Keith_Lee on 05/03/2019.
//

#include <iostream>
#include <queue>
#include <strings.h>
#include <memory.h>

using namespace std;

int N, M;

int map[20][20];
int tempMap[20][20];
bool visit[20][20];

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

int maxValue = 0;
bool finish = false;

int BFS(int x, int y){
    int count = 0;

    queue<pair<int, int>> Queue;

    memcpy(map, tempMap, sizeof(tempMap));

    Queue.push(make_pair(x, y));

    count++;

    while(!Queue.empty()){
        int currentX = Queue.front().first;
        int currentY = Queue.front().second;
        Queue.pop();

        for(int i=0; i<4; i++){
            int nextX = currentX + dx[i];
            int nextY = currentY + dy[i];

            if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < M){
                if(!visit[nextX][nextY] && map[nextX][nextY] == 2){
                    visit[nextX][nextY] = true;
                    count++;
                    Queue.push(make_pair(nextX, nextY));
                }
                else if(map[nextX][nextY] == 0){
                    finish = true;
                }
            }
        }
    }

    if(finish){
        return 0;
    }

    return count;
}

void DFS(int count){
    if(count == 2){
        int temp = 0;
        bzero(visit, sizeof(visit));

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(!visit[i][j] && tempMap[i][j] == 2){
                    finish = false;
                    visit[i][j] = true;
                    temp += BFS(i, j);
                }
            }
        }

        maxValue = maxValue < temp ? temp : maxValue;

        return;
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(tempMap[i][j] == 0){
                tempMap[i][j] = 1;
                DFS(count+1);
                tempMap[i][j] = 0;
            }
        }
    }
}

int main(){
    cin >> N >> M;

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

            tempMap[i][j] = map[i][j];
        }
    }

    DFS(0);

    cout << maxValue << '\n';

    return 0;
}

---