[백준]14502번 연구소(Python)

0. 문제 링크

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

14502번: 연구소

 

1. 문제 소개

1) 구하고자 하는 것 : 안전 영역의 최대 크기 구하기

2) 주어진 것

- N X M 직사각형

- 빈 칸이면 0, 벽이면 1, 바이러스면 2로 주어짐

- 바이러스는 모든 빈 칸으로 퍼져나감(상하좌우)

- 3개의 벽을 세워서 바이러스 막기

3) 구현

- 그래프를 탐색하면서 빈 칸(0)이면 벽을 세움

- 벽을 3개 세운 후 바이러스 퍼뜨리기

- 바이러스 위치를 deque에 넣기

- deque를 하나씩 꺼내면서 네 방향에 퍼뜨리기

- 바이러스가 퍼지면 새로운 위치를 deque에 넣기

- 빈 칸(0)의 개수를 센 다음 기존 값과 비교해서 최대값 찾기

 

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

# output
27

 

3. 코드

from collections import deque
import copy

# input
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

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

def bfs():
    queue = deque()                             # 바이러스 위치를 저장할 deque 생성
    tmp = copy.deepcopy(graph)                  # 깊은 복사

    # 바이러스 위치 찾기
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 2:                  # 바이러스가 있으면
                queue.append((i, j))            # 큐에 추가

    # 바이러스가 모두 퍼질 때까지 반복
    while queue:
        x, y = queue.popleft()                  # 큐에서 하나씩 꺼내기

        for i in range(4):                      # 네 방향 확인
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < n) and (0 <= ny < m): # 범위 안에 있으면
                if tmp[nx][ny] == 0:            # 빈 칸이면
                    tmp[nx][ny] = 2             # 바이러스가 퍼짐
                    queue.append((nx, ny))      # 해당 위치 큐에 추가

    global result
    count = 0
    for i in range(n):
        count += tmp[i].count(0)

    result = max(result, count)

def make_wall(count):
    if count == 3:                              # 벽을 3개 세웠으면
        bfs()                                   # 탐색
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:                # 아무것도 없으면
                graph[i][j] = 1                 # 벽 1개 세우기
                make_wall(count + 1)            # 벽 1개 더 세우기
                graph[i][j] = 0                 # 원상복귀

make_wall(0)
print(result)

 

실행 결과

 

4. 회고

- 벽을 세우는 부분에서 3번을 세우기 때문에 count 변수를 이용해서 재귀 함수로 구현

- 3개의 벽을 세웠으면 bfs()를 통해 바이러스의 개수를 구하고 max 값을 구함

- 바이러스의 위치를 deque(데크)를 이용하여 넣어놓고 popleft 방식으로 꺼내옴

  deque는 양방향 큐로 앞, 뒤 양방향에서 element를 추가/제거할 수 있으며, O(1) 시간 복잡도가 걸림

# deque
from collections import deque

# initialize
deq = deque()

# add element to the start
deq.appendleft(10)

# add element to the end
deq.append(0)

# pop element from the start
deq.popleft()

# pop element from the end
deq.pop()

- result는 global로 선언하여 함수 밖에서도 사용할 수 있게 정의함

- 안전 구역은 리스트에서 0인 개수를 count

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/14502_laboratory.py

GitHub - iihye/Algorithm