BOJ_7576 : 토마토

👉 문제링크

7576번: 토마토

---

---

🔸 문제 분석 🔸

•  n x m 크기의 창고에 토마토가 놓여있다.
  • 1 : 익은 토마토, 0 : 덜 익은 토마토, -1 : 빈 공간
  • 익은 토마토는 하루가 지날 때 마다 상하좌우 덜 익은 토마토를 익게 만든다.
  • 며칠이 지나야 토마토가 모두 익는지 출력한다. 모두 익지 못하면 -1 을 출력한다.
• 익은 토마토 주변에 익을 수 있는 토마토를 큐에 넣고 BFS을 실행한다.
  • 며칠이 지나는지 확인해야 하므로 익을 예정인 토마토들은 같은 큐에 넣지 않고, 임시 큐에 저장한다.
  • 초기 큐의 원소를 모두 꺼내면 임시큐를 확인해 원소가 있는지(앞으로 익을 토마토가 있는지) 확인한다.
  • 임시 큐의 원소를 초기 큐에 복사하고, 임시 큐는 비워버린다.
  • 임시 큐의 값이 없을 때 까지 반복한다.
• n x m 크기의 창고를 순회해 덜익은 토마토가 있는지 확인한다.
  • 있으면 -1을 출력한다.
  • 없으면 지나간 날짜를 출력한다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) {
        // 1) input
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        // 2) BFS
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        int day = 0;

        Queue<Pair> que = new LinkedList<>();
        Queue<Pair> temp = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {
                        int x = i + dx[k];
                        int y = j + dy[k];
                        if (0 <= x && x < n && 0 <= y && y < m && arr[x][y] == 0) {
                            temp.add(new Pair(x, y));
                        }
                    }
                }
            }
        }

        while (!temp.isEmpty()) {
            day++;
            que = temp;
            temp = new LinkedList<>();
            while (!que.isEmpty()) {
                Pair p = que.poll();
                arr[p.x][p.y] = 1;
                for (int i = 0; i < 4; i++) {
                    int x = p.x + dx[i];
                    int y = p.y + dy[i];
                    if (0 <= x && x < n && 0 <= y && y < m && arr[x][y] == 0) {
                        arr[x][y] = 1;
                        temp.add(new Pair(x, y));
                    }
                }
            }
        }

        boolean flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 0) {
                    flag = true;
                    break;
                }
            }
        }

        if (flag)
            System.out.println(-1);
        else
            System.out.println(day);
    }

    private static class Pair {
        int x, y;

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

🔸 코드 해석 🔸

• 좌표를 저장하기 위해 Pair클래스를 정의한다.
• 입력
  • n X m 크기 창고의 토마토 정보를 2차원 배열 arr에 저장한다.
• BFS
  • 2개의 큐 que, temp를 선언한다.
  • temp의 초기값을 넣어주기 위해, 먼저 arr를 순회한다.
    • 값이 1이면 상하좌우를 확인해 앞으로 익을 토마토가 있는지 확인한다.
    • 앞으로 익을 토마토의 좌표를 temp에 넣어준다.
  • 큐 temp가 빌 때까지 다음 계산을 반복한다.
    • 토마토가 모두 익을때 까지 필요한 날짜 day 변수를 +1 한다.
    • que에 temp를 복사하고, temp는 초기화한다.
    • 큐 que가 빌 때까지 계산을 반복한다.
      • que의 원소를 poll한다.
      • 해당 좌표의 값을 1로 변경한다. (temp의 초기화 때문이므로, day == 1에서만 실행 됨)
      • 상하좌우 4방향을 확인한다.
        • 상하좌우 인덱스가 창고 범위 내이며 값이 0이면,
          해당 좌표의 값을 1로 바꾸고 temp에 Pair객체 좌표를 추가한다.
• 출력
  • 창고 arr를 순회해 덜익은 토마토 (0)이 남아있는지 확인한다.
    • 남아있으면 -1, 없으면 day를 출력한다.

---

🔸 end 🔸

• 골드 5 치고는 비교적 쉬웠던 것 같다.
  • BFS에 익숙하고, 문제를 이전에 한 번 봤어서 그런듯 하다.
• 처음 큐 temp에 값을 초기화 할 때, BFS의 안쪽 while 처럼 좌표Pair객체를 넣으면서 값을 1로 바꿨더니 다음 for문에 영향이 갔다.
  • 그래서 BFS 안쪽 while문에 arr[p.x][p.y] = 1이라는 코드를 넣었는데, day가 1일때만 작동하기 때문에 좀 아쉬웠다.
  • 그렇다고 가장 안쪽 if문에서 1을 넣어주는걸 빼면 중복이 많아진다.
• 문제 파악 및 코딩 설계를 적어가며 풀이했지만, 별로 도움이 되지 않은 것 같아 아쉽다.
  • 아직 문제를 적어가며 푸는게 익숙하지 않은 것 같다.
• 반례도 만들어봤으면 좋았을텐데 뒷심이 좀 부족했다.
• 질의 응답에서 답변을 적어봤는데, 수정한 질문자분 코드가 2배 더 빨랐다...
  • https://www.acmicpc.net/board/view/109195