[BOJ] 99클럽 코테 스터디 12일차 TIL : 7569-토마토-BFS
문제
백준 토마토 | 골드 5
#그래프 이론 #그래프 탐색 #너비 우선 탐색
https://www.acmicpc.net/problem/7569
📌 문제 탐색하기
- 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 것 → 익어짐
- 1 : 익은 토마토
- 0 : 익지 않은 토마토
- -1 : 토마토가 들어있지 않음
- 상하좌우, 앞, 뒤 여섯 방향에 영향을 줄 수 있다.
- 며칠이 지나면 다 익게 되는지 최소 일수를 확인한다.
- 단, 저장될 때부터 모든 토마토가 익어 있으면 0 출력
- 토마토를 모두 익히지 못하는 상황일 경우 -1 출력
📌 알고리즘 선택
- 최소한의 일수로 모든 토마토가 익어야하므로 DFS/BFS로 완전탐색을 진행할 수 있다.
- 현재 상자의 크기, 상자의 수가 최대 100, 100, 100이므로 최대 10 ^ 6이 되므로 256MB, 1초 안에 가능할까 ?
- 1초에 1억번을 기준으로 문제를 푼다는 가정하에 완전탐색이 가능한 조건이다.
- 현재 상자의 크기, 상자의 수가 최대 100, 100, 100이므로 최대 10 ^ 6이 되므로 256MB, 1초 안에 가능할까 ?
- DFS와 BFS 중 BFS를 선택해야한다.
- 문제에서 하루가 지나면 6개의 방향의 토마토가 모두 익는 것을 확인할 수 있다. 그러므로 깊이 우선 탐색이 아닌, 너비 우선 탐색으로 진행해야한다.
📌 코드 설계하기
1. 상자의 크기 및 상자 내의 토마토 정보 입력값 받기
2. 정수가 0(익지 않은 토마토) 위치를 Queue에 넣어두기
⇒ Queue에 넣음으로써 각 위치별로 완전탐색 진행 가능
3. BFS 로직 구현
⇒ 갈 수 있는 공간인지 체크하는 로직 구현 (outOfGraph)
⇒ 이를 위해 Point 객체 구현
4. graph 전체를 돌며 모두 익히지 못하는 경우, 처음부터 불가능했던 경우, day를 추출할 수 있는 경우를 프린트
📌 시도 회차 수정 사항
1회차
* 2번째 EXAMPLE에서 계속 30이 나옴
* day를 추가하는 로직이 이게 아닌 것 같다는 생각이..
* 생각해보니, 최소의 day를 구해야되는거니까 배열마다 그 전의 토마토 날짜에 +1을 해줘야함.
* 또한, canGo 메소드를 굳이 하지 않고 새로 옮기는 칸이 0인 것을 체크해줘야함.
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
static int m, n, h, day = 0;
static int[][][] graph;
static int[][][] visited;
static Queue<Point> startQueue = new LinkedList<Point>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken()); //상자의 가로 칸
n = Integer.parseInt(st.nextToken()); //상자의 세로 칸
h = Integer.parseInt(st.nextToken()); //상자의 수 (쌓아올려지는)
graph = new int[h][n][m];
visited = new int[h][n][m];
for (int z = 0; z < h; z++) {
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
graph[z][i][j] = Integer.parseInt(st.nextToken());
if (graph[z][i][j] == 1) {
startQueue.offer(new Point(z, i, j));
}
}
}
}
if (isAllDone()) {
System.out.println(0);
} else {
bfs();
if (isAllDone()) {
System.out.println(day - 1);
} else {
System.out.println(-1);
}
}
}
public static void bfs() {
int[] dh = {0, 0, 0, 0, -1, 1}; //상하좌우위아래
int[] dx = {-1, 1, 0, 0, 0, 0};
int[] dy = {0, 0, -1, 1, 0, 0};
while (!startQueue.isEmpty()) {
Point p = startQueue.poll();
for (int i = 0; i < 6; i++) {
int nh = p.h + dh[i];
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (outOfGraph(nh, nx, ny)) {
if(graph[nh][nx][ny] == 0) {
graph[nh][nx][ny] = graph[p.h][p.x][p.y] + 1;
startQueue.offer(new Point(nh, nx, ny));
}
}
}
}
}
public static boolean outOfGraph(int hei, int x, int y) {
return 0 <= hei && hei < h && 0 <= x && x < n && 0 <= y && y < m;
}
public static boolean isAllDone() {
for (int z = 0; z < h; z++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (graph[z][i][j] == 0) {
return false;
} else {
day = Math.max(day, graph[z][i][j]);
}
}
}
}
return true;
}
}
class Point {
int h;
int x;
int y;
public Point(int h, int x, int y) {
this.h = h;
this.x = x;
this.y = y;
}
}
회고 & 배운점
* BFS 공부 (https://www.notion.so/dev-if/f2a7fe2bdc3b4878aef9442fe5ff0d20?pvs=4#51fe65b400d04edcb21f58396e7bf82d)
* 매번 2차원으로 bfs를 풀다가, 3차원으로 접근하니 좌표를 어떻게 구성해야할지 다시 고민해 볼 수 있었다.
* int[] dh = {0, 0, 0, 0, -1, 1};
* int[] dx = {-1, 1, 0, 0, 0, 0};
* int[] dy = {0, 0, -1, 1, 0, 0};
* 문제에서 요구하는 것이 '최소' 이므로 visited를 통해 구하는 것이 아닌, graph에 +1을 하며 값을 늘려 나가는 방법을 배웠다.