728x90

 0. [c++] 백준


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


 1. 풀이


1) 처음에는 DFS의 방식으로 문제를 풀어봤었다. 기본 예제문제들은 간단하게 풀어낼 수 있었지만, 입력의 크기가 커질 수록 문제를 풀기위해 반복을 하는 횟수가 N^2정도로 크게 증가를 하는 것을 볼 수 있었다.


2) 이를 해결하기 위해서 BFS의 방식을 선택해서 풀어보았는데, 넓이 우선 탐색이라는 말이 무색하지 않게 낮은 level을 먼저 탐색하는 형태를 취해서 문제를 풀어나가다보니 반복을 줄이면서 더 빠른시간에 문제를 해결 할 수 있었다.

이때, 해결하는 순서를 만들어 주기 위해서 queue라는 별도의 줄을 만들어서 따로 유지해주었다.



밑에 소스코드는 DFS와 BFS 두가지 형태 모두 구현해놓았는데, DFS는 주석으로 처리해놓았다.

두개의 해결 차이가 궁금하시다면 테스트 해보는 것도 나쁘지 않을 것이라고 생각한다.



 2. 소스코드


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
#include<iostream>
#include<queue>
 
using namespace std;
 
int tomatoBox[1003][1003];
int M, N, MAX;
int dirX[4] = { 0, 0, 1, -1 };
int dirY[4] = { 1, -1, 0, 0 };
queue<pair<int, int> > findHere;
 
 
int Max(int a, int b) {
    return a > b ? a : b;
}
 
//void find() {
//    int t =M*N;
//    while(t--)
//        for (int y = 1; y <= N; y++)
//            for (int x = 1; x <= M; x++) {
//                if (tomatoBox[y][x] > 0) {
//                    for (int i = 0; i < 4; i++) {
//                        if (tomatoBox[y + dirY[i]][x + dirX[i]] != 0)
//                            continue;
//                        tomatoBox[y + dirY[i]][x + dirX[i]] = tomatoBox[y][x] + 1;
//                    }
//                }
//
//            }
//}
 
////내 일자보다 작은 일이라면 바로 return을 해버린다. 이미 거기서 발생되는 것들은 이미 다 탐색을 완료했기 때문이다.
//void DFS(int hereY, int hereX, int day=1) {
//    //기저 사례 : 토마토가 없는 곳이라면 바로 return으로 탐색을 종료한다.
//    if (tomatoBox[hereY][hereX] == -1)
//        return;
//    //기저 사례 : 지금 날짜보다 더 작은 날짜가 저장되어 있다면 탐색을 종료한다.
//    if (tomatoBox[hereY][hereX] < day && tomatoBox[hereY][hereX] != 0)
//        return;
//
//    //기저 사례에 걸리지 않은 토마토는 지금 날짜를 달아준다.(익는데까지 가장 최소의 시간)
//    tomatoBox[hereY][hereX] = day;
//    //Count++;
//    //4방향 탐색을 들어가자
//    for (int i = 0; i < 4; i++) {
//        int nextY = hereY + dirY[i], nextX = hereX + dirX[i];
//        //범위를 넘지 않도록 조건을 넣어준다.
//        if (nextY < N&&nextX < M && nextY >= 0 && nextX >= 0)
//            DFS(nextY, nextX, day + 1);
//    }    
//}
 
void BFS(int hereY, int hereX) {
    //4방향 탐색을 들어가자
    for (int i = 0; i < 4; i++) {
        int nextY = hereY + dirY[i], nextX = hereX + dirX[i];
        //범위를 넘지 않도록 조건을 넣어준다.
        if (nextY < N&&nextX < M && nextY >= 0 && nextX >= 0) {
            if (tomatoBox[nextY][nextX] == 0) {
                tomatoBox[nextY][nextX] = tomatoBox[hereY][hereX] + 1;
                findHere.push({ nextY, nextX });
            }
        }
            
    }    
}
 
int main() {
    cin >> M >> N;
    for (int y = 0; y < N; y++)
        for (int x = 0; x < M; x++) {
            cin >> tomatoBox[y][x];
            if (tomatoBox[y][x] == 1)
                findHere.push({ y,x });
        }
 
    //토마토가 들어있는 상자에서 모두 탐색을 하자! Yes!
    /*for (int y = 0; y < N; y++)
        for (int x = 0; x < M; x++)
            if(tomatoBox[y][x] == 1)
                DFS(y,x);*/
 
    //for (int i = 0; i < hereIsRoot.size(); i++)
    //    DFS(hereIsRoot[i].first, hereIsRoot[i].second);
 
 
    while (!findHere.empty()) {
        BFS(findHere.front().first, findHere.front().second);
        findHere.pop();
    }
 
 
    //토마토 상자 출력
    //for (int y = 0; y < N; y++) {
    //    for (int x = 0; x < M; x++)
    //        cout << tomatoBox[y][x] << " ";
    //    cout << endl;
    //}
 
 
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            //만일 익어있지 않은 토마토가 있다면 -1을 출력한다.
            if (tomatoBox[y][x] == 0) {
                cout << -1;
                return 0;
            }
            MAX = Max(MAX, tomatoBox[y][x]);
        }
    }
 
 
    cout << MAX - 1;
    return 0;
}
cs


 3. 참고


BFS, DFS에 대한 자세한 강의?

https://blog.encrypted.gg/729



질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!


저작자표시

'<백준> > |c++| normal' 카테고리의 다른 글

[c++] 백준 2667 - 단지번호붙이기  (0) 2019.05.10
[c++] 백준 7569 - 토마토(BFS)  (0) 2019.05.10
|C++| 백준 1289 - 트리의 가중치(깊이 우선 탐색,DFS)  (0) 2019.05.10
[c++] 백준 1693 - 트리 색칠하기  (0) 2019.05.09
[c++] 백준 1991 - 트리 순회  (0) 2019.05.05

+ Recent posts

티스토리툴바