.jpg)
문제 링크 : https://www.acmicpc.net/problem/7576
import sys
r = sys.stdin.readline
global cnt
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
queue = []
cnt = -1
M, N = map(int,r().split())
tomatoes = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
for j in range(M):
if tomatoes[i][j] == 1:
queue.append([i,j])
while queue:
cnt += 1
x, y = queue.pop(0)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<N and 0<=ny<M and tomatoes[nx][ny] == 0:
tomatoes[nx][ny] = tomatoes[x][y] + 1
queue.append([nx, ny])
for i in tomatoes:
if 0 in i:
cnt = -1
print(cnt)SSAFY에서도 개발자 블로그를 하나 만들어, 기록하는 습관을 들이라기에 1학기가 절반 가량 지나간 지금 드디어(?) Velog라도 만들어보기로 했다. 스타팅 포스트는 뭐가 좋을까 하다 보니, 코드 짤 때 주석을 안 적어버릇 하는 것도 고칠 겸 해서 BFS 입문을 시켜준 BOJ 토마토 알고리즘을 해석하고 코드 리뷰를 해보는 게 좋겠다 싶다.
BFS의 교과서적인 문제
개발자를 꿈꾸거나, 혹은 취미로 프로그래밍을 하는 사람들에게는 가장 유명할 문제 중 하나다. 너비 우선 탐색(BFS) 알고리즘을 사용하여 익은 토마토와 익지 않은 토마토를 구분하는 문제다. 코드의 위에서부터 차례로 코멘터리를 달아봐야지.
기초 입력
import sys
from collections import deque
r = sys.stdin.readline
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]-
import sys명령어를 통해 혹시 모를 거대한 입력값을sys.stdin.readline으로 치환할 수 있게 한다. 백준에서는 심하면 2억개라던가 (개미 문제의 트라우마가 생각난다) 하는 인풋이 들어와서, 이건 손에 익어두면 좋을 것 같아. -
네 방향 탐색을 위해
dx,dy배열을 생성한다. (이차원 배열이기 때문에 각기 우/좌/상/하를 값으로 가지게 된다.) -
BFS에 필요한 정보를 저장하는 큐 역할을 위해 디큐를 선언해 큐를 만들 준비를 한다.
기준값의 입력, 토마토의 입력, 시작점 찾기
M, N = map(int,r().split())
tomatoes, q = [], deque()
for i in range(N):
row = list(map(int,r().split()))
for j in range(M):
if row[j] == 1:
q.append([i,j])
tomatoes.append(row)-
M, N은 문제에 나온 대로 입력을 받아준다. 기준값이 될 요소들이니 잘 기억해두자.
-
tomatoes배열에는 이차원 리스트 형식의 토마토들이 들어온다. 한 방에 어펜드하는것도 좋지만, 코드 가독성도 있고 이 때 저 입력법을 처음 배워서 그냥 안전빵으로 갔던 기억이 난다. 박스의 세로 크기인 N만큼 레인지를 도는 데 주의! -
입력값을 한줄한줄 받으면서 시작점을 찾아야지. 하나가 아닐 수 있으니, '1' 이라 기록된 칸들의 좌표를 적어준다.
돌아라, BFS! 돌아라!
def bfs(M, N, box):
days = -1
while q:
days += 1
for _ in range(len(q)):
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if (0<=nx<N) and (0<=ny<M) and (box[nx][ny] == 0):
box[nx][ny] = box[x][y] + 1
q.append([nx, ny])
for b in box:
if 0 in b:
return -1
return days-
BFS는 큐를 사용한다 - 이건 나중에 한번 정리해서 적어봐야겠다. 왜 큐를 사용하는지도 복습의 중요한 동기가 될 테니까.
-
토마토가 다 익을 시간을 적어둬야 한다. 그러니
days가 하나 올라간다 (하루 경과). -
어디서부터 탐색을 재개할지를 정해줘야 한다. 큐에 들어가 있던 맨 앞 칸 값을 뽑아서
x와y를 선언한다. (박스 내에서 토마토가 어디 있는지를 표시해준다.) -
네 방향 탐색을 위한 델타 배열을 순회하기 시작한다.
nx,ny변수를 통해 이제 어느 칸을 볼 건지 체크할 수 있다. -
델타값이 옳은 값이려면 두 가지 조건을 만족해야 한다.
- 박스 안에 들어 있어야 한다 (
0<=nx<N and 0<=ny<M) : 당연한 얘기겠지만, 값이 박스 안에 있어야 익는지 아닌지 알 수 있다. - 아직 방문하지 않은 칸 (익지 않은 토마토)여야 한다 (
tomatoes[nx][ny] == 0) : 나중에는 사용하게 된 Visited 배열의 압축판이다. BFS를 돌면서 방문하지 않은 칸들을 차례로 기록하는 과정이니, 당연히 방문하지 않은 칸을 사용해야 한다. 막힌 칸은 -1로, 토마토는 0이 아닌 값으로 표현되니 다행이다. - 만약 두 조건 모두 만족시키지 못한다면 다시
for문으로 돌아가 반복이 시작될 거고, 이 반복은 큐가 다 사라질 때까지 (더 이상 갈 곳이 없을 때까지) 반복된다. 만족시킨다면? 그럼 그 값이 큐에 들어가서 다시 반복이 시작된다.
- 박스 안에 들어 있어야 한다 (
그래서 최종 값은?
print(bfs(M, N, tomatoes))BFS 함수를 인쇄하면 끝난다.
Velog 처음 포스팅해보는데, 너무 예전 문제라서 기억이 가물가물하다. 그래도 기록하는 셈 치고 꾸준히 써봐야지.
