[백준] 14502

1. 문제

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

2. 아이디어

BFS + combinations

BFS: 바이러스의 이동범위 확인 용도
Combinations: 벽 위치 선정

3. 코드

from collections import deque
from itertools import combinations
import copy

N, M = map(int, input().split())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 안전영역계산
def safecount(placecp):
    result = 0
    for i in range(N):
        for j in range(M):
            if placecp[i][j] == 0:
                result +=1
    return result

# 바이러스 퍼지기
def virusmove(placecp, virusinit):
    sfresult = 0
    for vi in virusinit:
        bfs(placecp, vi[0], vi[1])
    sfresult = safecount(placecp)
    return sfresult

def bfs(placecp, x, y):
    visited = [[0]*M for _ in range(N)]
    queue = deque([(x, y)])
    visited[x][y] = 1
    while queue:
        px, py = queue.popleft()
        for i in range(4):
            nx = px + dx[i]
            ny = py + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 0 and placecp[nx][ny] == 0:
                    # 방문한 적 없고, 빈칸일 때
                    visited[nx][ny] = 1
                    placecp[nx][ny] = 2 # 바이러스 퍼짐
                    queue.append((nx, ny))
    return placecp 

def solution():
    maxval = 0
    place = []
    virusinit = []# 초기 바이러스 위치
    emptyinit = []# 초기 빈칸 위치
    
    for i in range(N):
        place.append(list(map(int, input().split())))
            
    # 초기 위치 저장
    for i in range(N):
        for j in range(M):
            if place[i][j] == 0: #빈칸 위치
                emptyinit.append([i, j])
            elif place[i][j] == 2: #바이러스 위치
                virusinit.append([i, j])
    
    # 벽 위치 선정
    combi = combinations(emptyinit, 3)
    for ci in combi:
        placecp = copy.deepcopy(place) # 새로운 copy list 생성
        placecp[ci[0][0]][ci[0][1]] = 1
        placecp[ci[1][0]][ci[1][1]] = 1
        placecp[ci[2][0]][ci[2][1]] = 1
        #print(placecp)
        result = virusmove(placecp, virusinit)
        maxval = max(maxval, result)
    return maxval

print(solution())

4. 결과

5. 느낀점

최대한 코드 작성 전 전체 풀이를 구성하려고 노력했다.