14502-연구소

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

14502번: 연구소

문제 조건도 까다롭지 않고 배열의 입력값 범위도 최대 8이어서 시간복잡도 걱정 없이 부르트포스로 풀면 되겠다고 생각하였다.

문제 풀이에서도 딱히 걸리는건 없었고 최대한 시간와 메모리를 쓰면서 코드를 작성했다. 

간단히 짚고 넘어갈 부분은 리스트의 얕은 복사와 깊은 복사 부분 정도인것 같다. 처음에 받은 배열을 계속 깊은 복사하면서 BFS를 시도한다.

주어진 지도에서 3개의 좌표에 벽을 세워야 하는데 이는 배열의 0인 부분만 따로 담아서 이를 combination으로 막을 리스트를 만들어 놓고 반복문마다 해당하는 벽을 막은 새로운 지도를 만들어 BFS를 진행한다.

 

- combination: from itertools import combinations -> combinaions(arr, k)의 형태로 추출!

- 깊은 복사: import copy 후 copy.deepcopy(arr)의 형태로 복사!

 

from collections import deque
from itertools import combinations
import sys
import copy
input = sys.stdin.readline
N, M = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
zerospot = []
for x in range(N):
    for y in range(M):
        if board[x][y] == 0:
            zerospot.append((x,y))
bruteList = list(combinations(zerospot,3))  # 막을 위치 combi로 추출

dy = (0,1,0,-1)
dx = (1,0,-1,0)

def is_valid_coord(x, y):
    return 0 <= x < N and 0 <= y < M

def bfs(arr, x, y):
    dq = deque()
    dq.append((x,y))
    while dq:
        nowx, nowy = dq.popleft()
        for i in range(4):
            nx, ny = nowx+dx[i], nowy+dy[i]
            if is_valid_coord(nx,ny) and arr[nx][ny] == 0:
                arr[nx][ny] = 3
                dq.append((nx,ny)) 

ans = 0
for block in bruteList:
    tmpboard = copy.deepcopy(board)     # 깊은복사
    for i in range(3):
        tmpboard[block[i][0]][block[i][1]] = 1
    
    for x in range(N):
        for y in range(M):
            if tmpboard[x][y] == 2:
                bfs(tmpboard, x, y)
    
    cnt = 0
    for x in range(N):
        for y in range(M):
            if tmpboard[x][y] == 0:
                cnt += 1
    ans = max(ans, cnt)
print(ans)

 

 

 

 

 

참고:https://wikidocs.net/16038

12. 얕은 복사(shallow copy)와 깊은 복사(deep copy)