[알고리즘] 백준 7569 토마토 2단계 -dfs, bfs- 자바 코틀린

www.acmicpc.net/problem/7569

7569번: 토마토

 

 

 

백준 토마토 2단계(?)를 풀어봤습니다. ㅎㅎ

 

youngest-programming.tistory.com/197

[알고리즘] 백준 7576 토마토 -bfs, dfs-

예쩐에 푼 토마토 문제의 연장선이고 3차원인 것을 제외하면 동일합니다.

해결방법은 비슷하므로 빨리 코드는 짯지만 한가지 실수를 해서 삽질을 했습니다.

 

 

 

3차원 배열을 입력받아 초기화하는 부분인데요.

이 부분을 입력값대로 H(3차원) -> N(2차원) -> M(1차원) 순서로 for문을 돌려야했는데 N->M->H 로 돌려서 예제입력 2번이 계쏙 다른 결과가 나왔었습니다. 주의해야하겠습니다.

for (int k = 1; k <= H; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    map[i][j][k] = sc.nextInt();
                    if (map[i][j][k] == 1) {
                        queue.offer(new Point(i, j, k));
                    }

                }
            }
        }

 

 

 

풀이는 다음과 같습니다.

[Java]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

    private static int N; //1차원
    private static int M; //2차원
    private static int H; //3차원
    private static int[][][] map;
    private static int[] dx = {-1, 0, 1, 0, 0, 0};
    private static int[] dy = {0, -1, 0, 1, 0, 0};
    private static int[] dz = {0, 0, 0, 0, -1, 1};
    private static TreeSet<Integer> resultTreeSet = new TreeSet();
    private static Queue<Point> queue = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        H = sc.nextInt();
        map = new int[N + 2][M + 2][H + 2];
        //바깥쪽 세팅을 위한 for 문 (테두리가 아닌 값도 세팅해서 시간오버플로우가 생기긴함)
        for (int i = 0; i < N + 2; i++) {
            for (int j = 0; j < M + 2; j++) {
                for (int k = 0; k < H + 2; k++) {
                    map[i][j][k] = -1;
                }
            }
        }
        for (int k = 1; k <= H; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    map[i][j][k] = sc.nextInt();
                    if (map[i][j][k] == 1) {
                        queue.offer(new Point(i, j, k));
                    }

                }
            }
        }

        //탐색
        bfs();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                for (int k = 1; k <= H; k++) {
                    if (map[i][j][k] == 0) { //익지 못하는 상황
                        System.out.println(-1);
                        return;
                    }
                }
            }
        }
        if (resultTreeSet.isEmpty()) { // 모드 토마토가 익어있는 상태
            System.out.println(0);
        } else {
            System.out.println(resultTreeSet.pollLast() - 1);
        }
    }

    static void bfs() {
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 6; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                int z2 = point.z + dz[i];
                if (map[x2][y2][z2] == 0) {
                    map[x2][y2][z2] = map[point.x][point.y][point.z] + 1;
                    resultTreeSet.add(map[x2][y2][z2]);
                    queue.offer(new Point(x2, y2, z2));
                }
            }
        }
    }

    static class Point {
        int x;
        int y;
        int z;

        public Point(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }


}

 

[Kotlin]

import java.util.*

private var N: Int = 0 //1차원
private var M: Int = 0 //2차원
private var H: Int = 0 //3차원
private var map: Array<Array<IntArray>>? = null
private val dx = intArrayOf(-1, 0, 1, 0, 0, 0)
private val dy = intArrayOf(0, -1, 0, 1, 0, 0)
private val dz = intArrayOf(0, 0, 0, 0, -1, 1)
private val resultTreeSet = TreeSet<Int>()
private val queue = LinkedList<Point>()


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    M = sc.nextInt()
    N = sc.nextInt()
    H = sc.nextInt()
    map = Array(N + 2) { Array(M + 2) { IntArray(H + 2) } }
    //바깥쪽 세팅을 위한 for 문 (테두리가 아닌 값도 세팅해서 시간오버플로우가 생기긴함)
    for (i in 0 until N + 2) {
        for (j in 0 until M + 2) {
            for (k in 0 until H + 2) {
                map!![i][j][k] = -1
            }
        }
    }
    for (k in 1..H) {
        for (i in 1..N) {
            for (j in 1..M) {
                map!![i][j][k] = sc.nextInt()
                if (map!![i][j][k] == 1) {
                    queue.offer(Point(i, j, k))
                }

            }
        }
    }

    //탐색
    bfs()
    for (i in 1..N) {
        for (j in 1..M) {
            for (k in 1..H) {
                if (map!![i][j][k] == 0) { //익지 못하는 상황
                    println(-1)
                    return
                }
            }
        }
    }
    if (resultTreeSet.isEmpty()) { // 모드 토마토가 익어있는 상태
        println(0)
    } else {
        println(resultTreeSet.pollLast()!! - 1)
    }
}

fun bfs() {
    while (!queue.isEmpty()) {
        val point = queue.poll()
        for (i in 0..5) {
            val x2 = point.x + dx[i]
            val y2 = point.y + dy[i]
            val z2 = point.z + dz[i]
            if (map!![x2][y2][z2] == 0) {
                map!![x2][y2][z2] = map!![point.x][point.y][point.z] + 1
                resultTreeSet.add(map!![x2][y2][z2])
                queue.offer(Point(x2, y2, z2))
            }
        }
    }
}

data class Point(var x: Int, var y: Int, var z: Int)

 

 

 

github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%207569%20%ED%86%A0%EB%A7%88%ED%86%A02%EB%8B%A8%EA%B3%84

mtjin/algorithm_practice

 

 

댓글과 공감은 큰 힘이 됩니다. 

감사합니다 !!