문제 출처: https://www.acmicpc.net/problem/2178



참고

BFS(Breadth-First Search): http://qlyh8.tistory.com/30?category=731166

BFS 문제: http://qlyh8.tistory.com/31?category=731166


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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    private static int N, M;
    private static int[][] miro;
    private static boolean[][] visit;
    private static int[] dirX = {0, 1, 0, -1}; // X 좌표
    private static int[] dirY = {1, 0, -1, 0}; // Y 좌표
 
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        miro = new int[N][M];
        visit = new boolean[N][M];
 
        for(int i=0 ; i<N ; i++){
            String inputLine = reader.readLine();
            for(int j=0 ; j<M ; j++){
                miro[i][j] = inputLine.charAt(j)-'0'; // 붙어서 입력으로 주어짐
            }
        }
 
        bfs(new Position(0, 0, 1)); // (0,0) 부터 탐색, 1 카운트
    }
 
    private static void bfs(Position position){
        Queue<Position> queue = new LinkedList<>();
        queue.offer(position); // 방문한 좌표를 큐에 넣음
        visit[position.getN()][position.getM()] = true; // visit 갱신
 
        while(!queue.isEmpty()){
            Position front = queue.poll(); // 방문한 좌표
 
            if(front.getN() == N-1 && front.getM() == M-1){ // 도착 위치일 경우 끝냄
                System.out.println(front.count);
                return;
            }
 
            for(int i=0 ; i<4 ; i++){ // 방문한 좌표의 주변 4방향 탐색
                int newN = front.getN() + dirY[i];
                int newM = front.getM() + dirX[i];
 
                if((0 <= newN && newN < N) && (0 <= newM && newM < M)){ // 미로 범위 내
                    if(miro[newN][newM] == 1 && !visit[newN][newM]){ // 이동할 수 있는 칸이고 방문하지 않았을 경우
                        visit[newN][newM] = true; // vist 갱신
                        queue.offer(new Position(newN, newM, front.getCount()+1)); // 큐에 넣음
                    }
                }
            }
        }
    }
 
    public static class Position{
        int n, m, count;
 
        Position(int n, int m, int count) {
            this.n = n;
            this.m = m;
            this.count = count;
        }
 
        int getN(){return n;}
 
        int getM(){return m;}
 
        int getCount(){return count;}
    }
}
cs



저작자표시

'Algorithm' 카테고리의 다른 글

백준 2667번: 단지번호붙이기  (0) 2018.10.26
백준 2606번: 바이러스  (0) 2018.10.26
백준 7569번: 토마토  (0) 2018.10.26
백준 7576번: 토마토  (0) 2018.10.26
백준 11866번: 조세퍼스 문제 0  (0) 2018.10.25

문제 출처: https://www.acmicpc.net/problem/7569



참고 문제) 토마토: http://qlyh8.tistory.com/155?category=731166


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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    private static int M, N, H;
    private static int[][][] box;
    private static int[] dirX = {0, 1, 0, -1, 0, 0}; // X 좌표
    private static int[] dirY = {1, 0, -1, 0, 0, 0}; // Y 좌표
    private static int[] dirZ = {0, 0, 0, 0, 1, -1}; // Z 좌표
 
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        H = Integer.parseInt(input[2]);
        box = new int[H][N][M];
 
        for(int i=0 ; i<H ; i++){
            for(int j=0 ; j<N ; j++){
                StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                for(int k=0 ; k<M ; k++) {
                    box[i][j][k] = Integer.parseInt(tokenizer.nextToken());
                }
            }
        }
 
        Queue<Tomato> queue = new LinkedList<>();
        for(int i=0 ; i<H ; i++){
            for(int j=0 ; j<N ; j++) {
                for(int k=0 ; k<M ; k++){
                    if (box[i][j][k] == 1) {
                        queue.offer(new Tomato(i, j, k));
                    }
                }
            }
        }
 
        bfs(queue);
 
        int count = 0;
        for(int i=0 ; i<H ; i++){
            for(int j=0 ; j<N ; j++){
                for(int k=0 ; k<M ; k++) {
                    if (box[i][j][k] == 0) {
                        System.out.println("-1");
                        return;
                    }
                    if (count < box[i][j][k]) {
                        count = box[i][j][k];
                    }
                }
            }
        }
 
        System.out.println(count-1);
    }
 
    private static void bfs(Queue<Tomato> queue){
        while(!queue.isEmpty()){
            Tomato front = queue.peek();
            queue.poll();
 
            for(int i=0 ; i<6 ; i++){ // 익은 토마토 주변 6방향
                int newH = front.getH() + dirZ[i];
                int newN = front.getN() + dirY[i];
                int newM = front.getM() + dirX[i];
 
                if((0 <= newH && newH < H) && (0 <= newN && newN < N) && (0 <= newM && newM < M)){
                    if(box[newH][newN][newM] == 0){
                        box[newH][newN][newM] += box[front.getH()][front.getN()][front.getM()] + 1;
                        queue.offer(new Tomato(newH, newN, newM));
                    }
                }
            }
        }
    }
 
    public static class Tomato{
        int h, n, m;
 
        Tomato(int h, int n, int m) {
            this.h = h;
            this.n = n;
            this.m = m;
        }
 
        int getH(){return h;}
 
        int getN(){return n;}
 
        int getM(){return m;}
    }
}
cs


저작자표시

'Algorithm' 카테고리의 다른 글

백준 2606번: 바이러스  (0) 2018.10.26
백준 2178번: 미로 탐색  (0) 2018.10.26
백준 7576번: 토마토  (0) 2018.10.26
백준 11866번: 조세퍼스 문제 0  (0) 2018.10.25
백준 1966번: 프린터 큐  (0) 2018.10.25

문제 출처: https://www.acmicpc.net/problem/7576



참고

BFS(Breadth-First Search): http://qlyh8.tistory.com/30?category=731166

BFS 문제: http://qlyh8.tistory.com/31?category=731166


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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    private static int M, N;
    private static int[][] box;
    private static int[] dirX = {0, 1, 0, -1};
    private static int[] dirY = {1, 0, -1, 0};
 
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        box = new int[N][M];
 
        for(int i=0 ; i<N ; i++){
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for(int j=0 ; j<M ; j++){
                box[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }
 
        Queue<Tomato> queue = new LinkedList<>(); 
        for(int i=0 ; i<N ; i++){
            for(int j=0 ; j<M ; j++) {
                if (box[i][j] == 1) {
                    queue.offer(new Tomato(i, j));  // 처음에 익은 토마토를 모두 큐에 넣음
                }
            }
        }
 
        bfs(queue); // 안익은 토마토를 익은 토마토로 
 
        int count = 0;
        for(int i=0 ; i<N ; i++){
            for(int j=0 ; j<M ; j++){
                if(box[i][j] == 0){  // 모든 토마토가 익지 못함
                    System.out.println("-1"); 
                    return;
                }
                if(count < box[i][j]){ // 모든 토마토가 익을 때의 날짜
                    count = box[i][j];
                }
            }
        }
 
        System.out.println(count-1);
    }
 
    private static void bfs(Queue<Tomato> queue){
        while(!queue.isEmpty()){
            Tomato front = queue.peek();
            queue.poll(); // 익은 토마토 위치
 
            for(int k=0 ; k<4 ; k++){
                int newN = front.getN() + dirY[k]; // 익은 토마토 주변 4방향 Y
                int newM = front.getM() + dirX[k]; // 익은 토마토 주변 4방향 X
 
                if((0 <= newN && newN < N) && (0 <= newM && newM < M)){ // 상자 범위 내
                    if(box[newN][newM] == 0){ // 안익은 토마토라면
                        box[newN][newM] += box[front.getN()][front.getM()] + 1;  // 익은 토마토로 만듬, 날짜 갱신
                        queue.offer(new Tomato(newN, newM)); // 익었으므로 큐에 넣음
                    }
                }
            }
        }
    }
 
    public static class Tomato{
        int n, m;
 
        Tomato(int n, int m) {
            this.n = n;
            this.m = m;
        }
 
        int getN(){return n;}
 
        int getM(){return m;}
    }
}
cs


저작자표시

'Algorithm' 카테고리의 다른 글

백준 2178번: 미로 탐색  (0) 2018.10.26
백준 7569번: 토마토  (0) 2018.10.26
백준 11866번: 조세퍼스 문제 0  (0) 2018.10.25
백준 1966번: 프린터 큐  (0) 2018.10.25
백준 10845번: 큐  (0) 2018.10.25

+ Recent posts

티스토리툴바