[백준] 14502 연구소

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

비어있는 공간들 중 3군데를 벽을 세워야 하므로 모든 조합을 구하기 위해 벽을 세울 좌표 조합을 구했습니다.

바이러스가 여러곳에서 동시에 퍼져야 하므로 BFS 탐색을 하였습니다.

바이러스가 퍼지면 안전 구역의 개수를 하나씩 줄여가며 답을 찾아나갔습니다.

2) 알고리즘

• 조합
• BFS

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
from itertools import combinations
sys.stdin = open('input.txt')

def solution():
    global ans

    q = deque(start_coordinates)                # 바이러스가 있는 모든곳에서 시작 (BFS)

    while q:
        node = q.popleft()
        for k in range(4):
            r = node[0] + dr[k]
            c = node[1] + dc[k]

            # 바이러스가 감염이 가능한 구역이면, 방문처리, 안전구역 1 감소, 다음 탐색 위한 추가
            if 0 <= r < N and 0 <= c < M and not board[r][c] and (r, c) not in e and not visited[r][c]:
                visited[r][c] = 1
                ans -= 1
                q.append((r, c))


dr = [-1, 0, 1, 0]              # 상 우 하 좌
dc = [0, 1, 0, -1]

N, M = map(int, sys.stdin.readline().split())                               # 세로, 가로 크기
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]    # 연구소 현황
empty_coordinates = []                          # 비어 있는 공간의 좌표들
start_coordinates = []                          # 바이러스 있는 공간의 좌표들
wall = set()                                    # 3곳의 벽을 세울 공간을 담을 변수
answer = 0                                      # 정답 변수

for i in range(N):                              # 연구실을 한번 전체 탐색하여
    for j in range(M):                          # 바이러스 있는 구역과 비어있는 구역의 좌표값을 따로 저장
        if board[i][j] == 2:
            start_coordinates.append((i, j))
        elif board[i][j] == 0:
            empty_coordinates.append((i, j))

safe = len(empty_coordinates) - 3               # 초기 안전한 구역의 개수 = 비어있는 공간의 개수 - 벽을 세울 3개의 공간
for e in combinations(empty_coordinates, 3):    # 벽을 세울 공간을 조합으로 구함
    visited = [[0] * M for _ in range(N)]       # 바이러스가 이미 침투했는지 확인을 위한 리스트
    ans = safe

    solution()
    
    answer = max(answer, ans)                   # 이전의 경우와 비교하여 현재 구한 안전구역의 개수 중 더 많은걸 저장

print(answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

14502번: 연구소

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다