[이코테] BFS - 연구소 with 파이썬

1. 문제

• 백준 14502와 같은 문제
  • 링크
• 바이러스 막기 위해 벽을 세우려 한다.
• N , M 직사각형
• 벽의 개수는 3개이며 꼭 3개를 세워야 한다.
• 0은 빈칸, 1은 벽, 2는 바이러스
• 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역
• 안전 영역의 크기의 최대값을 구하는 프로그램
• 입력
  • 세로 N, 가로 M ( 3 <= N, M <= 8)
  • 0은 빈칸, 1은 벽, 2는 바이러스 ( 2 <= 2의 개수 <=10 , 빈칸 >= 3)
• 출력
  • 안전영역의 최대 크기

입출력 예시

2. 아이디어

• 벽을 설치하는 모든 조합을 탐색하면서 BFS를 실행하고, 최소값을 갱신한다.
  • 벽이 아닌 곳 중 3개인 조합을 만들고, 벽을 설치한다.
    • 0인 점을 찾아서, 조합으로 3개를 뽑는다.
    • 그 점을 1로 바꾼다.
  • 바이러스 퍼짐은 BFS를 이용한다. 2가 있는 곳을 모두 모아서, BFS를 바이러스 위치에서 실행한다.
  • 0이 가장 많은 것을 갱신한다.

3. 예제코드

## 입력 
N, M = map(int, input().split())

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

## 벽설치할 위치, 바이러스 위치 모으기
walls = []
virus = []
for i in range(N):
    for j in range(M):
        if maps[i][j] == 0:
            walls.append((i,j))
        elif maps[i][j] == 2:
            virus.append((i,j))
            
## BFS 만들기
from collections import deque
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def BFS(x,y, graph):
    q = deque()
    q.append([x,y])
    
    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 and graph[nx][ny] == 0:   # 미방문, # 범위 항상 조심
                graph[nx][ny] = 2
                q.append((nx, ny))
## 메인
# 벽의 조합 완전탐색,  BFS 실행한 다음 , 안전영역 세기
from itertools import combinations
import copy
answer = 0
for combis in list(combinations(walls, 3)):  # 벽 조합
    new_maps = copy.deepcopy(maps)   # 새로운 지도 생성
    for a,b in combis:
        new_maps[a][b] = 1  # 벽설치
        
    for vx, vy in virus :    # 바이러스 퍼짐 
        BFS(vx,vy, new_maps)
    
    cnt = 0
    for i in range(N):
        for j in range(M):
            if new_maps[i][j] == 0:
                cnt += 1
    answer = max(answer, cnt)
    
print(answer)

참조

• 이것이 취업을 위한 코딩테스트다. with 파이썬