Cos Pro 1급 - 샘플 문제 6차 1번 - 모든 꽃이 피는 날 구하기

문제 지문 #1

n x n 크기 격자 모양 정원에 칸마다 핀 꽃 또는 피지 않은 꽃을 심었습니다. 이 정원의 꽃이 모두 피는 데 며칠이 걸리는지 알고 싶습니다. 핀 꽃은 하루가 지나면 앞, 뒤, 양옆 네 방향에 있는 꽃을 피웁니다.
정원 크기 n과 현재 정원의 상태를 담은 2차원 배열 garden이 주어졌을 때, 모든 꽃이 피는데 며칠이 걸리는지 return 하도록 solution 메서드를 작성해주세요.

---

#####매개변수 설명
정원 크기 n과 현재 정원 상태를 담은 2차원 배열 garden이 solution 메서드의 매개변수로 주어집니다.

• 정원 크기 n은 1보다 크고 100 보다 작거나 같은 자연수입니다.
• 정원 상태를 담은 2차원 배열 garden의 원소는 0 또는 1입니다.
• 이미 핀 꽃은 1로 아직 피지 않은 꽃은 0으로 표현합니다.
• 정원에 최소 꽃 한 개는 피어 있습니다.

---

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

---

#####예시

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

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

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

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

따라서, 2일이 지나면 정원의 모든 꽃이 핍니다.
예시 #2
첫날 화단의 상태는 아래와 같습니다.

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

728x90

 

혼자 풀이

전체 코드를 작성하는 문제입니다. nxn 크기의 정원과 꽃이 피어있는 위치가 주어지고, 하루가 지날 때마다 꽃의 상하좌우에 꽃이 필 때, 꽃이 정원을 가득 채우는 날짜를 구하는 문제입니다.
저는 bruteforce 방식으로 정원의 모든 칸에 대해 for문으로 순회하면서 꽃을 피우려고 했습니다.
그런데, garden 배열만 사용하여 순회하면, 처음 꽃보다 좌표가 큰 꽃이 한번 순회할 때 같이 꽃이 피어버립니다.
그래서 별도로 꽃이 피는 날짜를 표시하는 day 배열을 만들어 꽃이 피는 날짜를 체크했습니다.
그 외는 체스 말 움직이기와 비슷한 방식으로 처리했습니다.

// 다음과 같이 import를 사용할 수 있습니다.
import java.util.*;

class Main {
    //꽃이피는 위치가 정원 밖으로 나가지 않게 체크
    public boolean inRange(int x, int y, int n){
        if(x>=0 && y>=0 && x<n && y<n){
            return true;
        }
        return false;
    }
    public int solution(int n, int[][] garden) {
        // 여기에 코드를 작성해주세요.
        int answer = 0;
        int[][] day = new int[n][n]; //정원의 각 자리에 꽃이 몇일째에 피는지를 나타내는 배열
        int nowDay=0; //현재 몇일째인지 나타내는 변수

        int[] dx={1,-1,0,0}; //이동방향			
        int[] dy={0,0,1,-1}; //이동방향

        boolean blossom=true;
        while(blossom){					//꽃이 한개도 피지 않았으면 루프 종료
            blossom=false;				//false가 true로 바뀌지 않으면 루프 종료	
            for(int x=0;x<n;x++){
                for(int y=0;y<n;y++){
                    if(garden[x][y]==1 && day[x][y]==nowDay){ //꽃이 피어있고, 꽃이피는 날짜가 nowDay와 같아야 해당일에 꽃이 핌
                        //System.out.println("꽃:"+x+" "+y);
                        for(int i=0;i<4;i++){
                            if(inRange(x+dx[i],y+dy[i],n)){//두개 조건을 &&로 하면 out of index 오류 남
                                if(garden[x+dx[i]][y+dy[i]]==0){ //꽃이 피어있지 않으면
                                    garden[x+dx[i]][y+dy[i]]=1;   //꽃을 피우고
                                    day[x+dx[i]][y+dy[i]]=nowDay+1; //꽃이피는 날짜는 오늘 날짜+1을 넣어줌
                                    //System.out.println("blossom:"+(x-1)+" "+y);
                                    blossom=true; //꽃이 피었음을 저장
                                }
                            }
                        }			
                    }											
                }							
            }					
            nowDay++; //for문을 전체 반복할 때마다 날짜 증가
        }			  
        return nowDay-1; //마지막에 nowDay가 증가했으므로 1 빼줌
    }
    
    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args) {
        Main sol = new Main();
        int n1 = 3;
        int[][] garden1 = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        int ret1 = sol.solution(n1, garden1);
        
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret1 + " 입니다.");
        
        int n2 = 2;
        int[][] garden2 = {{1, 1}, {1, 1}};
        int ret2 = sol.solution(n2, garden2);
        
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret2 + " 입니다.");
        
    }    
}

 

정답

정답에서는 Flower 클래스를 선언해서 며칠 째 꽃이 피는지를 Flower의 멤버 변수로 두었습니다.
그리고 for문으로 전체 정원에 대해 순회하지 않고 큐를 만들고 꽃이 피면 큐에 꽃을 넣으면서 하나씩 꺼내서 꽃을 피우고, 꽃이 더 이상 피지 않아서 큐에 값이 없으면 종료하였습니다.

// 다음과 같이 import를 사용할 수 있습니다.
import java.util.*;

class Flower{
	int x,y,day;
	Flower(int x, int y, int day){
		this.x=x;
		this.y=y;
		this.day=day; //며칠째 피는 꽃인지를 저장
	}
}

class Main {
    public int solution(int n, int[][] garden) {
        // 여기에 코드를 작성해주세요.
        int answer = 0;

        int[] dx={-1,1,0,0};
        int[] dy={0,0,-1,1};

        Queue<Flower> q=new LinkedList<Flower>();

		//개화한 위치(1)을 찾아서 q에 넣음
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(garden[i][j]==1){ 
                    q.offer(new Flower(i,j,0));
                }
            }
        }
        //개화한 위치에서 꽃을 피움
        while(!q.isEmpty()){ //q에 개화 대상이 없으면 반복문 종료
            Flower flower = q.poll();

            for(int i=0;i<4;i++){
                int nextX=flower.x+dx[i];
                int nextY=flower.y+dy[i];
                int nextDay=flower.day+1;

				//nextX, nextY가 garden 범위 안에 있고, 꽃이 피지 않았을 때,
                if(nextX >=0 && nextX<n && nextY>=0 && nextY<n && garden[nextX][nextY]==0 ){
                    garden[nextX][nextY]=1;
                    answer=nextDay;
                    q.offer(new Flower(nextX,nextY,nextDay));//꽃을 피우고 큐에 입력					
                }
            }
        }
        return answer;
}
        
	// 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args) {
        Main sol = new Main();
        int n1 = 3;
        int[][] garden1 = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        int ret1 = sol.solution(n1, garden1);

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret1 + " 입니다.");

        int n2 = 2;
        int[][] garden2 = {{1, 1}, {1, 1}};
        int ret2 = sol.solution(n2, garden2);

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
System.out.println("solution 메소드의 반환 값은 " + ret2 + " 입니다.");
        
    }    
}

 

실습은 아래 참고

2022.10.25 - [Programming/Cos Pro 1급] - Cos Pro 1급 공부 사이트 추천 - 구름 에듀(https://edu.goorm.io/)

Cos Pro 1급 공부 사이트 추천 - 구름에듀(https://edu.goorm.io/)