[백준 파이썬] 14502 연구소

 

14502번: 연구소

 

문제

연구소의 정보가 주어진 후 임의의 벽 3개를 지어 가장 적은 곳에 바이러스가 퍼지게 하는 문제이다.

 

---

 

풀이

임의의 벽3개를 세우는 방법과 바이러스가 퍼지는 방법 2개를 고려해야한다.

먼저 임의의 벽 3개를 세우는 방법은 백트랙킹을 사용하였다. 

def makeWall(count):
    if count == 3:
        bfs()
        return
    for i in range(N):
        for k in range(M):
            if matrix[i][k] == 0:
                matrix[i][k] = 1
                makeWall(count + 1)
                matrix[i][k] = 0

모든 연구소를 순환하여 백트랙킹을 사용해 벽3개를 세우는 경우를 모두 구했다.

 

바이러스가 퍼지는 경우는 BFS를 사용하였다.

연구소를 순환하여 2번(바이러스)의 좌표를 큐에 넣어주고, 해당 바이러스가 벽을 만날때까지 BFS를 이용해 탐색을 하며 바이러스를 퍼트렸다.

def bfs():
    global result
    queue = deque()
    tmpMatrix = copy.deepcopy(matrix)
    for i in range(N):
        for j in range(M):
            if tmpMatrix[i][j] == 2:
                queue.append((i, j))
    
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            dr = r + dx[i]
            dc = c + dy[i]
            if 0 <= dr < N and 0 <= dc < M:
                if tmpMatrix[dr][dc] == 0:
                    tmpMatrix[dr][dc] = 2
                    queue.append((dr, dc))
    cnt = 0
    for i in range(N):
        for j in range(M):
            if tmpMatrix[i][j] == 0:
                cnt += 1
    result = max(result, cnt)

 

코드

from collections import deque
import copy
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

matrix = [list(map(int, input().split())) for _ in range(N)]

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

result = 0
tmpCnt = 0

def makeWall(count):
    if count == 3:
        bfs()
        return
    for i in range(N):
        for k in range(M):
            if matrix[i][k] == 0:
                matrix[i][k] = 1
                makeWall(count + 1)
                matrix[i][k] = 0
                
    

def bfs():
    global result
    queue = deque()
    tmpMatrix = copy.deepcopy(matrix)
    for i in range(N):
        for j in range(M):
            if tmpMatrix[i][j] == 2:
                queue.append((i, j))
    
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            dr = r + dx[i]
            dc = c + dy[i]
            if 0 <= dr < N and 0 <= dc < M:
                if tmpMatrix[dr][dc] == 0:
                    tmpMatrix[dr][dc] = 2
                    queue.append((dr, dc))
    cnt = 0
    for i in range(N):
        for j in range(M):
            if tmpMatrix[i][j] == 0:
                cnt += 1
    result = max(result, cnt)
        
makeWall(0)
print(result)