[BOJ 14502] 연구소

Breadth First Search

BOJ 14502번 연구소

문제

구조화

• 바이러스가 없고, 벽이 아닌 빈 공간의 좌표를 저장
  • 이 공간에만 벽 세우기 가능
• 저장된 Empty Space의 좌표 중 3개의 원소를 고를 수 있는 모든 조합을 추출
  • combinations 사용
• 이 경우를 모두 탐색하며, 조합에서 추출된 3개의 좌표는 벽으로 저장과 동시에 방문 처리
• 이후, BFS로 탐색
• BFS
  • 여기선, 바이러스가 얼마나 퍼지냐가 중요 포인트인 문제
  • 즉, queue에 저장되는 좌표는 바이러스가 존재하는 좌표
  • 각 바이러스의 좌표에서 벽이 아니고, 좌표 범위를 벗어나지 않았다면?
    • 방문 처리
• BFS 탐색 후 방문처리가 되지 않는 좌표들은 바이러스&벽이 아닌 안전지대
• 이 Case 중 Max값을 추출

예제 시각화

해답

from collections import deque
from itertools import combinations
n, m = map(int, input().split())
board = []
for i in range(n):
    data = list(map(int, input().split()))
    board.append(data)
b=[] # Empty Space의 모든 좌표
for i in range(n):
    for j in range(m):
        if board[i][j]==0:
            b.append([i,j]) # 빈칸인 좌표를 저장

test = list(combinations(b,3)) # 이 좌표 중 3개를 뽑을 수 있는 모든 경우의 수 저장
ax = [0,0,1,-1]
ay = [1,-1,0,0]

def bfs():
    while len(a):
        x,y = a.popleft()
        state[x][y] = 1
        for i in range(4):
            new_x = x+ax[i]
            new_y = y+ay[i]
            if new_x <= -1 or new_y <= -1 or new_x >= n or new_y >= m:
                continue
            if state[new_x][new_y]==0:
                if board[new_x][new_y]==0:
                    state[new_x][new_y]=1
                    a.append(([new_x,new_y]))
ans = []
for c in test: # 새로 벽을 세울 모든 경우의 수
    a=deque()
    state = [[0]*m for i in range(n)]
    for i in range(n):
        for j in range(m):
            if board[i][j]==2: # 바이러스 좌표를 queue에 추가
                a.append([i,j])
            elif board[i][j]==1: # 벽인 경우는 이동이 불가하므로 방문처리
                state[i][j]=1
    target1,target2,target3 = c # 새로 벽을 세운 좌표 역시 방문 처리
    state[target1[0]][target1[1]] = 1 
    state[target2[0]][target2[1]] = 1
    state[target3[0]][target3[1]] = 1
    bfs() # 탐색
    cnt=0 
    for p in range(len(state)): # 안전지대 개수 세기
        cnt+=state[p].count(0)
    ans.append(cnt) # 개수 추가 
print(max(ans)) # 모든 케이스 중 가장 안전지대가 많은 케이스 출력