공부공간

BOJ - 7569 ) 토마토 본문

알고리즘/완전탐색(BFS,DFS)

BOJ - 7569 ) 토마토

개발자가될수있을까? 2020. 1. 22. 21:43

https://www.acmicpc.net/problem/7569

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마

www.acmicpc.net

3차원 공간에서 토마토를 큐에 넣으면서 

 

인접한 토마토에 영향을 미치는지 여부를 판단하는 문제이다.

 

예외로 입력을 받았을때에, 0이 있는지 확인하는 메소드를 만들어 체크해주었다.

 

 

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
import java.util.Scanner;
class coordi{
    int x;
    int y;
    int z;
    int time;
    coordi(int x ,int y, int z , int time){
        this.x =x;
        this.y =y;
        this.z =z;
        this.time = time;
    }
}
public class Main {
    static int dx[] = {0,0,-1,+1,0,0};
    static int dy[] = {+1,-1,0,0,0,0};
    static int dz[] = {0,0,0,0,+1,-1};
    static int count =0;
    static int x,y,z;
    static int map[][][];
    public static boolean judge() {
        
        for(int h = 0 ; h < z ; h++) {
            for(int n = 0 ; n < y; n++) {
                for(int m = 0 ; m < x ; m++) {
                    if(map[h][n][m]== 0) {
                        return false;            
                    }
                }    
            }        
        }
        return true;
    }
    
    
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        Queue<coordi> Q = new LinkedList<coordi>();
        
         x = sc.nextInt();
         y = sc.nextInt();
         z = sc.nextInt();
        map = new int[z][y][x];
        boolean visit[][][] = new boolean[z][y][x];
        for(int h = 0 ; h < z ; h++) {
            for(int n = 0 ; n < y; n++) {
                for(int m = 0 ; m < x ; m++) {
                    map[h][n][m] = sc.nextInt();
                    if(map[h][n][m]== -1) visit[h][n][m] =true;
                    if(map[h][n][m]== 1) Q.add(new coordi(m,n,h,0));
                }    
            }        
        }
        if(judge()) {
            System.out.println(0);
        }
        else {
            while(!Q.isEmpty()) {
                
                coordi now = Q.poll();
 
                count = count > now.time ?count : now.time;
                for(int index = 0 ; index <6 ; index++) {
                    int nx = now.x + dx[index];
                    int ny = now.y + dy[index];
                    int nz = now.z + dz[index];
                        
                    if(nx >= 0 && ny >= 0 && nz >= 0 && nx < x && ny < y && nz < z && !visit[nz][ny][nx]) {
                        if(map[nz][ny][nx] == 0) {
                            map[nz][ny][nx] = 1;
                            visit[nz][ny][nx] = true;
                            Q.add(new coordi(nx, ny, nz,now.time+1));
                        }
                    }
                }
            }
            
//            for(int h = 0 ; h < z ; h++) {
//                for(int n = 0 ; n < y; n++) {
//                    for(int m = 0 ; m < x ; m++) {
//                        if( map[h][n][m] == 1 && !visit[h][n][m]) {
//                            
//                    
//                        }
//                    }    
//                }        
//            }
//            
            if(judge()) {
                System.out.println(count);
            }
            else {
                System.out.println(-1);
            }
 
        }
        
        
    }
    
 
}
 
  

'알고리즘 > 완전탐색(BFS,DFS)' 카테고리의 다른 글

BOJ - 2644 ) 촌수계산  (0) 2020.01.28
BOJ - 6603 ) 로또 JAVA  (0) 2020.01.23
BOJ - 1002 ) 적록색약 JAVA  (0) 2020.01.20
BOJ -1697 ) 숨바꼭질  (0) 2020.01.19
BOJ - 7576 ) 토마토  (0) 2020.01.19
'알고리즘/완전탐색(BFS,DFS)' Related Articles more
Comments