14502. 연구소 [BAEKJOON / Python]

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

 

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.

새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

 

0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다.

input = 7 7
            2 0 0 0 1 1 0
            0 0 1 0 1 2 0
            0 1 1 0 1 0 0
            0 1 0 0 0 0 0
            0 0 0 0 0 1 1
            0 1 0 0 0 0 0
            0 1 0 0 0 0 0

 

전체 코드

from collections import deque
import sys
import itertools
input = sys.stdin.readline

# 세로 가로
n, m = map(int, input().split())
maps = [list(map(int, input().rstrip().split())) for _ in range(n)]

wall = 0
noninft = []
virus = []

for i in range(n):
    for j in range(m):
        
        # 0인 좌표 할당 (안전영역)
        if maps[i][j] == 0:
            noninft.append((i, j))
        
        # 2인 좌표 할당 (바이러스)
        elif maps[i][j] == 2:
            virus.append((i, j))
        
        else:
            wall += 1

noninft3 = []
# 경우의 수, 3개로 조합
for j in itertools.combinations(noninft, 3):
    noninft3.append(j)

dx = [0, 0, -1, 1]
dy = [1, -1, 0 , 0]


# 바이러스 증식
def bfs():
    now = deque()
    visit = [[0] * m for _ in range(n)]
    
    for i in virus:
        now.append(i)
        visit[i[0]][i[1]] = 2
    
    while now:
        x, y  = now.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if maps[nx][ny] == 0 and visit[nx][ny] == 0:
                    # 바이러스 증식
                    visit[nx][ny] = 2
                    now.append((nx, ny))
    
    cnt = 0
    # 안전영역 구하기
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0:
                cnt += 1
    
    return cnt - wall - 3

result = []
for i in noninft3:
    # 벽 세우기
    for j in i:
        maps[j[0]][j[1]] = 1
    result.append(bfs())
    
    # 세운 벽 원상복귀
    for j in i:
        maps[j[0]][j[1]] = 0

print(max(result))

 

문제 풀이 포인트

• 브루트포스 
  • itertools.combinations 사용
    • 모든 경우의 수를 반환함
    • 0이 최대한 많은 경우의 수 출력하기
• bfs 사용
  • 4방향 탐색
  • deque 사용

 

로직

1. 벽 세우기 
2. bfs로 바이러스 증식
3. 0 세기 (안전구역 세기)
4. 세운 벽 다시 0으로 돌려놓기

 

 

코드 디테일

안전영역, 바이러스 좌표 정보 할당

wall = 0
noninft = []
virus = []

for i in range(n):
    for j in range(m):
        
        # 0인 좌표 할당 (안전영역)
        if maps[i][j] == 0:
            noninft.append((i, j))
        
        # 2인 좌표 할당 (바이러스)
        elif maps[i][j] == 2:
            virus.append((i, j))
        
        else:
            wall += 1

이중 for문으로 noninft(안전영역), virus 변수에 각 좌표 값을 할당한다. (튜플로)

벽의 좌표값을 받지 않는 이유는 추후에 안전영역에서 값을 빼주기 위해 개수만 카운트한다. 

 

noninft = [(0, 1), (0, 2), (0, 3), (0, 6), (1, 0), (1, 1), (1, 3), (1, 6), (2, 0), (2, 3), (2, 5), (2, 6), (3, 0), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (5, 0), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 0), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

이때 리스트들은 이러한 형태로 값을 받게 된다.

 

경우의 수 생성

noninft3 = []
# 경우의 수, 3개로 조합
for j in itertools.combinations(noninft, 3):
    noninft3.append(j)

dx = [0, 0, -1, 1]
dy = [1, -1, 0 , 0]

combinations로 안전영역의 좌표 값을 받은 변수 noninft에 3개로 조합할 수 있는 경우의 수를 모두 noninft3에 넣어준다.

벽을 3개 세워야 하므로 3자리의 조합한 경우의 수를 생성한다.

 

바이러스 증식

# 바이러스 증식
def bfs():
    now = deque()
    visit = [[0] * m for _ in range(n)]
    
    for i in virus:
        now.append(i)
        visit[i[0]][i[1]] = 2
    
    while now:
        x, y  = now.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if maps[nx][ny] == 0 and visit[nx][ny] == 0:
                    # 바이러스 증식
                    visit[nx][ny] = 2
                    now.append((nx, ny))

4방향 탐색으로 바이러스가 증식된 좌표를 생성하도록 한다.

 

visit 리스트를 만들 때 주의할 점은 입력값이 세로는 n, 가로는 m의 값으로 주어졌다.

그러므로 [0]은 세로값 만큼 나열해야하기 때문에 m을 곱한다.

 

위에서 바이러스 좌표값을 받은 virus 변수를 for문으로 now 리스트에 넣어준다. 

i 값은 바이러스가 있는 위치이기 때문에 방문 리스트에 튜플 형식으로 된 하나의 값에 2를 할당한다.

즉, 바이러스 증식된 위치임을 maps가 아닌 visit에 2로 표시하는 것이다. (maps 좌표값을 바꾸려고 하지 않는다.)

 

안전영역 구하기

    cnt = 0
    # 안전영역 구하기
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0:
                cnt += 1
    
    return cnt - wall - 3

while문(바이러스 증식)이 끝난 후 안전영역을 구한다.

이중 for문으로 만약 visit에 바이러스가 방문하지 않았다면 (if visit[i][j] == 0:)

0의 개수를 카운트 해준다. (cnt += 1)

 

0의 개수값에 위에서 카운트한 벽의 개수를 빼주고 추후에 세울 벽의 개수(3개) 또한 빼준다.

 

벽 세우기

result = []
for i in noninft3:
    # 벽 세우기
    for j in i:
        maps[j[0]][j[1]] = 1
    result.append(bfs())
    
    # 세운 벽 원상복귀
    for j in i:
        maps[j[0]][j[1]] = 0

print(max(result))

3자리 조합으로 만든 경우의 수 값을 넣은 noninft3를 for문으로 값을 하나씩 빼주면서 maps에 벽을 세울 위치(좌표)에 1 값을 할당한다.

bfs 함수가 실행한 후 result 리스트에 해당 값을 넣어준다. 

그렇다면 noninft3에서 모든 경우의 수를 bfs로 다 실행시키며 안전영역의 값을 result에 최종적으로 넣어주게 되는 것이다. 

 

모든 경우의 수를 탐색해야 하므로 위 for문에서 세운 벽(1)을 다시 안전영역의 값(0)으로 바꿔준다. 

 

모든 경우의 수를 탐색한 후 result에 할당된 제일 큰 수를 출력하게 되면 안전영역이 제일 많은 값을 출력하게 된다.