7676번:토마토

토마토:7576

package dfs.Day250303;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Day01_토마토_7576 {

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Tomato[][] box;
    static boolean[][] visited;
    static int n;
    static int m;
    static ArrayList<Xy> xyIndex = new ArrayList<>();

    static class Tomato {
        int day;
        int x;
        int y;

        public Tomato(int day, int x, int y) {
            this.day = day;
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
//            return " | " + "day " + day + " x: " + x + "y: " + y + " | ";
            return " | " + "day " + day + " | ";
        }
    }

    static class  Xy {
        int x;
        int y;

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

        @Override
        public String toString() {
            return "x : " + x + " y : " + y;
        }

    }

    public static int bfs(ArrayList<Xy> xy) {
        ArrayDeque<Tomato> queue = new ArrayDeque<>();
        int result = 0;
        for (Xy xy1 : xy) {
            queue.add(box[xy1.y][xy1.x]);
            visited[xy1.y][xy1.x] = true;
        }

        while (!queue.isEmpty()) {
            Tomato pollTomato = queue.poll();
            result = pollTomato.day;

            for (int i = 0; i < 4; i++) {
                int xx = dx[i] + pollTomato.x;
                int yy = dy[i] + pollTomato.y;

                if (xx >= 0 && yy >= 0 && xx < m && yy < n && !visited[yy][xx] && box[yy][xx].day != -1) {
                    visited[yy][xx] = true;
                    box[yy][xx] = new Tomato(pollTomato.day + 1, xx, yy);
                    queue.add(box[yy][xx]);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken()); // 가로
        n = Integer.parseInt(st.nextToken()); // 세로

        box = new Tomato[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                box[i][j] = new Tomato(Integer.parseInt(st.nextToken()), j, i);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (box[i][j].day == 1) {
                    xyIndex.add(new Xy(j, i));
                }
            }
        }


        int endBfs = bfs(xyIndex);;
        int total = 0;
        for (Tomato[] t : box) {
            for (Tomato tomato: t) {
                if (tomato.day == 0) {
                    total = -1;
                }
            }
        }

        if (total == -1) {
            System.out.println(total);
        } else {
            System.out.println(endBfs - 1);
        }
    }
}

문제

이번에는 토마토라는 문제를 풀었습니다. 난이도는 골드5로 생각보다 어려웠습니다.

가로 세로길이가 주어지면 그 크기에 맞는 박스에는 0, 1, -1 숫자들이 들어있습니다.

• 0, 1은 토마토입니다.
  • 1은 토마토 익은 토마토입니다.
  • 0은 익지 않은 토마토입니다.
• -1은 아무것도 없다는 뜻입니다.

익은 토마토들은 익지 않은 토마토 상하좌우에 하루정도 있으면 익습니다.
구해야되는 것은 토마토돌이 몇일이나 지나야지 전부 익는지 구해야됩니다.

풀이

토마토들은 한번에 동시에 익어야 되므로 bfs를 써야겠네? 라는 생각으로 아무생각없이 Tomato 클래스를 만들고 bfs를 돌도록 했습니다.
그런데 여기서 문제가 생겼습니다. 바로 토마토들이 동시에 익지 않는 점이었습니다.

해결

Xy 클래스들을 만들어서 queue에 미리 익은 토마를 전부 넣어서 동시에 진행하게 해서 해결했습니다.

아쉬운점

전부 푼 후 제출후 정답처리가 뜨고 나서 코드를 보니 굳이 토마토와 Xy를 나눌 필요가 없어보였습니다.
이미 Tomato 클래스에는 x, y라는 필드가 있었으니 이것을 재활용하면 되보였습니다.

마무리

생각보다 많은 시간이 걸렸지만 아무것도 보지 않고 풀었습니다.
내일은 어떤 문제를 풀지 고민중입니다.