[파이썬] 백준 14502 : 연구소 (골드4)

[파이썬] 백준 14502 : 연구소 (골드4)

 

14502번: 연구소

---

문제

---

풀이

0. 방향성 생각

최대 8x8의 적은 케이스. 완탐 + BFS로 풀었다.

조합 사용해서 벽 3개 모든 조합수 뽑아주고, 바이러스 위치에 대해서 BFS 돌리면 끝

1. 입력

from itertools import combinations as C
from collections import deque
h,w = map(int,input().split())
arr = [list(map(int,input().split())) for i in range(h)]

# 바이러스 위치, 벽 넣을 위치 찾기
zero = set()
virus = []
for i in range(h):
    for j in range(w):
        if arr[i][j] == 0:
            zero.add((j,i))
        elif arr[i][j] == 2:
            virus.append((j,i))

zero에 빈 공간 위치

virus에 바이러스 위치 넣기

2. BFS 함수 정의

answer = []
walls = list(C(zero,3)) # 3개 골라서
step = [[1,-1,0,0],[0,0,1,-1]]

def bfs(array):
    visit = [[False]*w for i in range(h)]
    q = deque()
    q.extend(virus)
    while q:
        x,y = q.popleft()
        visit[y][x] = True
        
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            if 0<=nx<w and 0<=ny<h :
                if array[ny][nx] == 0 and not visit[ny][nx]:
                    visit[ny][nx] = True
                    q.append((nx,ny))
    count = 0
    for i in range(h):
        for j in range(w):
            if not visit[i][j] and not array[i][j]: count += 1
    return count

반복작업 해야해서 함수 지역변수에서 돌리는게 빠름, 반복 작업도 해야하고

BFS 함수에 벽을 추가한 지도 array를 넣어서 안전지대의 수 count를 반환한다.

큐에 virus 위치 넣으주고 BSF 돌리기.

3. 출력

for wall in walls:
    temp = [row[:] for row in arr]
    for j,i in wall:
        temp[i][j] = 1
    answer.append(bfs(temp))
print(max(answer))

계속 arr의 copy본을 사용해야함. deep copy 사용해도 상관 없는데 [:]형태로 써주면 새로운 객체 생성 가능.

answer에 리턴값을 추가해서 최소값 출력하기

---

전체코드

from itertools import combinations as C
from collections import deque
h,w = map(int,input().split())
arr = [list(map(int,input().split())) for i in range(h)]

# 바이러스 위치, 벽 넣을 위치 찾기
zero = set()
virus = []
for i in range(h):
    for j in range(w):
        if arr[i][j] == 0:
            zero.add((j,i))
        elif arr[i][j] == 2:
            virus.append((j,i))
            
answer = []
walls = list(C(zero,3)) # 3개 골라서
step = [[1,-1,0,0],[0,0,1,-1]]

def bfs(array):
    visit = [[False]*w for i in range(h)]
    q = deque()
    q.extend(virus)
    while q:
        x,y = q.popleft()
        visit[y][x] = True
        
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            if 0<=nx<w and 0<=ny<h :
                if array[ny][nx] == 0 and not visit[ny][nx]:
                    visit[ny][nx] = True
                    q.append((nx,ny))
    count = 0
    for i in range(h):
        for j in range(w):
            if not visit[i][j] and not array[i][j]: count += 1
    return count

for wall in walls:
    temp = [row[:] for row in arr]
    for j,i in wall:
        temp[i][j] = 1
    answer.append(bfs(temp))
print(max(answer))

 

코멘트

원트!