[백준] 7576번: 토마토
그래프 탐색 문제이다.
처음 생각했던 접근방식
상하좌우로 토마토가 익기 때문에, BFS를 사용하여 문제를 해결해야겠다는 생각이 우선적으로 들었다. 그리고 다른 쉬운 그래프 문제와는
다르게 처음 익은 토마토가 여러개가 존재할 수 있기 때문에, 큐에 토마토 위치를 다 넣어주고 순회하면 되었다.
또한, 순회하면서 총 토마토 개수를 세며, 기존 상자에 들어갈 수 있는 토마토의 개수를 비교하여 조건에 맞게 -1, 0, 1을 출력할 수 있다.
그러나 구현하는데 있어서 순간 막혔던 부분은 "토마토가 여러개가 있을 경우 다 익는 데 최소로 걸리는 시간을 어떻게 구현할 것인가"였다.
처음 생각했던 방식은 단순하게 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
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int x, y;
int box[1000][1000];
int countDays[1000][1000];
bool visited[1000][1000];
vector<pair<int,int>> tomatos;
bool check(int yq, int xq){
if(yq<0 || yq>=y || xq<0 || xq>=x) return false;
if(visited[yq][xq] == true) return false;
if(box[yq][xq] == -1 || box[yq][xq] == 1) return false;
return true;
}
int bfs(){
int count = 0;
queue<pair<int,int>> q;
for(auto tomato: tomatos){
q.push(tomato);
visited[tomato.first][tomato.second] = true;
}
while(!q.empty()){
int xq = q.front().second;
int yq = q.front().first;
q.pop();
visited[yq][xq] = true;
count++;
if(check(yq,xq-1)){
q.push(make_pair(yq,xq-1));
visited[yq][xq-1] = true;
countDays[yq][xq-1] = countDays[yq][xq] + 1;
}
if(check(yq,xq+1)){
q.push(make_pair(yq,xq+1));
visited[yq][xq+1] = true;
countDays[yq][xq+1] = countDays[yq][xq] + 1;
}
if(check(yq-1,xq)){
q.push(make_pair(yq-1,xq));
visited[yq-1][xq] = true;
countDays[yq-1][xq] = countDays[yq][xq] + 1;
}
if(check(yq+1,xq)){
q.push(make_pair(yq+1,xq));
visited[yq+1][xq] = true;
countDays[yq+1][xq] = countDays[yq][xq] + 1;
}
}
return count;
}
int main(){
cin >> x >> y;
int minus = 0;
memset(visited, false, sizeof(visited));
for(int i=0; i<y; i++){
for(int j=0; j<x; j++){
cin >> box[i][j];
countDays[i][j] = box[i][j];
if(box[i][j] == 1) tomatos.push_back(make_pair(i,j));
if(box[i][j] == -1) minus++;
}
}
if(bfs() != (x*y-minus)){
cout << -1;
return 0;
}
int max = 0;
for(int i=0; i<y; i++){
for(int j=0; j<x; j++){
if(countDays[i][j] > max){
max = countDays[i][j];
}
}
}
cout << max-1;
return 0;
}
|
cs |
해결책은 새로운 2차원배열(countDays)을 두고 순회할 때마다 이전 칸의 countDays+1을 넣는것이다.
그렇게하면, 굳이 기존에 만들었던 알고리즘을 복잡하게 개조할 필요 없이 나중에 countDays의 최대값을 구하면
그것이 토마토가 다 익는데 걸리는 최소시간이기 때문이다. 다만, 1부터 시작했으므로 총 기간은 max-1이 된다.
평소에 알고리즘 문제를 풀 때 기존 알고리즘에 간단한 변수만으로 복잡하게 구현하려는 좋지 않은 습관이 있다는 것을 인지했다.
쉽게 표시할 수 있도록 새로운 자료구조를 추가하고, 조금 더 논리적이고 직관적으로 프로그래밍하기 쉬운 방법을 찾아갈 수 있도록 더욱 노력해야겠다.