14502번: 연구소

문제링크

C++

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

int N, M;

int my_map[8][8];

int    ret;

int num_empty;

int to_subtract;

queue<pair<int, int> > Q;

vector<pair<int, int> > emptypos;

int di[4] = {0, 0, -1, 1};
int dj[4] = {1, -1, 0, 0};

int visited[8][8];

void    find2(){
    queue<pair<int, int> > q = Q;
    memset(visited, 0, sizeof(visited));
    while (!q.empty()){
        pair<int, int> tmp = q.front();
        q.pop();
        int i, j;
        for (int idx = 0; idx < 4; idx++){
            i = tmp.first + di[idx];
            j = tmp.second + dj[idx];
            if (!(i >= 0 && i < N && j >= 0 && j < M))
                continue ;
            if (my_map[i][j] == 0 && visited[i][j] == 0){
                to_subtract++;
                visited[i][j] = 1;
                q.push({i, j});
            }
        }
    }
    if (num_empty - to_subtract > ret)
    {
        ret = num_empty - to_subtract;
    }
    to_subtract = 0;
}

void    find(){
    for (int i = 0; i < num_empty - 2; i++){
        my_map[emptypos[i].first][emptypos[i].second] = 1;
        for (int j = i + 1; j < num_empty - 1; j++){
            my_map[emptypos[j].first][emptypos[j].second] = 1;
            for (int k = j + 1; k < num_empty; k++){
                my_map[emptypos[k].first][emptypos[k].second] = 1;
                find2();
                my_map[emptypos[k].first][emptypos[k].second] = 0;
            }
            my_map[emptypos[j].first][emptypos[j].second] = 0;
        }
        my_map[emptypos[i].first][emptypos[i].second] = 0;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int n = 0; n < N; n++){
        for (int m = 0; m < M; m++){
            cin >> my_map[n][m];
            if (my_map[n][m] == 0){
                emptypos.push_back({n, m});
            }else if (my_map[n][m] == 2){
                Q.push({n, m});
            }
        }
    }
    num_empty = emptypos.size();
    find();
    ret -= 3;
    cout << ret << "\n";
}

Python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

my_map = []

for _ in range(N):
    my_map.append(list(map(int, input().split())))

emptypos = []
queue = []
for i in range(N):
    for j in range(M):
        if my_map[i][j] == 0:
            emptypos.append([i, j])
        elif my_map[i][j] == 2:
            queue.append([i, j])
num_empty = len(emptypos)

ret = 0
to_subtract = 0
def find():
    global ret, queue
    di = [0, 0, -1, 1]
    dj = [-1, 1, 0, 0]
    queue_copy = queue.copy()
    global N, M
    global my_map
    visited = [[0 for _ in range(M)] for __ in range(N)]
    to_subtract = 0
    while queue_copy:
        tmp = queue_copy[0]
        queue_copy.pop(0)
        for idx in range(4):
            i = tmp[0] + di[idx]
            j = tmp[1] + dj[idx]
            if not (i >= 0 and i < N and j >= 0 and j < M):
                continue
            if my_map[i][j] == 0 and visited[i][j] == 0:
                # print(i, j)
                to_subtract += 1
                visited[i][j] = 1
                queue_copy.append([i, j])
    if num_empty - to_subtract > ret:
        ret = num_empty - to_subtract

for i in range(num_empty - 2):
    my_map[emptypos[i][0]][emptypos[i][1]] = 1
    for j in range(i + 1, num_empty - 1):
        my_map[emptypos[j][0]][emptypos[j][1]] = 1
        for k in range(j + 1, num_empty):
            my_map[emptypos[k][0]][emptypos[k][1]] = 1
            find()
            my_map[emptypos[k][0]][emptypos[k][1]] = 0
        my_map[emptypos[j][0]][emptypos[j][1]] = 0
    my_map[emptypos[i][0]][emptypos[i][1]] = 0
ret -= 3
print(ret)

• BFS/DFS + 브루트포스로 풀었다
• 파이썬에서 깊은 복사/얕은 복사에서 많이 헤맸다
  • [[0 * N] * M]과 같은 형태로 초기화하면 M개의 리스트가 같은 리스트를 가리키는 상태
    • [[0 for _ in range(N)] for __ in range(M)]로 초기화하거나
    • list()나 []로 초기화한 후 append( )사용
  • 리스트를 새 리스트에 복사할 때도 주의
    • a = b로 할당하면 얕은 복사
    • a = b.copy()로 깊은 복사하거나
    • a = b[:]로 슬라이싱 이용
• $O(\binom{N * M}{3} * (N * M))$의 시간복잡도