14502 - 백준 - 연구소

1. 문제 출처

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

14502번: 연구소

2. 풀이

크게는 브루트 포스를 이용하여 모든 경우의 수를 구한 다음에 가장 결과가 큰값을 출력한다.

문제는 벽을 세우는 과정인데 이는 dfs ,bfs 2가지로 해결 할 수 있다.

(시간이 오래 걸리므로 python3가 아닌 pypy3 로 실행해야 시간 초과가 되지 않는다.)

 

bfs

import copy
from collections import deque
# 움직이는 방향
dy = [0,0,-1,1]
dx = [-1,1,0,0]
# 벽의 개수
wall = 0

# 높이 너비 받기
h,w  = map(int,input().split())
# 연구소 좌표 값을 저장하는 리스트
lab = [[] for _ in range(h)]
for idx in range(h):
    lab[idx] = list(map(int,input().split()))
# 결과값
result = 0

# bfs 실시
def bfs():
	# 덱을 이용하여 bfs를 한다.
    queue = deque()
    temp = copy.deepcopy(lab)
    for i in range(h):
        for j in range(w):
            if temp[i][j] == 2:
                queue.append((i, j))
	# 덱이 빌 때 까지
    while queue:
        # 덱에서의 첫번째 원소를 빼준다.
        x, y = queue.popleft()

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

            if 0<=nx<h and 0<=ny<w:
                if temp[nx][ny] == 0:
                    temp[nx][ny] = 2
                    queue.append((nx, ny))

    global result
    cnt = 0
	
    for line in temp:
        cnt += line.count(0)

    result = max(result, cnt)

def solution(wall):
# 만약 벽을 3개 추가 했다면
    if wall ==3:
    # 바이러스를 퍼트린다.
        bfs()
        return
	# 아니라면 재귀를 이용하여 벽이 3개가 될 때까지 1을 추가한다.
    for i in range(h):
        for j in range(w):
            if lab[i][j] == 0:
                lab[i][j] = 1
                solution(wall+1)
                lab[i][j] = 0

solution(wall) 
print(result)

dfs

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

wall = 0


h,w  = map(int,input().split())
lab = [[] for _ in range(h)]
for idx in range(h):
    lab[idx] = list(map(int,input().split()))
temp_lab = [[0 for _ in range(w)] for _ in range(h)]
result = 0
# 위 부분은 temp_lab을 제외하고 bfs와 동일


# 바이러스 퍼트리는 함수
def spread_virus(i,j):
    for idx in range(4):
        x = i +dx[idx]
        y = j +dy[idx]
        if (0<=x<h) and (0<=y<w):
            if temp_lab[x][y] == 0:             
                temp_lab[x][y] = 2
                spread_virus(x,y)


def dfs(wall):
    global result 
    # 만약 벽이 3개 추가 되었다면
    if wall == 3:
    # temp_lab로 복사를 하고
        for i in range(h):
            for j in range(w):
                temp_lab[i][j] = lab[i][j]
                
    # 각 원소 중 2인 것을 찾아서 바이러스를 퍼트린다.
        for i in range(h):
            for j in range(w):
                if temp_lab[i][j] == 2:
                    spread_virus(i,j)
        result = max(result,get_safe_count())
        return
    # 벽이 3개 추가가 안되었다면
    for i in range(h):
        for j in range(w):
        # 벽이 3개가 추가 될때 까지 추가한다.
            if wall <3:
                if lab[i][j] == 0:
                    lab[i][j] = 1
                    wall +=1
                    dfs(wall)
                    wall -=1
                    lab[i][j] = 0
                    

    
def get_safe_count():
    count = 0 
    for line in temp_lab:
        for i in line:
            count = count+1 if i==0 else count
    return count

dfs(wall) 
print(result)