(24.10.02)
먼저 문제를 이해해보자. 입력인 배열에서 0은 빈 상태를, 1은 신선한 오렌지를, 2는 썩은 오렌지를 의미한다. 매 분마다 썩은 오렌지에 상하좌우 4방향으로 둘러싸인 신선한 오렌지는 썩게된다.
이때, 모든 오렌지가 썩게되는 최소의 시간을 리턴하고 불가능하다면 -1을 리턴해라.
문제가 굉장히 깔끔하고 이해하기 쉽다. 2들을 BFS를 위해 enqueue하고 visit한 칸은 -1로 처리하여 계산에서 제외한다. 1분에 상하좌우만 가능하니 매 분 for 반복에서 모든 queue를 pop하여 상하좌우를 다 넣어주면 될 듯 하고, 그 for 반복이 얼마나 돌았는지가 곧 결과값이 된다. 최대 반복 횟수는 입력 배열 mxn 중 최댓값-1으로 하면 될 듯 하다.
다음은 코드이다.
class Solution {
int m, n;
public int orangesRotting(int[][] grid) {
m=grid.length;
n=grid[0].length;
int max=Math.max(m, n);
Queue<int[]> queue=new LinkedList<>();
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j]==2){
queue.offer(new int[]{i, j});
}
}
}
int minute;
int[] index;
int[][] directions=new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
Queue<int[]> buf_queue=new LinkedList<>();
for(minute=0; minute<max+1; minute++){//
while(!queue.isEmpty()){
index=queue.poll();
for(int[] direction: directions){
int[] new_index=new int[]{index[0]+direction[0], index[1]+direction[1]};
if(is_valid_idx(new_index) && grid[new_index[0]][new_index[1]] == 1) {
grid[new_index[0]][new_index[1]]=2;
buf_queue.add(new_index);
}
}
}
queue.addAll(buf_queue);
buf_queue.clear();
}
if(minute==max)
return -1;
return minute;
}
private boolean is_valid_idx(int[] index){
if(index[0]<0 || index[0]>=m || index[1]<0 || index[1]>=n)//범위체크 종료조건
return false;
return true;
}
}첫 실행 결과 Case1 만 통과하였다.
Case 2와 Case 3을 보자.
- Case 2
- Case 3
우선 Case 3는 처음부터 이미 진행할 게 없는 상황인데, minute가 계속 올라가 3이 리턴되었다. 이를 해결하기위해 buf_queue 이후 큐가 비어있다면 minute for 루프를 break시키는 코드를 추가하여 해결하였다.
다음으로 Case 2를 보자. 모든 사과를 썩게만들지 못하면 -1을 리턴해야한다. 검사 후 전체 grid에 1이 있는지 확인하는 코드를 추가해주자.
디버깅을 해보니 minute가 11인 상태에서 탐색이 끝났다. 예측 가능한 상황이었는데 실제 Exprected값과 반환된 minute값의 차이가 큰 것으로 보아, BFS로 진행될 때 탐색이 안되고 DFS로 진행할 때 탐색이 되는 경우로 추정된다.
(24.10.04)
현재 303번 테스트케이스에서 BFS로 시도하다 엄청 깊은 깊이의 그래프의 깊이를 제대로 계산하지 못하는 문제가 발견됐었다. 아무리 생각해도 DFS로 해결하는게 훨씬 수월할 것 같다.
하지만, 문제에서 구하라고 하는게 최단거리이기에 DFS는 최장거리가 되어 기존의 코드 문제점을 파악하는 것이 보다 나은 방법이라 판단했다. 현재 BFS의 문제점은 visit한 노드를 모두 2로 바꿔버렸기에 같은 level 다른 노드를 검색해도 2로 이전에 바뀌어 버려 원활한 탐색이 불가능함이다. 이를 해결하기 위해 방문한 노드를 2로 바꾸기 전에 grid를 복사하자.
class Solution {
int m, n;
public int orangesRotting(int[][] grid) {
m=grid.length;
n=grid[0].length;
int max=Math.max(m, n);
Queue<int[]> queue=new LinkedList<>();
int[][] grid_buf;
int[][] directions=new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
int minute;
int[] index;
boolean is_finish;
int min_minute=-1;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j]==2){
//얘부터 시작했을 때
queue.add(new int[]{i, j});
grid_buf=new int[grid.length][grid[0].length];
for(int gi=0; gi<m; gi++)
for(int gj=0; gj<n; gj++)
grid_buf[gi][gj]=grid[gi][gj];
is_finish=true;
minute=0;
int level=queue.size();
while(!queue.isEmpty()){//하나씩 오염시킬 사과의 위치가 담김
index=queue.poll();//인덱스를 가져와서
for(int[] direction: directions){//사 방향에 대해 유효한 인덱스고 신선한 사과가 있을 때
int[] new_index=new int[]{index[0]+direction[0], index[1]+direction[1]};
if(is_valid_idx(new_index) && grid_buf[new_index[0]][new_index[1]] == 1) {
grid_buf[new_index[0]][new_index[1]]=2;//오염시킨다.
queue.add(new_index);//감염된 사과의 위치를 추가함
}
}
level--;
if(level==0) {
minute++;
level = queue.size();
}
}
//더이상 오염시킬 사과가 없다면(큐는 비어있는 상태)
//성공적으로 모든 사과가 감염되었는지 확인
for(int ii=0; ii<m; ii++) {
for (int jj = 0; jj < n; jj++) {
if (grid_buf[ii][jj] == 1) {
is_finish = false;
break;
}
}
if(!is_finish)
break;
}
if(is_finish){//전부 감염 성공
minute--;
if(min_minute==-1) {
min_minute=minute;
} else if(min_minute>minute){//최단 시간 갱신
min_minute=minute;
}
}
}
}
}
return min_minute;
}
private boolean is_valid_idx(int[] index){
//범위체크 종료조건
return index[0] >= 0 && index[0] < m && index[1] >= 0 && index[1] < n;
}
}이전의 Case 303은 해결되었지만 Case 132 grid=[[0]]일 때 0이 아닌 -1를 반환하는 오류를 발견했다. 입력된 grid에 2가 없다면 0을 반환하는 예외처리를 수행하겠다. 이번엔 [[1]]만.. 도 예외처리 수행하겠다. 허나,, 아본앤 134에서 오류가..
(24.10.07)
case 134에서 fail된 것 디버깅을 통해 확인해보겠다.
문제는 기가막히게 2회 탐색 후 끝났는데, 다 끝났는지 확인할 수 없어 3회로 넘어간 것이 문제이다. 다 끝났는지 확인하는 코드를 넣자. 어라라? 이거 3 맞다.
왜 2지? 아하 모든 2에서 감염이 시작되는거였다. 현재 하나의 2에서만 감염이 시작된다.
(24.10.08)
위 문제를 해결하기 위해서 다시 초기의 코드로 돌아갈 수 밖에 없었다. 초기의 접근방식이 맞다는 확신을 문제를 해결해나갈수록 알게되어 전체 minute의 최댓값인 max를 60으로 바꾸어보았더니 문제가 발생했던 테스트케이스들이 해결되었다. 문제는 m과 n값 중 최댓값을 minute의 최댓값으로 정했는데, 대각선 길이를 고려해야하기에 그냥 m*n으로 바꾸었다.
