[백준(BOJ)] 14502번 : 연구소 - PYTHON[파이썬]

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

14502번: 연구소

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 브루트포스 알고리즘
• 너비 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

재귀를 통해 벽을 세우고 3개를 다 세웠으면 그때 bfs를 돌린다.

 

bfs는 바이러스를 기준으로 퍼져나가게 코드를 짜주었고, count 함수를 사용하여 0의 개수를 출력해준다.

0은 안전지역이다. 안전지역이 가장 많은 값을 ans에 저장해 주어 브루트 포스, 모든 경우에서 가장 많은 안전 영역을 가진 경우를 찾아낸다.

---

 

⊙ 문제 풀이

 

import sys
import copy
from collections import deque

input = sys.stdin.readline

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

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
ans = 0
q = deque()

def bfs():
    global ans
    w = copy.deepcopy(arr)
    for i in range(N):
        for j in range(M):
            if w[i][j]==2:
                q.append([i,j])

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if w[nx][ny]==0:
                    w[nx][ny] = 2
                    q.append([nx,ny])
    cnt = 0
    for i in w:
        cnt+=i.count(0)
    ans = max(ans,cnt)

def wall(x):
    if x==3:
        bfs()
        return
    for i in range(N):
        for j in range(M):
            if arr[i][j]==0:
                arr[i][j]=1
                wall(x+1)
                arr[i][j]=0

wall(0)
print(ans)

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!