[Cos Pro 1급 java] [6차] 문제1) 꽃피는 봄이 언제 오나요

안녕하세요

이번 포스팅은 Cos Pro 1급 java 6차 기출문제 중 1번 문제인 꽃피는 봄이 언제 오나요 문제를 풀어보겠습니다.

 

□ 문제설명

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

---

□ 매개변수 설명

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

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

---

□ return 값 설명

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

---

□ 예시

	n	garden	return
예시 #1	3	[[0, 0, 0], [0, 1, 0], [0, 0, 0]]	2
예시 #2	2	[[1, 1], [1, 1]]	1

---

□ 예시설명

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

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

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

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

 

예시 #2

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

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

반응형

 

※ 문제 접근 방식

(1) y, x 변수를 가진 Point 클래스를 만듭니다

(2) Point를 담는 List를 선언합니다.

(3) 이중 for문으로 garden 값이 1이면 리스트에 포인트 객체를 선언해서 넣습니다. cnt를 증가합니다.

(4) do ~ while문으로 cnt값이 n*n개가 될 때까지 순회합니다.

(5) 임시 리스트를 만들고 list사이즈만큼 for문을 순회하며 새로 꽃을 넣을 포인트를 임시 리스트에 넣습니다.

(6) for문이 끝나면 list를 clrear하고 tempList를 list에 초기화합니다.

 

package whenComeSpring;

import java.util.ArrayList;
import java.util.List;

public class WhenComeSpring {
	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 + " 입니다.");
	}
}

class Main {

	class Point {
		int x;
		int y;

		public Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

	public int solution(int n, int[][] garden) {
		int answer = 0;

		List<Point> list = new ArrayList<Point>();
		int cnt = 0;

		for (int i = 0; i < garden.length; i++) {
			for (int j = 0; j < garden[i].length; j++) {
				if (garden[i][j] == 1) {
					list.add(new Point(i, j));
					cnt++;
				}
			}
		}

		do {
			answer++;
			List<Point> tempList = new ArrayList<Point>();
			for (int i = 0; i < list.size(); i++) {
				Point p = list.get(i);

				if (p.y - 1 >= 0 && garden[p.y - 1][p.x] == 0) {
					garden[p.y - 1][p.x] = 1;
					cnt++;
					tempList.add(new Point(p.y - 1, p.x));
				}

				if (p.y + 1 < n && garden[p.y + 1][p.x] == 0) {
					garden[p.y + 1][p.x] = 1;
					cnt++;
					tempList.add(new Point(p.y + 1, p.x));
				}

				if (p.x - 1 >= 0 && garden[p.y][p.x - 1] == 0) {
					garden[p.y][p.x - 1] = 1;
					cnt++;
					tempList.add(new Point(p.y, p.x - 1));
				}

				if (p.x + 1 < n && garden[p.y][p.x + 1] == 0) {
					garden[p.y][p.x + 1] = 1;
					cnt++;
					tempList.add(new Point(p.y, p.x + 1));
				}
			}

			list.clear();
			list = tempList;
		} while (cnt < n * n);

		return answer;
	}
}