๐Ÿ“š Study/Baekjoon

[Gold IV] 14502 - ์—ฐ๊ตฌ์†Œ

์œฐ๊ฐฑ 2025. 4. 25. 15:34

๋ฌธ์ œ

์ธ์ฒด์— ์น˜๋ช…์ ์ธ ๋ฐ”์ด๋Ÿฌ์Šค๋ฅผ ์—ฐ๊ตฌํ•˜๋˜ ์—ฐ๊ตฌ์†Œ์—์„œ ๋ฐ”์ด๋Ÿฌ์Šค๊ฐ€ ์œ ์ถœ๋˜์—ˆ๋‹ค. ๋‹คํ–‰ํžˆ ๋ฐ”์ด๋Ÿฌ์Šค๋Š” ์•„์ง ํผ์ง€์ง€ ์•Š์•˜๊ณ , ๋ฐ”์ด๋Ÿฌ์Šค์˜ ํ™•์‚ฐ์„ ๋ง‰๊ธฐ ์œ„ํ•ด์„œ ์—ฐ๊ตฌ์†Œ์— ๋ฒฝ์„ ์„ธ์šฐ๋ ค๊ณ  ํ•œ๋‹ค.

์—ฐ๊ตฌ์†Œ๋Š” ํฌ๊ธฐ๊ฐ€ 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)