BOJ 14502. 연구소

🔎 BOJ 14502. 연구소 (골드4)

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

14502번: 연구소

 

💡 Sol

import sys
import copy
from collections import deque
from itertools import combinations

N, M = list(map(int, sys.stdin.readline().split()))
array, zero, two = [], [], []
one = 3
for i in range(N):
    new = list(map(int, sys.stdin.readline().split()))
    for j in range(M):
        if new[j] == 0:
            zero.append((i, j))
        elif new[j] == 2:
            two.append((i, j))
        else:
            one += 1
    array.append(new)

comb = list(combinations(zero, 3))
min_cnt = N * M

for c in comb:
    # array 복사
    c_array = copy.deepcopy(array)
    # visited 생성
    v = [[0] * M for _ in range(N)]
    # 벽 3개 세움
    for i, j in c:
        c_array[i][j] = 1
        v[i][j] = 1
    # q 생성
    q = deque(copy.deepcopy(two))

    cnt = len(two)
    while q:
        si, sj = q.popleft()
        for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ni, nj = si + di, sj + dj
            if 0 <= ni < N and 0 <= nj < M and not v[ni][nj] and c_array[ni][nj] == 0:
                q.append((ni, nj))
                v[ni][nj] = 1
                cnt += 1
        if min_cnt < cnt :
            break
    if min_cnt > cnt:
        min_cnt = cnt
print((N * M) - one - min_cnt)

 

💭 TIL

Python 순열 / 조합 라이브러리

from itertools import *

1. 순열 (permutaions)
   • 중복을 허용하지 않음
   • 순서에 의미가 있음
   • list(permutations([1, 2, 3], 2)) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
2. 중복 순열 (product)
   • 중복을 허용하는 순열
   • list(product([1, 2, 3], repeat=2)) # [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
3. 조합 (combinations)
   • 중복을 허용하지 않음
   • 순서에 의미가 없음
   • list(combinations([1, 2, 3], 2)) # [(1, 2), (1, 3), (2, 3)]
4. 중복 조합 (combinations_with_replacement)
   • 중복을 허용하는 조합
   • list(combinations_with_replacement([1, 2, 3], 2)) # [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]