연구소 [백준 14502번]

문제

 

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

14502번: 연구소

내 풀이 1

 

combinations 사용하여 벽을 세웠다.

시간 : 700ms

 

from collections import deque
from itertools import combinations
from copy import deepcopy

N, M = map(int, input().split())
board, zero = [], []
for i in range(N):
    b = input().split()
    for j in range(M):
        if b[j] == '0': zero.append((i, j))
    board.append(b)
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
MAX = 0

def bfs(i, j, nboard):
    dq = deque()
    check = [[False]*M for _ in range(N)]
    dq.append((i, j))
    check[i][j] = True
    while dq:
        x, y = dq.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<M and not check[nx][ny] and nboard[nx][ny] == '0':
                check[nx][ny] = True
                nboard[nx][ny] = '2'
                dq.append((nx, ny))

walls_combi = list(combinations(zero, 3))
for walls in walls_combi:
    nboard = deepcopy(board)
    for i, j in walls:
        nboard[i][j] = '1'
    
    for i in range(N):
        for j in range(M):
            if board[i][j] == '2':
                bfs(i, j, nboard)
    cnt = 0
    for i in range(N):
        for j in range(M):
            if nboard[i][j] == '0':
                cnt += 1
    MAX = max(MAX, cnt)
print(MAX)

 

내 풀이 2

 

백트래킹 사용하여 벽을 세웠다.

시간 : 2456ms

 

from collections import deque
from copy import deepcopy

N, M = map(int, input().split())
board = []
for i in range(N):
    board.append(input().split())
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
MAX = 0

def bfs():
    global MAX
    dq = deque()
    check = [[False]*M for _ in range(N)]
    nboard = deepcopy(board)
    
    for i in range(N):
        for j in range(M):
            if board[i][j] == '2':
                dq.append((i, j))
                check[i][j] = True

    while dq:
        x, y = dq.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<M and not check[nx][ny] and nboard[nx][ny] == '0':
                check[nx][ny] = True
                nboard[nx][ny] = '2'
                dq.append((nx, ny))
    cnt = 0
    for i in range(N):
        for j in range(M):
            if nboard[i][j] == '0':
                cnt += 1
    MAX = max(MAX, cnt)

def make_wall(wall):
    if wall == 3:
        bfs()
        return
    for i in range(N):
        for j in range(M):
            if board[i][j] == '0':
                board[i][j] = '1'
                make_wall(wall+1)
                board[i][j] = '0'
make_wall(0)
print(MAX)

 

총평

백트래킹 사용한 풀이가 더 멋있어 보이지만, combinations 사용한 방법이 더 효율적이다.

멋있다고 다가 아니라는 것을 배웠다.