[백준] 7576. 토마토

7576. 토마토

7576번: 토마토

 

• 내 풀이-
  • 첫 풀이: 메모리 초과 error
  • 익은 토마토들이 나오면 bfs()를 돌렸음
    • -> 이부분 틀림
    • 이렇게 하면 처음 걸린 bfs()에서 이미 처리가 끝나버려서 다른 토마토들을 실행할 수 없다.

package day19;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

//메모리초과
public class JUN7576_ParkSomin_error {
    static int R,C, min;
    static int[][] map;
    static int[][] visited;

    static int[] dr={-1,1,0,0};
    static int[] dc={0,0,-1,1};

    static class Pair{
        int r;
        int c;

        public Pair(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        //상자 가로 R, 세로 C
        C=Integer.parseInt(st.nextToken());
        R=Integer.parseInt(st.nextToken());

        visited=new int[R][C];
        //Arrays.fill은 1차원 배열에서 가능
        for (int i = 0; i < visited.length; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }

        min=Integer.MIN_VALUE;

        map=new int[R][C];
        //익은 토마토 1, 익지않은 토마토 0, 빈공간 -1
        for (int i = 0; i < R; i++) {
            st=new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j]==1){
                    bfs(i,j);
                }
            }
        }

        if(min!=-1){
            check();
        }
        System.out.println(min);

    }

    private static void bfs(int r, int c){
        //1인 r,c에서 출발
        Queue<Pair> q=new ArrayDeque<>();
        visited[r][c]=0;
        q.offer(new Pair(r,c));

        while(!q.isEmpty()){
            Pair p=q.poll();

            for (int i = 0; i < 4; i++) {
                int nr=p.r+dr[i];
                int nc=p.c+ dc[i];
                if(nr>=0 && nr<R && nc>=0 && nc<C
                                && map[nr][nc]==0){
                    //들렸던 곳도 또 들리면서 작은값으로
                    visited[nr][nc]=visited[nr][nc]>visited[p.r][p.c]+1 ? visited[p.r][p.c]+1:visited[nr][nc] ;
                    q.offer(new Pair(nr,nc));
                }
            }
        }
        //토마토가 모두 익지 못하는 상황
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j]==1){
                    min=-1;
                    return;
                }
            }
        }
    }

    private static int check(){
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(visited[i][j]>=1){
                    min=min>visited[i][j] ? visited[i][j] : min;
                }
            }
        }
        return min;
    }
}

 

 

 

 

 

• 다른 사람 풀이
  • 익은 토마토들이 동시에 돌아야하기 때문에 Queue에 바로 넣은 후에
    • bfs()는 한 번 실행
  • 최단, 최소 -> BFS

package day19;

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

public class JUN7576_ParkSomin {
    static int R,C, answer;
    static int[][] map;
    static int[][] visited;

    static int[] dr={-1,1,0,0};
    static int[] dc={0,0,-1,1};
    static Queue<Pair> q;

    static class Pair{
        int r;
        int c;
        int day;

        public Pair(int r, int c, int day) {
            this.r = r;
            this.c = c;
            this.day=day;
        }
    }

    //익은 토마토 여러개가 동시에 돌아야하기 때문에 바로 큐에 넣어야함
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        //상자 가로 R, 세로 C
        C=Integer.parseInt(st.nextToken());
        R=Integer.parseInt(st.nextToken());

        visited=new int[R][C];

        answer=0;

        map=new int[R][C];
        //익은 토마토 1, 익지않은 토마토 0, 빈공간 -1
        q= new LinkedList<>();

        for (int i = 0; i < R; i++) {
            st=new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
                if(map[i][j]==1){
                    //익은 토마토 여러개가 동시에 돌아야하기 때문에 바로 큐에 넣어야함
                    q.offer(new Pair(i,j,0));
                }
            }
        }

        System.out.println(bfs());

    }

    private static int bfs(){
        answer=0;

        while(!q.isEmpty()){
            Pair p=q.poll();
            int x=p.r;
            int y=p.c;
            int d=p.day;

            for (int i = 0; i < 4; i++) {
                int nr=x+dr[i];
                int nc=y+ dc[i];
                if(nr>=0 && nr<R && nc>=0 && nc<C && map[nr][nc]==0){

                    map[nr][nc]=1;
                    answer=d+1;
                    q.offer(new Pair(nr,nc, d+1));
                }
            }
        }
        //토마토가 모두 익지 못하는 상황
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j]==0){
                    return -1;
                }
            }
        }
        return answer;
    }

}