백준
백준 boj 파이썬 14502 연구소
코테봇
2022. 6. 29. 19:44
벽의 위치를 3개 세우는 방식이 사람마다 다른 것 같다.
나는 from itertools import combinations을 이용하였다.
이차원 배열을 돌면서 벽의 위치를 수집하고
벽의 개수가 n개면 0~n-1까지의 리스트를 만들고
combinations(orders,3)로 3개의 조합을 뽑는 리스트를 생성 후
각각 벽을 세워줬다.
무언가 어려워보이지 않지만 실제로 풀다보면 굉장히 실수도 많이 발생하고
구현하기에 상당히 빡빡한 문제라는 생각이 들었다.
굉장히 탄탄한 벽 같다는 느낌을 받았다.
벽 위치 수집 -> combinations을 이용하여 각각 경우의 수마다 벽을 세우고->바이러스를 퍼트리고-> 모든 경우의 수 반복 후->안전영역 계산
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
import sys
from collections import deque
from itertools import combinations
#sys.setrecursionlimit(1000000)
## 콤비네이션 함수로 3개 뿌리고 그 3개마다 bfs 탐색해서 안전영역 최대의 크기를 구한다.
## 바이러스 퍼트리기
def virus():
#print(q)
while q:
x,y= q.popleft()
for k in range(4):
nx=x+dx[k]
ny=y+dy[k]
if 0<=nx<n and 0<=ny<m:
if temp[nx][ny]==0:
temp[nx][ny]=2
q.append((nx,ny))
#for i in range(n):
# for j in range(m):
# print(temp[i][j],end=' ')
# print()
#print()
if __name__=='__main__':
#sys.stdin=open("input.txt", "rt")
n,m=map(int,input().split()) ##n=행,m=열
board=[list(map(int,input().split())) for _ in range(n)]
wall=[]
##벽의 후보 위치 수집
for i in range(n):
for j in range(m):
if board[i][j]==0:
wall.append((i,j)) ##[(0,1),(1,2),~~]
w=len(wall) ##벽을 세울 수 있는 위치의 크기
#print(w)
order=[x for x in range(w)]
wall_com=list(combinations(order,3)) ##벽의 후보 3개 뽑기 [(0,1,2),(2,3,4)~~~~]
# print(wall_com)
q=deque()
dx=[0,0,-1,1]
dy=[1,-1,0,0]
temp=[[0]*m for _ in range(n)]
ans=-3 ##안전 영역 최대 크기
## 벽 세우기 (각각 케이스마다)
# print((wall_com))
for x in wall_com:
#print(x)
ch=[[-1]*m for _ in range(n)]
##초기화 시키기 그래프
for i in range(n):
for j in range(m):
temp[i][j]=board[i][j]
##벽 세우기
for y in x:
a=(wall[y][0])
b=(wall[y][1])
temp[a][b]=1
# print(a,b)
#print()
## 바이러스 있는 위치 수집
for i in range(n):
for j in range(m):
if temp[i][j]==2:
q.append((i,j))
virus() ##바이러스 퍼트리기
##안전 영역 계산
cnt=0
for i in range(n):
for j in range(m):
if temp[i][j]==0:
cnt+=1
ans=max(ans,cnt)
#if ans==14:
# for i in range(n):
# for j in range(m):
# print(temp[i][j],end=' ')
# print()
# exit()
# print(ans)
print(ans)
|
cs |