Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 재귀
- 파이썬
- 딕셔너리
- level3
- 백준
- 다이나믹 프로그래밍
- level0
- 운영체제
- MYSQL
- python
- 가상메모리 관리
- dict
- 그리디
- 수학
- 가상메모리
- BOJ
- dfs
- 스택
- 다익스트라
- 프로그래머스
- level1
- 브루트포스
- BFS
- programmers
- N과M
- 구현
- DP
- 힙
- 코딩테스트
- level2
Archives
- Today
- Total
동캄의 코딩도장
백준 14502 [연구소] 파이썬 본문
https://www.acmicpc.net/problem/14502
# 백준 14502
from collections import deque
import sys
input = sys.stdin.readline
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
R, C = map(int, input().split())
field = []
virus = []
for i in range(R):
s = list(map(int, input().split()))
for j in range(C):
if s[j] == 2:
virus.append([i, j])
field.append(s)
def bfs(virus):
q = deque([])
for v in virus:
q.append(v)
while q:
r, c = q.popleft()
for i in range(4):
n = r+dr[i]
m = c+dc[i]
if 0 <= n < R and 0 <= m < C and field_[n][m] == 0:
field_[n][m] = 2
q.append([n, m])
answer = 0
point = R*C
for b1 in range(point):
br1 = b1//C
bc1 = b1 % C
if field[br1][bc1] == 0:
for b2 in range(b1):
br2 = b2//C
bc2 = b2 % C
if field[br2][bc2] == 0:
for b3 in range(b2):
br3 = b3//C
bc3 = b3 % C
if field[br3][bc3] == 0:
field_ = []
for i in range(R):
field_.append(list(map(int, field[i])))
field_[br1][bc1] = 1
field_[br2][bc2] = 1
field_[br3][bc3] = 1
bfs(virus)
temp = 0
for k in range(R):
temp += field_[k].count(0)
answer = max(answer, temp)
print(answer)
bfs와 브루트포스를 합친 문제이다.
'코테 > BOJ' 카테고리의 다른 글
백준 2096 [내려가기] 파이썬 (0) | 2022.04.16 |
---|---|
백준 15686 [치킨배달] 파이썬 (0) | 2022.04.16 |
백준 7569 [토마토] 파이썬 (0) | 2022.04.15 |
백준 16928 [뱀과 사다리 게임] 파이썬 DFS BFS (0) | 2022.04.14 |
백준 14500 [테트로미노] 파이썬 (0) | 2022.04.14 |