[백준] Baaaaaaaaaduk2 (Easy)

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

16988번: Baaaaaaaaaduk2 (Easy)

BFS를 활용하여 풀이하였습니다. 0으로 되어있는 칸들이 인간이 놓을 수 있는 위치들이므로 해당 위치들 중 2개를 뽑아서돌을 놓아보고 잡을 수 있는 최대 돌의 수를 얻는 방식으로 풀이하였습니다. 잡아먹을 수 있는 돌들의 집합인 경우를 체크하는 방법은 2번 돌들을 기준으로 BFS를 하다가 빈 공간을 만나면 잡아먹을 수 없는 그룹인 것을 이용하였습니다.

 

import sys
from itertools import combinations
from collections import deque

# sys.stdin = open("input.txt", "r")

n, m = tuple(map(int, input().split()))

board = [
    list(map(int, input().split()))
    for _ in range(n)
]

pos = []

for i in range(n):
    for j in range(m):
        if board[i][j] == 0:
            pos.append((i, j))


dys = [0, 1, 0, -1]
dxs = [1, 0, -1, 0]

ans = 0

visited = [
    [False] * m
    for _ in range(n)
]

def inRange(y, x):
    return 0 <= y < n and 0 <= x < m

def getCnt(startY, startX):
    global visited

    visited[startY][startX] = True
    cnt = 0
    q = deque([(startY, startX)])
    flag = False
    while q:
        y, x = q.popleft()
        cnt += 1

        for dy, dx in zip(dys, dxs):
            ny = y + dy
            nx = x + dx

            if inRange(ny, nx) and not visited[ny][nx]:
                # 다음이 비어있는 칸이면 잡아먹을 수 없다.
                if board[ny][nx] == 0:
                    flag = True

                # 다음이 흑색돌이면 탐색을 진행
                if board[ny][nx] == 2:
                    visited[ny][nx] = True
                    q.append((ny, nx))

    return -1 if flag else cnt

for selected in list(combinations(pos, 2)):
    visited = [
        [False] * m
        for _ in range(n)
    ]

    # 선택된 위치에 내 바둑돌은 둔다.
    board[selected[0][0]][selected[0][1]] = 1
    board[selected[1][0]][selected[1][1]] = 1

    cur = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] == 2 and not visited[i][j]:
                ret = getCnt(i, j)
                if ret > 0:
                    cur += ret

    #print(selected, cur)
    ans = max(cur, ans)
    # 원상복구
    board[selected[0][0]][selected[0][1]] = 0
    board[selected[1][0]][selected[1][1]] = 0

print(ans)

 

하지만, 이런 풀이는 매우 시간이 오래걸리게 되는데 만약 20 X 20의 칸에 검은 돌이 단 하나만 놓여있다면 

O(399C2 X N X M)이 되게 되므로 31,760,400만큼의 연산이 필요로 하게 됩니다. 매우 비효율적인 것을 알 수 있습니다. 

 

빠른 시간에 푸신 분의 코드를 참고하여 훨씬 더 효율적인 알고리즘으로 바꾸어보았습니다. 먼저, 2번 돌들이 놓인 그룹을 BFS로 탐색합니다. 탐색하면서 만나는 0인 위치의 개수를 세어두고 만약 2보다 작거나 같은 수만큼 만나게 되면 돌 2개 이하를 놓아서 돌을 잡을 수 있는 그룹이 되게 됩니다. 이런 그룹들을 저장해두고 그룹에 포함된 요소들의 조합을 활용하여 잡을 수 있는 최대의 돌을 얻으면 됩니다.

 

import sys
from collections import deque

#sys.stdin = open("input.txt", "r")

n, m = tuple(map(int, input().split()))

board = [
    list(map(int, input().split()))
    for _ in range(n)
]

pos = []

dys = [0, 1, 0, -1]
dxs = [1, 0, -1, 0]


group = []

def inRange(y, x):
    return 0 <= y < n and 0 <= x < m

def bfs(startY, startX):
    board[startY][startX] = 3
    cnt = 0

    q = deque([(startY, startX)])
    needs = set()
    while q:
        y, x = q.popleft()
        cnt += 1

        for dy, dx in zip(dys, dxs):
            ny = y + dy
            nx = x + dx

            if inRange(ny, nx):
                # 다음 칸이 비어있는 경우
                if (ny, nx) not in needs and board[ny][nx] == 0:
                    needs.add((ny, nx))

                if board[ny][nx] == 2:
                    board[ny][nx] = 3
                    q.append((ny, nx))
    # 현재 그룹을 잡아먹기 위해 필요한 칸이 2칸 이하인 경우
    if len(needs) <= 2:
        group.append((needs, cnt))

ans = 0
cur_group = []

# cnt: 현재 잡은 돌의 개수
# start: combination을 위한 개수
# edges: 놓은 돌의 위치들
# count: 현재 선택 위치
def combi(cnt, start, edges, count):
    global ans
    if len(edges) > 2:
        return

    ans = max(ans, cnt)

    if count == len(group):
        return

    for i in range(start, len(group)):
        cur_group.append(group[i])

        cur_set = set(edges)
        for e in group[i][0]:
            cur_set.add(e)

        combi(cnt + group[i][1], i + 1, cur_set, count + 1)

        cur_group.pop()

for i in range(n):
    for j in range(m):
        if board[i][j] == 2:
            bfs(i, j)

combi(0, 0, set(), 0)

print(ans)