나를 울게 만든 BFS... 그리고 백준 토마토 접근도 못 하겠는 사람 모여

네이버 코테 전날 알고리즘을 1 도 모르면서 벼락치기 라도 해보겠다고 BFS 문제를 허겁지겁 풀다가 토마토에서 막혀버렸다... 밤은 늦었고 내일 코테는 어차피 글렀고... 어차피 경험 삼으려고 신청한 거고... 하며 답답한 마음으로 집에 가는데 서러워져서 울었다 ㄹㅇ임

진짜 어떻게 하라는 건지 감도 안 잡히는 거야

평생 이 모양으로 살까봐 눈물을 훔쳤다

그니까 BFS 란 그래프나 트리에서 가까운 노드부터 탐색해 나가는 알고리즘이다. BFS 는 같은 레벨 (거리) 에 있는 노드를 먼저 다 본 다음, 그 다음 레벨로 넘어간다.

 

BFS 알고리즘을 작성할 때의 특징

• 큐(Queue) 자료구조 사용
• 최단 거리 문제에 자주 쓰임
• 방문한 노드를 다시 방문하지 않도록 visited 배열을 사용

동작 방식

1. 시작 노드를 큐에 넣고 방문 표시
2. 큐에서 노드를 꺼냄
3. 해당 노드와 연결된 (방문하지 않은) 노드들을 큐에 추가하고 방문 표시
4. 큐가 빌 때까지 반복

그러니까, bfs 문제를 풀 때 보편적으로 하고 넘어가는 단위 작업은 큐 만들기, visited 배열 만들기다.

 

BFS 알고리즘이 쓰이는 곳

• 최단 경로 문제  (ex. 미로 탈출, 지하철 노선)
• 레벨 탐색 (트리의 레벨 순회)
• 소셜 네트워크 (ex. 친구 추천 : 친구의 친구까지)

🍅 토마토 문제 풀기

• 창고에 보관된 토마토 중 일부는 익어 있고, 일부는 아직 익지 않았다.
• 하루가 지나면 익은 토마토에 인접한 (상하좌우) 익지 않은 토마토는 익게 된다.
• 모든 토마토가 익는 데 걸리는 최소 일수를 구한다.
• 익지 못하는 토마토가 하나라도 있다면 -1 을 출력한다.

1. 여러 개의 시작점에서 BFS 를 시작한다.
2. 인접한 익지 않은 토마토를 하루씩 더해가며 BFS 를 한다.
3. 마지막에 max (걸린 일 수) 계산을 한다.

여러 개의 시작점 찾기

for i in range(n):
    for j in range(m):
        if grid[i][j] == 1:
            queue.append((i, j))

이중 for 문을 통해 전체 격자 (grid) 를 순회한다. grid[i][j] 가 1 이면 이미 익은 토마토라는 뜻이다. 그런 좌표들을 먼저 큐(에 담아 퍼뜨릴 것이다.

BFS 실행하기

while queue:
    x, y = queue.popleft()

큐에 있는 좌표를 하나씩 꺼내서 현재 익은 토마토의 좌표를 가져온다. 즉 x, y 는 현재 위치이다. 이 위치에서 상하좌우 인접칸을 살펴본다.

상하좌우 탐색

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

상하좌우 네 방향을 탐색하기 위해 미리 설정된 dx, dy 를 사용한다.

dx = [1, -1, 0, 0]  # 아래, 위, 오른쪽, 왼쪽
dy = [0, 0, 1, -1]

g

nx, ny 는 다음에 확인할 좌표다. (next) 현재 위치 (x, y) 에서 한 칸씩 이동한 좌표.

유효한 범위인지 + 익지 않은 토마토인지 확인

if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 0:

(nx, ny) 가 격자 밖으로 나가지 않도록 범위를 체크하고 grid[nx][ny] 가 0 인 경우에만 진행한다. -> 아직 익지 않은 토마토일 때만 처리하는 것이다. 

토마토 익게 만들고 큐에 넣기

    grid[nx][ny] = grid[x][y] + 1
    queue.append((nx, ny))

토마토가 익었다! 하루가 더 지난 거니까 현재 칸보다 1 을 더한다. 처음 익은 토마토가 1 로 시작하므로 익은 날짜는 2, 3, 4, ... 로 올라간다, 그리고 그 위치를 큐에 추가해서 나중에 그 자리도 중심으로 BFS 가 계속 돌 수 있게 한다.

 

1. 처음에 익은 토마토 위치들 (1인 곳) 을 다 큐에 넣음
2. 그 자리들부터 시작해서 상하좌우 인접한 칸이 0 이면 익힘 (날짜 +1)
3. 그렇게 익힌 자리를 또 큐에 넣고, 다시 그 자리에서 퍼뜨림
4. 큐가 빌 때까지 반복 -> 즉, 모든 익을 수 있는 토마토 다 익히기까지 반복

from collections import deque

# 입력 받기 (가로 M, 세로 N)
M, N = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(N)]

# 큐 초기화: 익은 토마토(1)의 위치를 모두 넣음
queue = deque()
for i in range(N):
    for j in range(M):
        if grid[i][j] == 1:
            queue.append((i, j))

# 방향 설정: 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 시작
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 grid[nx][ny] == 0: # grid 내에 존재하고 안 익은 토마토일 때
            grid[nx][ny] = grid[x][y] + 1 # 다음 좌표는 현재 좌표 숫자 day + 1
            queue.append((nx, ny))


max_days = 0

for row in grid:
    for cell in row:
        if cell == 0:
            print(-1)  # 익지 못한 토마토 있음
            exit(0)
    max_days = max(max_days, max(row))

# 최소 일수 = 최댓값 - 1 (처음 시작이 1이었으므로)
print(max_days - 1)

나름 깔끔하게 푼 거 같지 않나... 애쓰셨다