[DFS, BFS] 백준 7576번: 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

으아아아악!!! 중간에 꼬여서 3시간 정도 걸린 거 같다..

import collections
y_lim, x_lim = map(int, input().split())

table=[]
for i in range(x_lim):
    table.append(input().split())

q = collections.deque()

for x in range(x_lim):
    for y in range(y_lim):
        if table[x][y] == '1':
            q.append([x - 1, y, 0])
            q.append([x + 1, y, 0])
            q.append([x, y - 1, 0])
            q.append([x, y + 1, 0])

ans = -1
while q:
    x, y, day = q.popleft()
    ans = day
    if (0 <= x < x_lim) and (0 <= y < y_lim) and table[x][y]=='0':
        table[x][y]='1'
        q.append([x-1, y, day+1])
        q.append([x+1, y, day+1])
        q.append([x, y-1, day+1])
        q.append([x, y+1, day+1])

possible = True
for x in range(x_lim):
    for y in range(y_lim):
        if table[x][y]=='0':
            possible = False
            break
    if not possible:
        break

if possible:
    print(ans)
else:
    print(-1)

BFS로 풀이가 가능하다.

주의할 점은 처음에 1값을 가진 토마토들의 정보를 가져온다음 bfs를 해야한다.

이후부터는 0값을 가진 토마터들을 q에 넣는다.

++ 좀 더 깔끔하게 고쳐봤다.

위의 코드에선 day를 q안에 같이 넣어갔었는데 아래 코드는 하루 간격으로 while문이 돌아가게 된다. 아래에 있는 for문으로 인해!

import collections
y_lim, x_lim = map(int, input().split())

table=[]
q = collections.deque()

for x in range(x_lim):
    table.append(input().split())
    for y in range(y_lim):
        if table[x][y] == '1':
            q.append([x, y])

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(q):
    day= -1
    while q:
        day +=1
        n = len(q)
        for _ in range(n):
            x,y = q.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if (0 <= nx < x_lim) and (0 <= ny < y_lim) and table[nx][ny]=='0':
                    table[nx][ny] = '1'
                    q.append([nx, ny])

    for x in range(x_lim):
        for y in range(y_lim):
            if table[x][y]=='0':
                return -1
    return day

print(bfs(q))