๋ฌธ์
์ธ์ฒด์ ์น๋ช ์ ์ธ ๋ฐ์ด๋ฌ์ค๋ฅผ ์ฐ๊ตฌํ๋ ์ฐ๊ตฌ์์์ ๋ฐ์ด๋ฌ์ค๊ฐ ์ ์ถ๋์๋ค. ๋คํํ ๋ฐ์ด๋ฌ์ค๋ ์์ง ํผ์ง์ง ์์๊ณ , ๋ฐ์ด๋ฌ์ค์ ํ์ฐ์ ๋ง๊ธฐ ์ํด์ ์ฐ๊ตฌ์์ ๋ฒฝ์ ์ธ์ฐ๋ ค๊ณ ํ๋ค.
์ฐ๊ตฌ์๋ ํฌ๊ธฐ๊ฐ N×M์ธ ์ง์ฌ๊ฐํ์ผ๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, ์ง์ฌ๊ฐํ์ 1×1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ์ฐ๊ตฌ์๋ ๋น ์นธ, ๋ฒฝ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ๋ฒฝ์ ์นธ ํ๋๋ฅผ ๊ฐ๋ ์ฐจ์งํ๋ค.
์ผ๋ถ ์นธ์ ๋ฐ์ด๋ฌ์ค๊ฐ ์กด์ฌํ๋ฉฐ, ์ด ๋ฐ์ด๋ฌ์ค๋ ์ํ์ข์ฐ๋ก ์ธ์ ํ ๋น ์นธ์ผ๋ก ๋ชจ๋ ํผ์ ธ๋๊ฐ ์ ์๋ค. ์๋ก ์ธ์ธ ์ ์๋ ๋ฒฝ์ ๊ฐ์๋ 3๊ฐ์ด๋ฉฐ, ๊ผญ 3๊ฐ๋ฅผ ์ธ์์ผ ํ๋ค.
์๋ฅผ ๋ค์ด, ์๋์ ๊ฐ์ด ์ฐ๊ตฌ์๊ฐ ์๊ธด ๊ฒฝ์ฐ๋ฅผ ์ดํด๋ณด์.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
์ด๋, 0์ ๋น ์นธ, 1์ ๋ฒฝ, 2๋ ๋ฐ์ด๋ฌ์ค๊ฐ ์๋ ๊ณณ์ด๋ค. ์๋ฌด๋ฐ ๋ฒฝ์ ์ธ์ฐ์ง ์๋๋ค๋ฉด, ๋ฐ์ด๋ฌ์ค๋ ๋ชจ๋ ๋น ์นธ์ผ๋ก ํผ์ ธ๋๊ฐ ์ ์๋ค.
2ํ 1์ด, 1ํ 2์ด, 4ํ 6์ด์ ๋ฒฝ์ ์ธ์ด๋ค๋ฉด ์ง๋์ ๋ชจ์์ ์๋์ ๊ฐ์์ง๊ฒ ๋๋ค.
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
๋ฐ์ด๋ฌ์ค๊ฐ ํผ์ง ๋ค์ ๋ชจ์ต์ ์๋์ ๊ฐ์์ง๋ค.
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
๋ฒฝ์ 3๊ฐ ์ธ์ด ๋ค, ๋ฐ์ด๋ฌ์ค๊ฐ ํผ์ง ์ ์๋ ๊ณณ์ ์์ ์์ญ์ด๋ผ๊ณ ํ๋ค. ์์ ์ง๋์์ ์์ ์์ญ์ ํฌ๊ธฐ๋ 27์ด๋ค.
์ฐ๊ตฌ์์ ์ง๋๊ฐ ์ฃผ์ด์ก์ ๋ ์ป์ ์ ์๋ ์์ ์์ญ ํฌ๊ธฐ์ ์ต๋๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ง๋์ ์ธ๋ก ํฌ๊ธฐ N๊ณผ ๊ฐ๋ก ํฌ๊ธฐ M์ด ์ฃผ์ด์ง๋ค. (3 ≤ N, M ≤ 8)
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ์ง๋์ ๋ชจ์์ด ์ฃผ์ด์ง๋ค. 0์ ๋น ์นธ, 1์ ๋ฒฝ, 2๋ ๋ฐ์ด๋ฌ์ค๊ฐ ์๋ ์์น์ด๋ค. 2์ ๊ฐ์๋ 2๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 10๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
๋น ์นธ์ ๊ฐ์๋ 3๊ฐ ์ด์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ป์ ์ ์๋ ์์ ์์ญ์ ์ต๋ ํฌ๊ธฐ๋ฅผ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1 ๋ณต์ฌ
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
์์ ์ถ๋ ฅ 1 ๋ณต์ฌ
27
์์ ์ ๋ ฅ 2 ๋ณต์ฌ
4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2
์์ ์ถ๋ ฅ 2 ๋ณต์ฌ
9
์์ ์ ๋ ฅ 3 ๋ณต์ฌ
8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
์์ ์ถ๋ ฅ 3 ๋ณต์ฌ
3
# ํ์ด ๋ฐฉ๋ฒ
์ฒ์์๋ ๊ฐ ๋ฐ์ด๋ฌ์ค์์ ํผ์ง ์ ์๋ ์์ญ์ ์๋ฅผ ๊ตฌํ ํ์ ๊ทธ๊ฒ ํฐ ๋ฐ์ด๋ฌ์ค๋ฅผ ๋จผ์ ๋ง๊ณ ์ด๋ฐ ์์ผ๋ก ์งํํ๋ ค๊ณ ํ๋ค.
๊ทธ๋ฐ๋ฐ ๊ทธ๋ ๊ฒ ํ๋ค๋ณด๋ ์ด๋ป๊ฒ ๊ธฐ์ค์ ์ธ์์ผํ ์ง ๋ช ํํ์ง ์์๋ค..
์ฌ๊ธฐ์ ์๊ฐํ๊ฒ ๋ชจ๋ ์๋ฅผ ๋ค ๊ณ ๋ คํด์ผ ํ๋..? ์๊ฐ์ด ๋ค์๋ค.
combination์ ์ฌ์ฉํ์ฌ ์ด๋ฅผ ๊ตฌํํด๋๋ค.
๊ณ์ ์ต์ ํํ๋ ค๋ค ๋ณด๋ ์คํ๋ ค ๊ธฐ๋ณธ์ ์ธ ์ฝ๋๋ฅผ ๋์น์ง ์์๋
๋จผ์ ์ด๋ป๊ฒ๋ ์ฝ๋๊ฐ ๋์๊ฐ๊ฒ ํ๊ณ ๊ทธ ๋ค์ ์ต์ ํ๋ฅผ ์๊ฐํ๋ ๋ฐฉํฅ์ผ๋ก ์งํํด๋ณด์.
# ์ฝ๋
# 2025-04-25 14:15-15:15
import sys
sys.stdin = open("input.txt","r")
from collections import deque
from itertools import combinations
import copy
n, m = map(int,sys.stdin.readline().split())
graph = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
empty = []
virus = []
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
empty.append((i,j))
if graph[i][j] == 2:
virus.append((i,j))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs_virus(graph,x,y):
queue = deque()
queue.append((x,y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
graph[nx][ny] = 2
queue.append((nx,ny))
# ๋ฒฝ 3๊ฐ ์ธ์ฐ๊ธฐ
max_cnt = -1
for walls in combinations(empty,3):
tmp_graph = copy.deepcopy(graph)
for wx, wy in walls:
tmp_graph[wx][wy] = 1
for vx, vy in virus:
bfs_virus(tmp_graph,vx,vy)
cnt = sum(row.count(0) for row in tmp_graph)
max_cnt = max(max_cnt, cnt)
print(max_cnt)
# ์ฐธ๊ณ (์ฝ๋ ๊น๋ํ๊ฒ)
๋ง์ง๋ง์ tmp_graph์์ 0์ธ ๊ฐ์๋ฅผ ์ธ๋๊ฑธ ๋ ๊น๋ํ๊ฒ ํ์ด๋ณผ ์ ์๋ค๋ ๊ฒ์ ๋ฐฐ์ ๋ค.
๊ธฐ์กด ์ฝ๋๋ ๋ ๊ธธ์์
# 2025-04-25 14:15-15:15
import sys
sys.stdin = open("input.txt","r")
from collections import deque
from itertools import combinations
import copy
n, m = map(int,sys.stdin.readline().split())
graph = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
empty = []
virus = []
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
empty.append((i,j))
if graph[i][j] == 2:
virus.append((i,j))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs_virus(graph,x,y):
queue = deque()
queue.append((x,y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
graph[nx][ny] = 2
queue.append((nx,ny))
# ๋ฒฝ 3๊ฐ ์ธ์ฐ๊ธฐ
max_cnt = -1
for walls in combinations(empty,3):
tmp_graph = copy.deepcopy(graph)
for wx, wy in walls:
tmp_graph[wx][wy] = 1
for vx, vy in virus:
bfs_virus(tmp_graph,vx,vy)
cnt = 0
for i in range(n):
for j in range(m):
if tmp_graph[i][j] == 0:
cnt += 1
if cnt > max_cnt:
max_cnt = cnt
print(max_cnt)
'๐ Study > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Gold V] 16926 - ๋ฐฐ์ด ๋๋ฆฌ๊ธฐ1 (0) | 2025.04.27 |
---|---|
[Gold IV] 1107 - ๋ฆฌ๋ชจ์ปจ (0) | 2025.04.25 |
[Gold V] 15486 - ํด์ฌ2 (0) | 2025.04.20 |
[Silver I] 1699 - ์ ๊ณฑ์์ ํฉ (0) | 2025.04.19 |
[Silver I] 1389 - ์ผ๋น ๋ฒ ์ด์ปจ์ 6๋จ๊ณ ๋ฒ์น (0) | 2025.04.19 |