문제 유형
격자 안에 토마토가 주어지는데, 익은 토마토의 동서남북으로 인접한 토마토는 하루만에 익는다.
모든 토마토가 익게되는최소일수를 구하시오
필요 핵심 자료구조
TomatoPoint 클래스 // (Q에 x, y좌표를 담기 위한 객체),
Queue<new TomatoPoint> // (n개 만큼 자연수 입력),
int L // (현재 레벨),
int cnt // (익지 않은 토마토 체크 변수),
int nx, ny // (다음 좌표를 담는 변수),
DFS() 메서드 // 핵심 로직,
핵심 문제 해석
첫째 역시나 최소라는 단어에 집중하자.
최소, 최단이 들어간 경우 BFS 문제일 가능성이 있다.
둘째 동서남북이 들어갔으니 좌표 이동 문제라고 파악할 수 있고,
동서남북으로 이동하는 배열을 선언해줘야할 것이다.
또한, 뻗어나갈 수 있는 방향의 조건이 주어지므로
그 조건에 맞도록 조건문을 작성해줘야할 것이다.
문제 풀이 과정
평소에는 코드를 작성하면서 알고리즘을 풀었었는데,
이 코드가 명확한지 명확하지 않은지 알 수가 없으니 구현할 수가 없었다.
그래서,
알고리즘 흐름을 먼저 그려보고 결과를 도출한 뒤에
코드를 구현했더니
10분도 안걸려서 코드를 작성할 수 있었다.
아래는 내가 그린 알고리즘 흐름이다.
L(레벨)이 곧 일수이므로,
4일이 걸린다는걸 확인할 수 있었다.
코드 구현은 미로최단거리탐색과 비슷하다.
미로최단거리탐색문제 링크 : https://velog.io/@ni0307/BFS-%EB%AF%B8%EB%A1%9C%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC%ED%83%90%EC%83%89
핵심 코드
public int BFS(){
Queue<TomatoPoint> Q = new LinkedList<>();
int L = 0;
int cnt = 0;
//arr[i][j]에 0이 존재하는지 확인한다. 만약 존재한다면 cnt를 증가시킨다.
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(arr[i][j] == 0){
cnt++;
break;
}
}
if(cnt != 0) break;
}
// 처음부터 모든 토마토가 익은 경우 0을 반환
if(cnt == 0) return 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(arr[i][j] == 1){
Q.offer(new TomatoPoint(i, j));
}
}
}
while(!Q.isEmpty()){
int len = Q.size();
for(int i = 0; i < len; i++){
TomatoPoint tomatoPoint = Q.poll();
for(int j = 0; j < 4; j++){
int nx = tomatoPoint.x+dx[j];
int ny = tomatoPoint.y+dy[j];
if(nx >= 0 && ny >=0 && nx < m && ny < n && arr[nx][ny] == 0){
arr[nx][ny] = 1;
Q.offer(new TomatoPoint(nx, ny));
}
}
}
L++;
}
// 모든 토마도가 익지 않은 경우 return -1
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(arr[i][j] == 0){
return -1;
}
}
}
return L-1;
}
개선된 점
첫번째 알고리즘과 자료구조를 그려놓고
알고리즘 흐름을 파악한 뒤에
결론을 도출하고
코드를 작성했다.
두번째 최대한 많은 상상력을 동원했다.
논리적인 사고는 상상력에서 온다고 생각한다.
따라서, 상상력을 최대한 발휘하면 높은 집중 상태를 유지할 수 있게되고
더 명확한 결론을 도출할 수 있게 된다.
세번째 디버깅을 적극 활용했다.
디버깅을 활용하면 내가 짠 코드에 불필요한 작동이 있는지
불필요한 변수가 있는지
어떤 허점이 있는지
...
등 많은 정보를 얻을 수 있기 때문에
반드시 디버깅을 해보는게 좋다고 생각한다.
피드백, 개선할 점
첫째 문제를 잘 해결했지만
문제의 마지막 조건인
처음부터 모든 토마토가 익은 경우 0을 return
모든 토마도가 익지 않는 경우 -1을 return
하라는 조건을 빼먹고 코드를 작성해서
결과가 오답으로 처리됐다.
문제를 더 꼼꼼하게 읽고, 어떤 조건이 있는지 리스트화 시키자.
느낀점
첫번째 코드를 먼저 적기보다는 알고리즘과 자료구조를 그려놓고
알고리즘의 흐름을 파악하고 결론을 도출한 뒤에
코드를 작성하는게 알고리즘 문제 풀이 속도를 더 단축시키고
더 명확한 코드 구현이 가능해지는 것 같다.
