연구소, python

문제 설명

0이 들어 있는 칸에 총 세 개의 벽인 1을 세워서 바이러스가 퍼진 후 남은 0의 최대 갯수를 세는 문제다.

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

14502번: 연구소

문제 풀이

첫 번째 접근

이번에도 총 세 가지 순서로 문제에 접근했다.

 

1. 벽을 세 개 세운다.

  0이 있는 부분에 벽을 세우는데, 이는 재귀함수를 이용해서 풀었다. count가 3이 되기 전까지 벽을 세우는데, 중요한 점은 return을 한 다음에 세운 벽을 0으로 되돌려 줘야 한다는 거다. 그래야지 다음 빈칸으로 넘어가서 벽을 세울 수 있다.

 

2. 벽을 세 개 세웠다면 바이러스를 퍼트린다.

  바이러스가 한 개 이상 있을 수 있으므로 벽을 세운 그래프를 돌면서 바이러스가 있으면 그 위치를 큐에 넣어준다. 그리고 큐가 빌 때까지 바이러스의 위치를 하나씩 꺼내서 사방으로 나갈 수 있는지 확인한다. 나갈 수 있으면 해당 위치에 2를 넣어 바이러스가 퍼졌음을 알리고 큐에 그 위치를 넣는다. 이렇게 바이러스를 전부 퍼트렸다면, 남을 0을 세서 안전한 구역이 총 몇인지 확인한다. 그리고 안전한 구역의 수를 반환한다.

 

3. 새로 구한 안전한 구역과 현재 최댓값을 비교한다.

  안전한 구역의 최댓값을 구하는 문제이므로 새로 구한 안전한 구역과 현재의 최댓값을 비교해서 더 큰 값을 넣어준다. 여기서 정답은 global로 전역 변수임을 표기해야 한다. 나는 파이썬의 전역 변수와 지역 변수의 정확한 범위를 잘 몰라 꽤 시간을 썼다.

 

간단하게 말하자면 전역 변수로 썼을 경우에도 외부 함수에서 해당 변수를 사용하려면 global를 붙여줘야 한다. 그 이유는 파이썬은 지역 변수, 전역 변수, 빌트인 변수로 검사를 하기 때문이다. 즉, 아무리 전역 변수로 썼다고 생각을 해도 global을 붙여주지 않으면 파이썬은 내가 전역 변수라고 생각한 변수를 지역 변수로 인식하는 것. 그러나 배열의 경우 굳이 global을 붙여주지 않아도 전역 변수로 인식한다. 왜?

 

왜냐하면 리스트의 경우 스코프가 mutable이기 때문이다. 정수형 변수의 경우 immutable이라 아무리 전역 변수로 써줬어도 global이 없으면 지역 변수라고 생각하고 값을 바꿀 때 새로운 객체를 생성한다. 그러나 리스트의 경우 mutable이기 때문에 굳이 global을 사용하지 않더라도 전역 변수로 사용이 가능한 것이다.

 

코드

import sys
from collections import deque
import copy

dR = [-1, 0, 1, 0]
dC = [0, 1, 0, -1]

n, m = map(int, sys.stdin.readline().rstrip().split(" "))
graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split(" "))))


def virus():
    q = deque()
    tmpGraph = copy.deepcopy(graph)
    safe = 0
    
    # 초기 바이러스 위치를 잡아 준다.
    for i in range(n):
        for j in range(m):
            if tmpGraph[i][j] == 2:
                q.append((i, j))
    # 바이러스를 퍼트린다.
    while q:
        cR, cC = q.popleft()

        for i in range(4):
            nR = cR + dR[i]
            nC = cC + dC[i]

            if (0 <= nR < n) and (0 <= nC < m):
                if tmpGraph[nR][nC] == 0:
                    tmpGraph[nR][nC] = 2
                    q.append((nR, nC))
    # 바이러스가 퍼지지 않은 안전 구역의 수를 센다.
    for i in range(n):
        for j in range(m):
            if tmpGraph[i][j] == 0:
                safe += 1

    return safe


def wall(count):
    # 벽을 총 3개 세우면 바이러스를 퍼트려서 안전 구역의 수를 센다.
    if count == 3:
        # global로 전역 변수인 answer의 값과 바이러스로 센 값을 비교해서 더 큰 값을 넣어준다.
        global answer
        answer = max(answer, virus())
        return
    
    # 벽을 세운다.
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                wall(count+1)
                # 세운 벽을 0으로 해줘서 다음 벽을 세울 수 있게 해야 한다.
                graph[i][j] = 0


answer = 0
wall(0)
print(answer)