7569
- 알고리즘 : BFS
- 난이도 : 골드5
문제
접근
- 토마토가 익기위한 최소 날짜를 구해야한다.
- 상,하,좌,우, 위, 아래 로 익는다.
- 상자 위와 사자 아래를 탐색하는 것이 핵심인듯 하다.
- 2차원 평면 탐색이 아닌 3차원 탐색을 하려면 어떻게 해야 할까?
- Z축을 추가해서 탐색을 해야한다.
가정
-BFS 로 푸는데 Z축을 추가해서 풀어야한다.
풀어보기
package org.example;
import java.util.*;
public class Main {
// 3차원 토마토 상자의 크기와 상태를 저장할 변수들
private static int[][][] box;
private static boolean[][][] visited;
private static int M, N, H;
// 이동 방향 (상, 하, 좌, 우, 위, 아래)
private static final int[] dx = {-1, 1, 0, 0, 0, 0};
private static final int[] dy = {0, 0, -1, 1, 0, 0};
private static final int[] dz = {0, 0, 0, 0, -1, 1};
// BFS로 토마토 익히기
private static int bfs(List<int[]> ripeTomatoes) {
Queue<int[]> queue = new LinkedList<>(ripeTomatoes);
int days = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] pos = queue.poll();
int x = pos[0];
int y = pos[1];
int z = pos[2];
// 6가지 방향으로 탐색
for (int d = 0; d < 6; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
int nz = z + dz[d];
// 상자의 경계를 넘지 않으며, 익지 않은 토마토가 있고, 아직 방문하지 않은 위치일 경우
if (nx >= 0 && nx < H && ny >= 0 && ny < N && nz >= 0 && nz < M) {
if (box[nx][ny][nz] == 0 && !visited[nx][ny][nz]) {
visited[nx][ny][nz] = true;
box[nx][ny][nz] = 1; // 토마토를 익힌다
queue.offer(new int[]{nx, ny, nz});
}
}
}
}
if (!queue.isEmpty()) {
days++;
}
}
return days;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M = sc.nextInt(); // 상자의 가로 길이
N = sc.nextInt(); // 상자의 세로 길이
H = sc.nextInt(); // 상자의 높이
box = new int[H][N][M];
visited = new boolean[H][N][M];
List<int[]> ripeTomatoes = new ArrayList<>();
// 토마토 상자의 초기 상태 입력 받기
for (int h = 0; h < H; h++) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
box[h][n][m] = sc.nextInt();
if (box[h][n][m] == 1) {
ripeTomatoes.add(new int[]{h, n, m});
visited[h][n][m] = true;
}
}
}
}
// 모든 토마토를 익히는 데 걸리는 시간을 계산
int days = bfs(ripeTomatoes);
// 익지 않은 토마토가 남아있는지 확인
for (int h = 0; h < H; h++) {
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
if (box[h][n][m] == 0) {
System.out.println(-1);
return;
}
}
}
}
// 결과 출력
System.out.println(days);
}
}
시행착오
- x와 Z가 헷갈려서 풀기 어려웠다.
- 3중 중첩을 이용할 수 밖에 없어서 가독성이 떨어졌다.
- 시작 지점을 선택하기위해 3중 중첩에 List를 BFS로 넘겨주었다.
- 시간 복잡도를 생각하면 굉장히 비효율 적이다.
참고자료
- 큐 예제코드
import java.util.*;
public class BFSExample {
// 그래프의 크기와 방문 여부를 저장할 변수들
private static int[][] graph;
private static boolean[][] visited;
private static int rows, cols;
// 이동 방향 (상, 하, 좌, 우)
private static final int[] dx = {-1, 1, 0, 0};
private static final int[] dy = {0, 0, -1, 1};
// BFS로 연결된 부분을 탐색하여 방문 처리
private static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
visited[x][y] = true;
while (!queue.isEmpty()) {
int[] pos = queue.poll();
int currX = pos[0];
int currY = pos[1];
// 4가지 방향으로 탐색
for (int i = 0; i < 4; i++) {
int nx = currX + dx[i];
int ny = currY + dy[i];
// 그래프의 경계를 넘지 않으며, 연결된 노드가 있고, 아직 방문하지 않은 위치일 경우
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
if (graph[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
rows = sc.nextInt(); // 그래프의 행 크기
cols = sc.nextInt(); // 그래프의 열 크기
graph = new int[rows][cols];
visited = new boolean[rows][cols];
// 그래프 초기화: 1은 연결된 노드, 0은 비어 있는 노드로 간주
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
graph[i][j] = sc.nextInt();
}
}
int groupCount = 0; // 연결된 그룹의 수
// 그래프의 각 위치를 순회하며 BFS로 군집 찾기
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (graph[i][j] == 1 && !visited[i][j]) {
bfs(i, j);
groupCount++; // 새로운 군집을 찾을 때마다 카운트 증가
}
}
}
System.out.println(groupCount); // 총 연결된 군집의 수 출력
sc.close();
}
}
AllTimeDevelop