[Python] 백준 14502 연구소 | BFS

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

14502번: 연구소

 

 

문제 해결 포인트

- 0인 값의 모든 위치를 리스트 (blank)에 넣어서 cominations 모듈을 사용해 3개 위치 랜덤 추출(nCr)

- 베이스가 되는 기존 정보에 해당 하는 3개의 위치를 1로 설정하고 check 함수 호출

 

- check 함수

   ~ BFS를 위한 큐를 선언하여 값이 2인 위치를 넣는다.

   ~ 큐에 값을 하나씩 꺼내 해당 하는 위치에서 위, 아래, 오른쪽, 왼쪽 위치가 0이면서 크기를 벗어나지 않는다면

       2로 변경하고 해당 위치를 큐에 삽입하여 바이러스가 퍼질 수 있는 곳을 전부 2로 변경한다.

   ~ 최종 결과에서 0의 개수를 카운드하여 반환한다.

 

- 모든 경우에 대해서 0의 개수가 가장 큰 값이 최종 답이 된다.

 

작성 코드

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

dr = [1, -1, 0, 0]  # down, up, right, left
dc = [0, 0, 1, -1]


def check(board):
    que = deque()
    for i in range(n):
        for j in range(m):
            if board[i][j] == 2:
                que.append((i, j))
    while que:
        r, c = que.popleft()
        for d in range(4):
            y = r + dr[d]
            x = c + dc[d]
            if -1 < x < m and -1 < y < n and board[y][x] == 0:
                board[y][x] = 2
                que.append((y, x))

    result = 0
    for i in range(len(board)):
        result += board[i].count(0)
    return result

n, m = map(int, input().split())
board = []
blank = []
result = 0

for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(m):
        if temp[j] == 0:
            blank.append((i, j))
    board.append(temp)

nCr = combinations(blank, 3)

for x in nCr:
    tempBoard = copy.deepcopy(board)
    for i, j in x:  # 선택된 벽 3개 위치
        tempBoard[i][j] = 1
    result = max(result, check(tempBoard))

print(result)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

궁금한 사항이 있으면 댓글 달아주세요~!