이유's STUDY/알고리즘 문제풀이
7576_토마토
살아가는 이유_EU
2019. 10. 16. 21:07
728x90
반응형
토마토 케이스..!
처음에 DFS 로 풀려고 했는데 dfs 로 풀면 모든 정점을 다 돌 수가 없기 때문에 시간초과가가 났고...
정확한 기저사례, 반례를.. 잘 구하지 못해서 틀렸다..
BFS 로 다시 도전해서 풀어보기.
1. fist trial - dfs 로 도전해서 실패
|
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
|
#include <iostream>
using namespace std;
int N, M; //M : 가로 칸, N: 세로 칸
int count; //최소날짜 수
#define MAX 1000
int tomatoBox [MAX][MAX];
int checked [MAX][MAX];
int dx[] = { 0, 0, -1, 1};
int dy[] = { -1, 1, 0, 0};
void tomatoSearch(int x, int y)
{
//bfs 로직 확인해서
//토마토 <-- --> 상하좌우로직 으로 익은 것 옆의 주변부도 함께 익도록 설정.
// 1: 익은 토마토, 0: 아직 안익은 토마토 , -1:토마토가 없음.
//익은 토마토에 대해서만
checked[x][y] = 1;
//빠진 내용 : 기저사례
if(tomatoBox[x][y] == -1)
return;
if(tomatoBox[x][y] == 1)
if(checked[x][y] == 1 )
{
for(int i = 0; i< 4; i++)
{
int x_value = dx[i];
int y_value = dy[i];
if(checked[x + x_value][y + y_value] == 0) //여기서, x value, y value 를 더하는 것을 깜박했당.
tomatoSearch(x_value, y_value); //주변부 영향을 받아서 익는 과정
}
}
count++;
}
int main(void)
{
cin>>M>>N;
//토마노트들의 정보 input process
for(int i =0; i<M ; i++)
for(int j=0 ; j<N; j++)
scanf("%d",&tomatoBox[i][j]);
for(int i =0; i<M ; i++)
for(int j=0 ; j<N; j++)
if(tomatoBox[i][j] == 1) //익었을 경우에만 돌도록 설정.
tomatoSearch(i,j);
//main process
////예외처리과정 : 토마토가 모두 익은 상태 : 0, 토마토가 모두 익지 못하는 상황 :-1
/////아예 input 부터 받아서 처리
//<--- ---> 상하좌우를 확인하여, 옆에 있는 토마토가 있을 경우,
printf("%d", count);
return 0;
}
//유용한 사이트 : https://kyunstudio.tistory.com/118
|
cs |
2. 2nd trial -BFS
[ coming sooooon]
728x90
반응형