[Python] 백준 7576 & 백준 14502

# 백준 7576

from collections import deque
import sys

m, n = map(int, input().split())
input = sys.stdin.readline()
graph = [list(map(int, input.split())) for _ in range(n)]

d_row = [0, -1, 0, +1]
d_col = [+1, 0, -1, 0]
# 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
def bfs():
    queue = deque()
    count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                queue.append([i,j])
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            # 익은 토마토 상하좌우 돌면서 일수 저장
            nx = x + d_row[i]
            ny = y + d_col[i]
            if nx< 0 or ny < 0 or nx > n-1 or ny > m-1:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append([nx,ny])

bfs()
answer = 0

for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            print(-1)
            exit()
        answer = max(answer, graph[i][j])
print(answer-1)

 

# 백준 14502번

from collections import deque
import copy

n, m = map(int, input().split(' '))
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

d_row = [0, -1, 0, +1]
d_col = [+1, 0, -1, 0]

def make_wall(cnt):
    if cnt == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                make_wall(cnt+1)
                graph[i][j] = 0

def bfs():
    queue = deque()
    temp_graph = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if temp_graph[i][j] == 2:
                queue.append((i, j))

    while queue:
        x, y = queue.popleft()
        for z in range(4):
            nx = x + d_row[z]
            ny = y + d_col[z]
            if nx < 0 or ny < 0 or nx > n - 1 or ny > m - 1:
               continue
            if temp_graph[nx][ny] == 0:
               temp_graph[nx][ny] = 2
               queue.append((nx, ny))

    global result
    cnt = 0
    for w in range(n):
        cnt += temp_graph[w].count(0)

    result = max(result,cnt)

result = 0
make_wall(0)
print(result)

 

 

📝 Points

1. 최소, 최대 일수 구할때는 graph 에 값 저장

2. 랜덤으로 벽 세울때는 재귀에서 빠져나올때 원상복구 하기