[백준] 14502 - 연구소 [Python(파이썬)]

문제

www.acmicpc.net/problem/14502

14502번: 연구소

 

풀이

이 문제는 두 가지의 작은 문제로 분할하여 생각해볼 수 있다.

1) 벽을 어떻게 세울 것인가?

2) 어떻게 탐색을 할 것인가?

 

BFS/DFS문제를 어느 정도 접해본 사람이라면 2)는 문제가 되지 않을 것이다.

그러나 문제는 바로 1)이다.

이 문제의 경우엔 n, m의 범위가 작기 때문에 브루트 포스를 이용하면 된다.

 

재귀를 이용하는 방법도 있지만, 시간을 줄이기 위해 처음 입력을 받을 때부터 빈 칸(0)의 좌표를 리스트에 저장해둔다.

 

그 다음 삼중 for문을 통해 3개의 벽을 세운다. 벽을 세운 후엔 바이러스를 퍼트리고(BFS 탐색), 세운 벽을 곧바로 허문다.

 

BFS탐색은 간단하다. 입력받을 때 체크해뒀던 바이러스의 좌표를 하나씩 큐에 담아준 후, 탐색을 시작하면 된다.

모든 탐색이 끝나면 빈 칸의 개수를 체크해서 기존의 최댓값보다 크다면 교체한다.

 

코드

import sys, copy, collections

n, m = map(int, sys.stdin.readline().split())
max_num = 0

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
empty_list = []
virus_list = []

EMPTY = 0
WALL = 1
VIRUS = 2

# 입력
g = [[0]*m for _ in range(n)]

for y in range(n):
    raw = [int(x) for x in sys.stdin.readline().split()]

    for x in range(m):
        g[y][x] = raw[x]
        if g[y][x] == EMPTY:
            empty_list.append([y, x])
        if g[y][x] == VIRUS:
            virus_list.append([y, x])

# bfs 탐색
def bfs(ng):
    q = collections.deque([])
    visited = [[False]*m for _ in range(n)]
    cnt = 0
    global max_num

    for virus in virus_list:
        q.append(virus)

    while q:
        cy, cx = q.popleft()

        for i in range(4):
            ny = cy + dy[i]
            nx = cx + dx[i]

            if ny < 0 or ny >= n or nx < 0 or nx >= m:
                continue
            if ng[ny][nx] == EMPTY and visited[ny][nx] == False:
                q.append([ny, nx])
                ng[ny][nx] = VIRUS
                visited[ny][nx] = True
    
    for i in range(n):
        cnt += ng[i].count(EMPTY)
    
    if max_num < cnt:
        max_num = cnt

# 벽 세우기
for i in range(len(empty_list)):
    for j in range(i):
        for k in range(j):
            y1, x1 = empty_list[i]
            y2, x2 = empty_list[j]
            y3, x3 = empty_list[k]

            g[y1][x1] = WALL
            g[y2][x2] = WALL
            g[y3][x3] = WALL

            ng = copy.deepcopy(g)
            bfs(ng)

            g[y1][x1] = EMPTY
            g[y2][x2] = EMPTY
            g[y3][x3] = EMPTY

print(max_num)