BOJ::문제풀이

7576 토마토

2영재 2018. 1. 6. 18:08

BOJ::7576 토마토


익은 토마토들의 위치에서 bfs를 통해 갱신해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    
    static final int SZ = 1000;
    static final int dx[]={0,0,1,-1};
    static final int dy[]={1,-1,0,0};
    
    static int n, m;
    static int map[][] = new int[SZ][SZ];
    static int d[][] = new int[SZ][SZ];
    
    static Queue<Node> q = new LinkedList();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        m = sc.nextInt();
        n = sc.nextInt();
        
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                map[i][j] = sc.nextInt();
            }
        }
        
        //D배열 -1로 초기화
        initD();
        
        boolean flag = false;
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                if(map[i][j] == 1){
                    q.add(new Node(i, j));
                    d[i][j] = 0;
                    flag = true;
                }
            }
        }
        
        
        //토마토가 하나도 없는 경우
        if(!flag) System.out.println(0);
        //토마토가 하나 이상 있는 경우
        else{
            bfs();
            
            //토마토가 모두 익었는지 확인.
            
            //안익은 토마토가 없으면
            if(isOK()){
                //d배열에 기록된 최대값 출력
                System.out.println(getResult());
            }
            //안익은 토마토가 있으면 -1 출력
            else{
                System.out.println(-1);
            }
        }
        
        //printD();
    }
    
    public static int getResult(){
        int res = 0;
        
        for(int i = 0 ; i < n ; i++){
            for(int  j = 0 ; j < m ; j++){
                if(map[i][j] == -1) continue;
                res = Math.max(res, d[i][j]);
            }
        }
        return res;
    }
    
    public static boolean isOK(){
        for(int i = 0 ; i < n; i++){
            for(int j = 0 ; j < m ; j++){
                if(map[i][j] == -1) continue;
                if(d[i][j] == -1) return false;
            }
        }
        return true;
    }
    
    public static void printD(){
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                System.out.print(d[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
    
    public static void initD(){
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                d[i][j] = -1;
            }
        }
    }
    
    public static void bfs(){
        while(!q.isEmpty()){
            int x = q.peek().x;
            int y = q.poll().y;
            
            for(int i = 0 ; i < 4; i++){
                int ax = x+dx[i];
                int ay = y+dy[i];
                
                if(ax>=0&&ay>=0&&ax<n&&ay<m){
                    if(map[ax][ay] == 0 && (d[ax][ay] == -1 || d[ax][ay] > d[x][y] + 1)){
                        d[ax][ay] = d[x][y] + 1;
                        q.add(new Node(ax, ay));
                    }
                }
            }
        }
    }
    
}
 
class Node{
    int x, y;
    Node (int x,int y){
        this.x = x;
        this.y = y;
    }
}
cs


저작자표시