[백준] 7576번 토마토 / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
24. DFS와 BFS
그래프를 순회하는 알고리즘을 배워 봅시다.
그래프를 순회하는 알고리즘을 배워 봅시다.
Java / Python
6. 토마토
BFS로 토마토를 익히는 문제
이번 문제는 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하는 문제입니다. (단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.)
BFS 탐색을 이용했습니다.
- Java
import java.io.*;
import java.util.*;
class tomato{
int x; // 세로
int y; // 가로
tomato(int x, int y){
this.x = x;
this.y = y;
}
}
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int N, M;
static int[][] board;
static int result = 0;
static Queue<tomato> queue;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
board = new int[N][M];
queue = new LinkedList<tomato>();
for(int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < M; j++){
board[i][j] = Integer.parseInt(st.nextToken());
if(board[i][j] == 1)
queue.add(new tomato(i,j));
}
}
bfs();
bw.write(result + "\n");
bw.flush();
bw.close();
br.close();
}
public static void bfs(){
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] == 1)
//익은 토마토가 있는 모든 위치를 큐에 담는다.
queue.add(new tomato(i, j));
}
}
while(!queue.isEmpty()) {
tomato tom = queue.poll();
for(int i = 0; i < 4; i++) {
int nx = tom.x + dx[i];
int ny = tom.y + dy[i];
if(nx >= 0 && ny >= 0 && nx < N && ny < M) {
if(board[nx][ny] == 0){
queue.add(new tomato(nx, ny));
board[nx][ny] = board[tom.x][tom.y] + 1;
}
}
}
}
result = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(board[i][j] == 0){
result = -1;
return;
}
result = Math.max(result, board[i][j]);
}
}
result = result - 1;
}
}
- Python
from collections import deque
import sys
M, N = map(int, sys.stdin.readline().split())
tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
# queue 방식 사용 (deque 필수 X)
queue = deque()
for i in range(N):
for j in range(M):
if tomato[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 k in range(4):
nx = x + dy[k]
ny = y + dx[k]
if 0 <= nx < N and 0 <= ny < M and tomato[nx][ny] == 0:
tomato[nx][ny] = tomato[x][y] + 1
queue.append([nx, ny])
result = -2
check = False # 안 익은게 있는지 확인
for i in tomato:
for j in i:
if(j == 0):
check = True
result = max(result, j)
if check:
print(-1)
elif result == -1:
print(0)
else:
print(result - 1)
Author And Source
이 문제에 관하여([백준] 7576번 토마토 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-7576번-토마토-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)