[C++/14502] 연구소 - using BFS

문제: 연구소

 

아이디어: BFS

전형적인 BFS 문제다. [특정 map에서 무언가가 퍼져나가는 경우의 수 or 시간 or 집합의 수] 등등의 대부분은 BFS/DFS로 해결 가능하다.

이 문제의 핵심은 어떻게 3개의 벽을 세울 수 있는 경우의 수를 계산하느냐에 달려있다. 나의 경우에는 3개의 벽을 세울 수 있는 모든 가능한 경우의 수를 계산했다.

벽은 빈칸에만 세울 수 있고 어떻게 벽을 세울 때 best 결과가 나올지 모르기 때문에 full search를 하도록 했다. 왜냐하면 애초에 제한 사항에 다음과 같이 map의 크기가 8x8이 최대이기 때문에 가능한 모든 경우의 수를 세어도 무방했다.

다음 로직에 따라 알고리즘을 구성했다.

1. map에서 모든 칸을 확인하며 빈칸일 때 3개의 벽을 세울 수 있는 경우의 수를 확인함
2. (1)번의 경우의 수마다 벽을 세웠다고 가정하고 BFS를 돌며 안전한 칸의 수를 센다
3. 최대값보다 (2)의 결과값이 크다면 최대값을 갱신한다.
4. 모든 칸에 대하여 이 작업을 반복한다.

 

구현

BFS는 그냥 정석대로 구현했고, 나의 코드 구현의 핵심은 3개 벽을 세울 수 있는 경우의 수를 계산하는 부분이다.

temp는 map의 2차원 배열을 복사한 2차원 배열이다.

 

    for(int i = 0;i < N * M;i++) {
    	// 벽을 세울 수 없는 경우
        if (map[i / M][i % M] == 2 || map[i / M][i % M] == 1)
            continue;
            
        // 벽을 세울 수 있다면 temp 배열의 값을 1로 만들어줌
        temp[i / M][i % M] = 1;
        for(int j = i + 1;j < N * M;j++) {
        	// 벽을 세울 수 없는 경우
            if (map[j / M][j % M] == 2 || map[j / M][j % M] == 1)
                continue;
                
            // 벽을 세울 수 있다면 temp 배열의 값을 1로 만들어줌
            temp[j / M][j % M] = 1;
            for(int k = j + 1;k < N * M;k++) {
            	// 벽을 세울 수 없는 경우
                if (map[k / M][k % M] == 2 || map[k / M][k % M] == 1)
                    continue;
                    
                // 벽을 세울 수 있다면 temp 배열의 값을 1로 만들어줌
                temp[k / M][k % M] = 1;
                
                // BFS를 돌며 안전 영역 계산하고 최대값 갱신
                int count = bfs(temp);
                result = max(count, result);
                
                // 값 복원
                temp[k / M][k % M] = map[k / M][k % M];
            }
            // 값 복원
            temp[j / M][j % M] = map[j / M][j % M];
        }
        // 값 복원
        temp[i / M][i % M] = map[i / M][i % M];
    }

 

여기서 모든 칸을 돌며 계산을 할 때 N*M 번을 한번에 돌도록 위와 같이 for문을 작성했다.

이때 index는 행과 열을 따로 지정하지 않았기 때문에 index를 열의 크기로 나눈 몫을 행, index를 열의 크기로 나눈 나머지를 열 로 계산해서 2차원 배열에 접근했다.

이때 접근할 수 없는 경우, 즉 2차원 배열의 값이 2(바이러스) 또는 1(이미 벽)인 경우에는 continue를 통해 벽을 세울 수 있는 경우의 수만 계산하도록 구현했다. 

그 다음 3개의 벽이 모두 세워졌다면 bfs 함수를 돌면서 안전영역을 계산하고 최대값을 갱신한다.

이후, 가능한 3개 벽의 경우의 수를 다시 계산하기 위해 temp 배열의 값을 다시 map 배열의 값으로 복원해준다.

 

전체 코드는 다음과 같다.

 

int bfs(vector<vector<int>> map) {
    int count = 0;
    
    int visited[10][10] = {0, };
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    for(int i = 0;i < map.size();i++) {
        for(int j = 0;j < map[0].size();j++) {
            if (map[i][j] == 2) {
                queue<pair<int, int>> temp;
                visited[i][j] = 1;
                temp.push({i, j});
                
                while(!temp.empty()) {
                    int x = temp.front().first;
                    int y = temp.front().second;
                    temp.pop();
                    
                    for(int dir = 0;dir < 4;dir++) {
                        int tempX = x + dx[dir];
                        int tempY = y + dy[dir];
                        
                        if (tempX < 0 || tempY < 0 || tempX >= map.size() || tempY >= map[0].size())
                            continue;
                        
                        if (map[tempX][tempY] == 0 && visited[tempX][tempY] == 0) {
                            map[tempX][tempY] = 2;
                            visited[tempX][tempY] = 1;
                            temp.push({tempX, tempY});
                        }
                    }
                    
                }
                
            }
        }
    }

    for(int i = 0;i < map.size();i++) {
        for(int j = 0;j < map[0].size();j++) {
            if (map[i][j] == 0)
                count++;
        }
    }

    return count;
}


int main() {
    int N, M;
    cin>>N>>M;
    
    vector<vector<int>> map(N, vector<int>(M, 0));
    vector<vector<int>> temp(N, vector<int>(M, 0));
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < M;j++) {
            cin>>map[i][j];
            temp[i][j] = map[i][j];
        }
    }
    
    // 벽을 세울 수 있는 가능한 경우의 수 모두 계산
    int result = 0;
    for(int i = 0;i < N * M;i++) {
        if (map[i / M][i % M] == 2 || map[i / M][i % M] == 1)
            continue;
        temp[i / M][i % M] = 1;
        for(int j = i + 1;j < N * M;j++) {
            if (map[j / M][j % M] == 2 || map[j / M][j % M] == 1)
                continue;
            temp[j / M][j % M] = 1;
            for(int k = j + 1;k < N * M;k++) {
                if (map[k / M][k % M] == 2 || map[k / M][k % M] == 1)
                    continue;
                temp[k / M][k % M] = 1;
                // 벽을 세웠다면 bfs를 돌며 안전한 칸의 수 계산
                int count = bfs(temp);
                result = max(count, result);
                temp[k / M][k % M] = map[k / M][k % M];
            }
            temp[j / M][j % M] = map[j / M][j % M];
        }
        temp[i / M][i % M] = map[i / M][i % M];
    }
    cout<<result<<endl;
    
    return 0;
}

 

 

사실 이 문제의 난이도는 BFS 개념을 다 알고있다고 하면 중~중상 정도에 해당한다고 생각한다.

그런데 나는 2일이나 걸렸는데 원인은 for문을 작성할때 내가 아~무 생각없이

 

 for(int i = 0;i < N * M;i++) {
        if (map[i / M][i % M] == 2 || map[i / M][i % M] == 1)
            continue;
        temp[i / M][i % M] = 1;
        for(int j = i + 1;j < N * M;j++) {
            if (map[i / M][i % M] == 2 || map[i / M][i % M] == 1)
                continue;
            temp[j / M][j % M] = 1;
            for(int k = j + 1;k < N * M;k++) {
                if (map[i / M][i % M] == 2 || map[i / M][i % M] == 1)
                // 생략

 

이렇게 map 2차원 배열의 인덱스 값을 확인하는 if 문을 복붙해놓고 j, k로 안바꿔서 값이 제대로 안나왔기 때문이었다.

교훈: 복붙은 항상 조심해야 한다.