Completion over Perfection

백준 7576 - 토마토 BFS (JAVA) 본문

앨고리듬 알고리즘

백준 7576 - 토마토 BFS (JAVA)

난차차 2020. 11. 4. 21:28
반응형

백준 7576 - 토마토 BFS (JAVA)

 

 

 

www.acmicpc.net/problem/7576

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

 

전형적인 BFS 문제입니다.

큐 Queue를 연습하기에 좋습니다.

 

저는 초보라서 Scanner와 int 배열만을 이용하여 풀었습니다.

참고만 해주세요~

 

 

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
import java.util.*;
 
 
 
public class Main {
 
 
 
  static int N,M,result;
 
  static int map [][];
 
  static int dx[] = {1,0,-1,0};
 
  static int dy[] = {0,1,0,-1};
 
  
 
  public static void main(String[] args) {
 
 
 
    Scanner sc = new Scanner(System.in);
 
    
 
    N = sc.nextInt(); //6
 
    M = sc.nextInt(); //4
 
    
 
    map = new int[M+2][N+2];
 
        
 
    int num_one = 0;
 
    int num_zero = 0;
 
    int num_negone = 0;
 
    
 
    result = 0;
 
    
 
    Queue<Integer> q = new LinkedList<Integer>();
 
        
 
    for (int i=1; i<=M; i++) { //4
 
      for (int j=1; j<=N; j++) { //6
 
        map[i][j] = sc.nextInt();
 
        if (map[i][j]==1) { // 4 6 == 1
 
          num_one++;
 
          q.add(i);
 
          q.add(j);
 
          q.add(1);
 
        }else if(map[i][j]==-1) {
 
          num_negone++;
 
        }else {
 
          num_zero++;
 
        }
 
      }
 
    }
 
    
 
    if (num_one == N*M ) {
 
      System.out.println("1");
 
      return;
 
    }else if (num_negone == N*M){
 
      System.out.println("-1");
 
      return;
 
    } else if(num_zero==0) {
 
      System.out.println("0");
 
      return;
 
    }
 
 
 
    //bfs 시작
 
    
 
    while(!q.isEmpty()) {
 
      int x_out = q.poll(); // x좌표 꺼냄
 
      int y_out = q.poll(); // y좌표 꺼냄
 
      int day = q.poll();
 
      int x_temp;
 
      int y_temp;
 
      for(int i=0; i<4; i++) {
 
        x_temp = x_out + dx[i]; // 5 4
 
        y_temp = y_out + dy[i]; // 6 7    
 
        if(x_temp<=M && y_temp<=N && x_temp>0 && y_temp>0) {
 
          if(map[x_temp][y_temp]>0) { // 0보다 큰, 0이 아닌 다른 수가 들어가 있는 경우 처리
 
 
 
            if(day+1<map[x_temp][y_temp]) { //day+1의 값이 진행하려는 곳의 값보다 작은 경우
 
              map[x_temp][y_temp] = day+1;
 
              q.add(x_temp);
 
              q.add(y_temp);
 
              q.add(day+1);
 
            }    
 
          }else if(map[x_temp][y_temp]==0) {
 
            map[x_temp][y_temp] = day+1;
 
            q.add(x_temp);
 
            q.add(y_temp);
 
            q.add(day+1);
 
          }
 
        }   
 
      } 
 
    }
 
    for (int i=1; i<=M; i++) { // 진행안된 곳이 있는지 확인
 
      for (int j=1; j<=N; j++) {
 
        if(map[i][j] == 0) {
 
          System.out.println("-1"); // 있다면 -1 리턴
 
          return;
 
        }else {
 
          result = Math.max(result, map[i][j]);
 
        }
 
      }
 
    }
 
    System.out.println(result-1);
 
  }
 
}
 cs
반응형
저작자표시

'앨고리듬 알고리즘' 카테고리의 다른 글

백준 9019 - DSLR (JAVA, 자바)  (0) 2020.11.14
백준 2178 - 미로탐색 (JAVA 자바)  (0) 2020.11.11
백준 1260 - DFS와 BFS (JAVA)  (0) 2020.11.10
백준 13866 - 팀 나누기 (JAVA)  (2) 2020.11.07
백준 1012 - 유기농배추 DFS (JAVA)  (0) 2020.11.06
'앨고리듬 알고리즘' Related Articles more
Comments