(코테) 백준_7576_토마토 BFS

 

 

 

 

 

내가 최초 제안한 답.

import java.util.*;
import java.io.*;

public class Main {
    static int[][] map;
    static boolean[][] visted;
    static int m, n;
    static int[] x = {-1, 1, 0, 0};
    static int[] y = {0, 0, -1, 1};
    static int count;
    static boolean flag = true;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visted = new boolean[n][m];

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

        while (flag) {
            // ✅ 전역 flag를 false로 초기화
            flag = false;
            bfs2(0, 0);
        }

        // ✅ 모든 토마토가 익었는지 확인
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    System.out.println(-1); // 익지 않은 토마토 존재
                    return;
                }
            }
        }

        System.out.println(count);
    }

    public static void bfs2(int i, int j) {
    Queue<int[]> q = new LinkedList<>();

    for (int a = 0; a < n; a++) {
        for (int b = 0; b < m; b++) {
            if (map[a][b] == 1 && !visted[a][b]) {
                visted[a][b] = true;

                for (int f = 0; f < 4; f++) {
                    int nx = a + x[f];
                    int ny = b + y[f];

                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

                    if (map[nx][ny] == 0) {
                        map[nx][ny] = 1;              // ✅ 중복 처리 방지
                        q.offer(new int[] {nx, ny});
                        flag = true;
                    }
                }
            }
        }
    }

    if (flag) count++;
}

}

 

 

 

 

 

개선된 답

import java.util.*;
import java.io.*;

public class Main {
    static int[][] map;
    static int m, n;
    static int[] dx = {-1, 1, 0, 0};  // 상하좌우 x 이동
    static int[] dy = {0, 0, -1, 1};  // 상하좌우 y 이동

    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());  // 행
        map = new int[n][m];

        // ✅ 올바르게 한 줄씩 읽어서 파싱
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bfs();

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    System.out.println(-1);  // 익지 않은 토마토가 남아있음
                    return;
                }
                result = Math.max(result, map[i][j]);
            }
        }

        System.out.println(result - 1);  // 처음 익은 상태가 1이므로 하루 수 = -1
    }

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();

        // ✅ 처음에 익은 토마토 모두 큐에 넣기 (다중 시작점 BFS)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1) {
                    q.offer(new int[]{i, j});
                }
            }
        }

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int cx = now[0];
            int cy = now[1];

            for (int d = 0; d < 4; d++) {
                int nx = cx + dx[d];
                int ny = cy + dy[d];

                // ✅ 범위 초과 방지
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

                // ✅ 안 익은 토마토만 처리
                if (map[nx][ny] == 0) {
                    map[nx][ny] = map[cx][cy] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
    }
}

 

 

회고 

 

내 코드 부족한 점 

1.  불필요한 전역 visited 생성 활용도 하지 않으면서

2. dfs 와 같이 재귀로 호출하였다. 범위가 넓어 스텍오버플로우 위험. 

3. 익지 않은 토마토 결과값 명시 x  -> 문제에서 마지막에 익지 않은 토마토 존재시 -1 표기하라고 했는데 못했음.

4. 범위 초과 코드 기억해내지 못함. 사각형 벗어났을 때  ex) if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

 

 

 

문제 핵심포인트

1. 처음 큐에 다익은 토마토를 넣기   + 익은 토마토만 큐에 담는다!!! 중요!!! 그래서 이중 for문이 아닌 익힐때마다 큐에 넣어  상하좌우 탐색시킴 여기서 안익은토마토(0) 발견시  일수+1 값 map에 넣어줌

2. 토마토 익으면(1이 되면) map에 표기시 +1을 넣어줘  총 일수 계산  -> 그리고 큐에 추가하여 탐지시킴.

 

 

 

 

 

* 나는 이중 for문으로 재귀하여 토마토 익히는 시간을 count 하려고 시도하였다. 

좋은 방법은 아니였다.

이 문제를 통해 bfs 큐에 대해 확실히 파악 할 수 있는 계기가 된거 같다.

비록 시간은 많이 가져갔으나....