BOJ - 연구소 14502번 (python)

❓ 문제 - 백준 연구소 14502번 - python 풀이법

출처 

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

14502번: 연구소

 

 

📝 문제해결법

1. 이 문제의 핵심은 그래프탐색(BFS)과 조합(Combination)으로 해결하는 것이다.

• 문제에서 벽을 3곳에 둘 수 있으므로 처음 graph를 입력받을 때 빈칸(0)일 때의 인덱스 i,j를 리스트에 저장
• 해당 빈칸 위치 리스트에서 3개 조합으로 벽을 둘 수 있는 곳을 선정
• graph에 해당 조합을 반영하기 위하여 copy_graph로 graph를 copy 하고 해당 조합의 위치에서 빈칸(0)을 벽(1)으로 바꿔줌
• 해당 3개의 벽을 뒀을 경우에서 바이러스가 퍼져나가는 것을 BFS로 구현
• 해당 조합의 경우에서 바이러스 다 퍼져나간 후  빈칸(0) 즉, 안전영역의 갯수를 계속 갱신하면서  안전영역의 최댓값 찾기

2. BFS 내에서 구현 방법

• BFS를 이용하여 4방향(북, 남, 동,서)로 탐색
• 모든 바이러스 위치에서 4방향 탐색하면서 만약 탐색한 범위가 벽(1)이라면 탐색 종료
• 만약 탐색한 범위가 방문하지 않고 빈칸(0)이면 바이러스가 퍼져나갈 수 있으므로 해당 값을 바이러스(2)로 바꾸고 해당 위치를 queue에 append 하기 

 

 

💻 소스코드

# 연구소 - BOJ 14502
# BFS + 조합
import sys
from collections import deque
from itertools import combinations
import copy

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

graph = []
blank = []
virus = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(v, copy_graph):
    visited = [[False]*m for _ in range(n)]
    for k in v:
        q = deque()
        q.append((k[0], k[1]))
        visited[k[0]][k[1]] = True
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    if copy_graph[nx][ny] == 1:
                        visited[nx][ny] = True
                        continue
                    elif graph[nx][ny] == 0:
                        if visited[nx][ny] == False:
                            copy_graph[nx][ny] = 2
                            visited[nx][ny] = True
                            q.append((nx, ny))
    count = 0
    for i in range(n):
        for j in range(m):
            if copy_graph[i][j] == 0:
                count += 1
    return count

for i in range(n):
    data = list(map(int, input().split()))
    for j in range(m):
        if data[j] == 0:
            blank.append([i, j])
        elif data[j] == 2:
            virus.append([i, j])
    graph.append(data)

max_count = 0
for combi in list(combinations(blank, 3)):
    copy_graph = copy.deepcopy(graph)
    for c in combi:
        x, y = c
        copy_graph[x][y] = 1
    count = bfs(virus, copy_graph)
    max_count = max(max_count, count)


print(max_count)