14502

날짜 : 2023. 03. 02

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque
import copy

n, m = map(int, sys.stdin.readline().split())  # 가로, 세로
lab = list()
for _ in range(n): lab.append(list(map(int, sys.stdin.readline().split())))  # 연구소 입력
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
res = 0


def infect():  # 감염된 경우
    temp = copy.deepcopy(lab)  # 테스트용
    q = deque()
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2:  # 감염지점 추가
                q.append([i, j])
                
    while q:
        r, c = q.popleft()
        for i in range(4):
            x = r + dx[i]
            y = c + dy[i]
            if x in range(n) and y in range(m):
                if temp[x][y] == 0:
                    temp[x][y] = 2  # 감염처리
                    q.append([x, y])  # 큐에 추가

    safe_zone = 0  # 안전지대
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                safe_zone += 1
    return safe_zone


def wall(count):
    if count == 3:
        global res
        res = max(res, infect())
        return res
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 0:
                lab[i][j] = 1  # 벽 생성
                wall(count+1)  # 함수 실행(벽 생성 첨가)
                lab[i][j] = 0  # 원상복구


wall(0)
print(res)

 

풀이

- 벽을 3개를 세울 수 있다는 것이 이 문제의 포인트였다.

- 백트래킹 방식을 활용해서 0부터 시작, 3이 된 경우에는 감염 시뮬레이션(BFS)을 돌린다.

- 그리고 결과값이 도출될 때마다 최대값으로 갱신한 후 출력한다.

 

 

알게된 점

- 깊은복사하는 과정에서 변수를 정확하게 설정하지 못해 꽤 시간을 허비했다.

- 골드4라서 어려울줄 알았는데 의외로 풀이방식이 간단해서 조금 의아했다.

- 추가로 연구소 크기와 세울 수 있는 벽의 개수가 3개라는 것에서 브루트포스를 활용할 수 있다는 것을 떠올리는 것이 이 문제의 키포인트같다.

 

참고 사이트

-