파트3. 함수 작성 - 꽃피우기

문제 설명

정사각형 크기 격자 모양 정원에 칸마다 핀 꽃 또는 피지 않은 꽃을 심었습니다. 이 정원의 꽃이 모두 피는 데 며칠이 걸리는지 알고 싶습니다. 핀 꽃은 하루가 지나면 앞, 뒤, 양옆 네 방향에 있는 꽃을 피웁니다.

현재 정원의 상태를 담은 2차원 배열 garden이 주어졌을 때, 모든 꽃이 피는데 며칠이 걸리는지 return 하도록 solution 메소드를 작성해주세요.

---

매개변수 설명

현재 정원 상태를 담은 2차원 배열 garden이 solution 메소드의 매개변수로 주어집니다.

• 정원의 한 변의 길이는 2 이상 100 이하입니다.
• 정원 상태를 담은 2차원 배열 garden의 원소는 0 또는 1 입니다.
• 이미 핀 꽃은 1로 아직 피지 않은 꽃은 0으로 표현합니다.
• 정원에 최소 꽃 한 개는 피어 있습니다.

---

return 값 설명

꽃이 모두 피는데 며칠이 걸리는지 return 합니다.

---

예제gardenreturn

[[0, 0, 0], [0, 1, 0], [0, 0, 0]]	2
[[1, 1], [1, 1]]	0

예제 설명

예제 #1
첫 날 정원은 아래와 같습니다.

1일이 지난 정원의 상태는 아래와 같습니다.

2일이 지난 정원의 상태는 아래와 같습니다.

따라서, 2일이 지나면 정원의 모든 꽃이 핍니다.

예제 #2
첫 날 화단의 상태는 아래와 같습니다.

따라서, 0일이 지나면 정원의 모든 꽃이 핍니다.

 

---

// 다음과 같이 import를 사용할 수 있습니다.
import java.util.*;
class Solution {
    public static int xMove[] = {-1, 1, 0, 0};
    public static int yMove[] = {0, 0, -1, 1};
    public int solution(int[][] garden) {
        // 여기에 코드를 작성해주세요.
        int answer = 0;
        Queue<info> flower = new LinkedList<>();
        
        for(int i=0; i<garden.length; i++){
            for(int j=0; j<garden[0].length; j++){
                if(garden[i][j]==1) flower.add(new info(i, j));
            }
        }
        
        while(!flower.isEmpty()){
            info info = flower.poll();
            int x = info.x;
            int y = info.y;
            for(int i=0; i<4; i++){
                int xTo = x-xMove[i];
                int yTo = y-yMove[i];
                if(xTo<0 || yTo<0 || xTo>=garden.length || yTo>=garden[0].length) continue;
                if(garden[xTo][yTo]==0){
                    int days = garden[x][y];
                    int nextDay = days+1;
                    garden[xTo][yTo] = nextDay;
                    flower.add(new info(xTo, yTo));
                    answer = Math.max(answer, nextDay-1);
                }
            }
        }
        
        return answer;
    }
    
    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] garden1 = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        int ret1 = sol.solution(garden1);
        
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret1 + " 입니다.");
        
        int[][] garden2 = {{1, 1}, {1, 1}};
        int ret2 = sol.solution(garden2);
        
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret2 + " 입니다.");
        
    }    
}
class info{
    int x;
    int y;
    info(int x, int y){
        this.x = x;
        this.y = y;
    }
}

1. 꽃이 핀 것(1)을 모두 Queue에 좌표로 저장
2. 그 꽃들의 상하좌우 확인
3. 상하좌우에 꽃이 안핀 곳(0)이 있으면 거기에는 다음날에 꽃이 핀다.
4. 현재 꽃이 피는데 걸린 시간 + 1 = 다음 꽃이 피는데 걸리는 시간
5. 그걸 계속 반복하면 총 꽃이 피는데 걸린 시간이 구해진다.
6. 이 중 최대값이 전체 꽃이 걸리는데 걸린 시간+1이다.
   • 그 이유는 꽃이 핀것이 1로 시작했기 때문이다.
7. 귀찮게 전체 맵을 돌 필요 없이 그냥 혹시 꽃이 아직 안핀 곳(다음날 펴야한다)이 있으면 그걸 저장하면서 다음에 저장된 숫자가 최대값이 됨으로 그걸 answer에 -1해서 max로 넣어주면 된다
8. 이렇게 하면 처음에 모든 꽃이 핀 경우 시작에 세팅된 0이 return되고, 꽃이 펴야하는 경우 1로부터 시작된 날짜가 마지막에 언제 끝나는지 파악해서 그 -1을 구하주면 된다는 것이다.

사실 이거 일부러 파악하기 쉽게 코드를 좀 더럽게 풀어 놓았다. 변수명을 굳이 더럽게 늘릴 필요 없이

이렇게만 해놔도 충분히 알아볼 수 있을 것이다.