[BOJ] 연구소(14502) - PYTHON

가로, 세로의 크기가 각각 N, M인 직사각형에서 (3 <=N, M <=8) 각 칸이 빈칸(0), 벽(1), 바이러스(2)로 이루어진 좌표가 입력으로 들어온다. 바이러스는 상, 하, 좌, 우로 번지게 된다. 이때 빈칸 중 3칸을 벽으로 만들 수 있다고 할 때, 바이러스가 번지지 않은 빈칸(0)의 최대값을 구하는 문제이다. 

14502번: 연구소

---

풀이 방법

주어진 좌표에서 좌표값이 0인 좌표 3개의 값을 1로 바꾸고, BFS/DFS를 통해 값이 2(바이러스)인 좌표에서 시작해  값이 0(빈칸)인 좌표에 방문해 값을 2로 바꿔나가며 계속 퍼져나가면 된다. 순서를 정리하면 다음과 같다.

1. 좌표 전체에서 바이러스가 위치한 좌표를 찾는다.
2. 빈칸 좌표 중 3개를 선택하는 경우의 수(조합)를 구한다.
3. 각 경우마다 BFS/DFS를 통해 값이 바이러스와 인접한 값이 0인 좌표의 값을 2로 바꿔나간다.
4. 순회가 끝나면 전체 좌표 중 값이 0인 좌표의 개수를 찾는다.(바이러스가 퍼져나가지 못한 좌표)
5. 모든 경우에서의 0의 좌표 최댓값을 출력한다.

이때 좌표에서 값이 0인 점들 중 3개를 고르는 경우의 수는 combination(MN,3)이며 각 경우마다 BFS/DFS를 수행하는데 MN의 연산이 발생한다. 따라서 이 알고리즘의 시간 복잡도는 위에서 적은 값과 같다.  

---

코드

from collections import deque
from itertools import combinations
import copy
 
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
virus = []
hole = []
answer = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
for i in range(N):
    for j in range(M):
        if matrix[i][j] == 2:
            virus.append((i, j))
        elif matrix[i][j] == 0:
            hole.append((i, j))
 
hole_comb = combinations(hole, 3)
for indices in hole_comb:
    # dupMatrix = matrix[:] # 깊은 복사 아님
    dupMatrix = copy.deepcopy(matrix)
    temp = 0
    q = deque()
    for x, y in indices:
        dupMatrix[x][y] = 1
    for x, y in virus:
        q.append((x, y))
    ###BFS###
    while len(q) > 0:
        x, y = q.popleft()
        for tx, ty in zip(dx, dy):
            nx = x + tx
            ny = y + ty
            if 0 <= nx < N and 0 <= ny < M and dupMatrix[nx][ny] == 0:
                dupMatrix[nx][ny] = 2
                q.append((nx, ny))
    for i in range(N):
        for j in range(M):
            if dupMatrix[i][j] == 0:
                temp += 1
    answer = max(answer, temp)
print(answer)
 

 

주석 추가

from collections import deque  # BFS를 위한 Queue
from itertools import combinations  # 조합을 구하기 위한 combinations
import copy  # 배열의 깊은 복사를 위한 copy
 
N, M = map(int, input().split())  # 직사각형의 가로, 세로
matrix = [list(map(int, input().split())) for _ in range(N)]  # 2차원 좌표
virus = []  # 바이러스의 좌표를 담을 배열
hole = []  # 빈칸을 담을 배열
answer = 0
dx = [-1, 1, 0, 0]  # 바이러스의 x위치 변화 (상,하,좌,우)
dy = [0, 0, -1, 1]  # 바이러스의 y위치 변화 (상,하,좌,우)
 
for i in range(N):
    for j in range(M):  # 모든 점에 대해
        if matrix[i][j] == 2:  # 값이 바이러스면
            virus.append((i, j))  # 바이러스 배열에 추가
        elif matrix[i][j] == 0:  # 값이 빈칸이면
            hole.append((i, j))  # 빈칸에 추가
 
hole_comb = combinations(hole, 3)  # 빈칸 좌표 중 3개를 고르는 경우의 수 담기
for indices in hole_comb:  # 각 경우마다
    # dupMatrix = matrix[:] # 깊은 복사 아님
    dupMatrix = copy.deepcopy(matrix)  # 좌표 배열을 복사
    temp = 0  # 그래프 탐색후 빈칸의 갯수를 담을 변수
    q = deque()  # 큐
    for x, y in indices:  # 각 선택된 점마다
        dupMatrix[x][y] = 1  # 값을 0 -> 1로 바꾸기
    for x, y in virus:  # 각 바이러스마다
        q.append((x, y))  # 큐에 바이러스 위치 삽입(초기값)
    ###BFS###
    while len(q) > 0:
        x, y = q.popleft()
        for tx, ty in zip(dx, dy):  # 현재 점에서 (상,하,좌,우)의 좌표 변화량
            nx = x + tx  # 다음 x좌표
            ny = y + ty  # 다음 y좌표
            if 0 <= nx < N and 0 <= ny < M and dupMatrix[nx][ny] == 0:  # 다음 좌표값이 직사각형 안에 있고, 값이 0이라면(빈칸이라면)
                dupMatrix[nx][ny] = 2  # 값을 바이러스(2)로 바꾸고
                q.append((nx, ny))  # 큐에 좌표 삽입
    for i in range(N):
        for j in range(M):
            if dupMatrix[i][j] == 0:  # 모든 점에대해 값이 0인 점의 갯수 세기
                temp += 1
    answer = max(answer, temp)  # 정답으로 각 경우마다 최대값 갱신
print(answer)

 

각 경우마다 좌표를 복사할 때 matrix[:]를 사용하면 얕은 복사가 발생해 배열이 제대로 복사되지 않는다. copy모듈의 deepcopy를 사용하면 깊은 복사를 통해 값을 복사할 수 있다.

combinations모듈은 배열에서 원하는 길이로 조합을 생성해준다.

ex)
arr = [1, 2, 3, 4]
combinations(arr,3) = ((1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4))
※ combinations의 결과는 list가 아니라 tuple임

---

채점 결과