JAVA 백준 7576 토마토 (그래프)

 

https://www.acmicpc.net/problem/7576

---

문제

1. 첫째 줄에 상자의 크기 M, N ( 2 <= M, N <= 1000)이 주어진다.
2. 둘째 줄에 M, N 크기의 상자에 토마토의 정보가 주어지며, N개의 줄에 M개의 정보가 주어진다.
3. 토마토의 정보는 0 (익지 않은 토마토), 1 (익은 토마토), -1 (토마토가 없음) 로 나누어진다.
4. 익은 토마토와 근접한 토마토만 익을 수 있다. 만약 익은 토마토와 익지 않은 토마토가 빈칸으로 나누어져 있다면 익지 않은 토마토는 익을 수 없다.
5. 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 될 때, 토마토가 처음부터 모두 익어있다면 0을 출력하고, 토마토가 모두 익지 못한다면 -1을 출력한다.

---

 

 

 

초기 코드

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

public class Main {
    public static class Node {
        int row;
        int column;

        public Node(int row, int column) {
            this.row = row;
            this.column = column;
        }
    }

    public static boolean[][] visited;
    public static int date = 0;

    public static void bfs(ArrayList<Node>[][] list, Integer[][] box, int M, int N) {
        Queue<Node> queue = new LinkedList<>();

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < M + 1; j++) {
                if (box[i][j] == 1) {
                    queue.offer(new Node(i, j));
                    visited[i][j] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            boolean check = false;
            int size = queue.size();
            Queue<Node> tempQueue = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                Node num = queue.poll();
                ArrayList<Node> temp = list[num.row][num.column];
                for (int j = 0; j < temp.size(); j++) {
                    if (!visited[temp.get(j).row][temp.get(j).column] && box[temp.get(j).row][temp.get(j).column] != -1) {
                        tempQueue.offer(new Node(temp.get(j).row, temp.get(j).column));
                        visited[temp.get(j).row][temp.get(j).column] = true;
                        box[temp.get(j).row][temp.get(j).column] = 1;
                        check = true;
                    }
                }
            }
            if (check) {
                date++;
            }
            queue.addAll(tempQueue);
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        Integer[][] box = new Integer[N + 1][M + 1];
        ArrayList<Node>[][] list = new ArrayList[N + 1][M + 1];
        visited = new boolean[N + 1][M + 1];

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < M + 1; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < M + 1; j++) {
                list[i][j] = new ArrayList<>();
            }
        }

        boolean flag1 = false;
        boolean flag2 = false;

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < M + 1; j++) {
                flag1 = false;
                flag2 = false;
                if (i == 1) {
                    list[i][j].add(new Node(i + 1, j));
                    if (box[i][j] == 0 && box[i + 1][j] == -1) {
                        flag1 = true;
                    }
                } else if (i == N) {
                    list[i][j].add(new Node(i - 1, j));
                    if (box[i][j] == 0 && box[i - 1][j] == -1) {
                        flag1 = true;
                    }
                } else {
                    list[i][j].add(new Node(i + 1, j));
                    list[i][j].add(new Node(i - 1, j));
                    if (box[i][j] == 0 && box[i + 1][j] == -1 && box[i - 1][j] == -1) {
                        flag1 = true;
                    }
                }

                if (j == 1) {
                    list[i][j].add(new Node(i, j + 1));
                    if (flag1 && box[i][j + 1] == -1) {
                        flag2 = true;
                    }
                } else if (j == M) {
                    list[i][j].add(new Node(i, j - 1));
                    if (flag1 && box[i][j - 1] == -1) {
                        flag2 = true;
                    }
                } else {
                    list[i][j].add(new Node(i, j + 1));
                    list[i][j].add(new Node(i, j - 1));
                    if (flag1 && box[i][j + 1] == -1 && box[i][j - 1] == -1) {
                        flag2 = true;
                    }
                }

                if (flag1 && flag2) {
                    break;
                }
            }
            if (flag1 && flag2) {
                break;
            }
        }

        if (flag1 && flag2) {
            date = -1;
        } else {
            bfs(list, box, M, N);
        }

        System.out.println(date);
    }
}

 

이 코드는 93 퍼센트 쯤에 틀린 코드인데 틀린 이유는 모든 1이 -1로 감싸졌을 때 -1을 출력하지 않고 0을 출력했기 때문이다.

전체적으로 0과 1이 -1으로 나눠져 있을 경우 -1을 출력해야 되기 때문에 이 부분도 수정해줘야 된다.

 

 

최종 코드

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

public class Main {
    public static class Node {
        int row;
        int column;

        public Node(int row, int column) {
            this.row = row;
            this.column = column;
        }
    }

    public static boolean[][] visited;
    public static int date = 0;

    public static void bfs(ArrayList<Node>[][] list, Integer[][] box, int M, int N) {
        Queue<Node> queue = new LinkedList<>();

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < M + 1; j++) {
                if (box[i][j] == 1) {
                    queue.offer(new Node(i, j));
                    visited[i][j] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            boolean check = false;
            int size = queue.size();
            Queue<Node> tempQueue = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                Node num = queue.poll();
                ArrayList<Node> temp = list[num.row][num.column];
                for (int j = 0; j < temp.size(); j++) {
                    if (!visited[temp.get(j).row][temp.get(j).column] && box[temp.get(j).row][temp.get(j).column] != -1) {
                        tempQueue.offer(new Node(temp.get(j).row, temp.get(j).column));
                        visited[temp.get(j).row][temp.get(j).column] = true;
                        box[temp.get(j).row][temp.get(j).column] = 1;
                        check = true;
                    }
                }
            }
            if (check) {
                date++;
            }
            queue.addAll(tempQueue);
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        Integer[][] box = new Integer[N + 1][M + 1];
        ArrayList<Node>[][] list = new ArrayList[N + 1][M + 1];
        visited = new boolean[N + 1][M + 1];

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < M + 1; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < M + 1; j++) {
                list[i][j] = new ArrayList<>();
            }
        }

        boolean flag1 = false;
        boolean flag2 = false;

        boolean flag3 = false;
        boolean flag4 = false;
        int count = 0;


        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < M + 1; j++) {
                flag1 = false;
                flag2 = false;
                if (box[i][j] == 1) {
                    count++;
                }

                if (i == 1) {
                    list[i][j].add(new Node(i + 1, j));
                    if (box[i][j] == 0 && box[i + 1][j] == -1) {
                        flag1 = true;
                    } else if (box[i][j] == 1 && box[i + 1][j] == -1) {
                        flag3 = true;
                    }
                } else if (i == N) {
                    list[i][j].add(new Node(i - 1, j));
                    if (box[i][j] == 0 && box[i - 1][j] == -1) {
                        flag1 = true;
                    } else if (box[i][j] == 1 && box[i - 1][j] == -1) {
                        flag3 = true;
                    }
                } else {
                    list[i][j].add(new Node(i + 1, j));
                    list[i][j].add(new Node(i - 1, j));
                    if (box[i][j] == 0 && box[i + 1][j] == -1 && box[i - 1][j] == -1) {
                        flag1 = true;
                    } else if (box[i][j] == 1 && box[i + 1][j] == -1 && box[i - 1][j] == -1) {
                        flag3 = true;
                    }
                }

                if (j == 1) {
                    list[i][j].add(new Node(i, j + 1));
                    if (flag1 && box[i][j + 1] == -1) {
                        flag2 = true;
                    } else if (box[i][j] == 1 && box[i][j + 1] == -1) {
                        flag4 = true;
                    }
                } else if (j == M) {
                    list[i][j].add(new Node(i, j - 1));
                    if (flag1 && box[i][j - 1] == -1) {
                        flag2 = true;
                    } else if (box[i][j] == 1 && box[i][j - 1] == -1) {
                        flag4 = true;
                    }
                } else {
                    list[i][j].add(new Node(i, j + 1));
                    list[i][j].add(new Node(i, j - 1));
                    if (flag1 && box[i][j + 1] == -1 && box[i][j - 1] == -1) {
                        flag2 = true;
                    } else if (box[i][j] == 1 && box[i][j + 1] == -1 && box[i][j - 1] == -1) {
                        flag4 = true;
                    }
                }

                if (flag1 && flag2) {
                    break;
                }
                if (flag3 && flag4) {
                    count--;
                }
            }
            if (flag1 && flag2) {
                break;
            }
        }

        boolean flag = false;

        if (flag1 && flag2 || count == 0) {
            date = -1;
        } else {
            bfs(list, box, M, N);
            for (int i = 1; i < N + 1; i++) {
                for (int j = 1; j < M + 1; j++) {
                    if (box[i][j] == 0) {
                        flag = true;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
        }

        if (flag) {
            date = -1;
        }

        System.out.println(date);
    }
}

 

마지막에 bfs 함수 실행 후 반복문으로 전체에 안 익은 토마토 ( 0 )이 있을 경우 -1을 출력하도록 함