Cos Pro 1급 - 샘플 문제 풀이 4차 4번 (마방진 만들기)

문제 지문 #4

마방진이란 가로, 세로, 대각선 방향의 수를 더한 값이 모두 같은 정사각형 행렬입니다. 마방진에는 1부터 정사각형 넓이까지, 수가 하나씩 배치되어야 합니다. 아래는 가로, 세로, 대각선 방향의 수를 더한 값이 모두 34인 4 x 4 마방진입니다.

4 x 4 행렬의 두 빈칸을 채워 행렬을 마방진으로 완성하려 합니다. 빈칸은 0으로 표시합니다. 이를 위해 다음과 같이 프로그램 구조를 작성했습니다.

1. 두 빈칸의 위치를 찾습니다.
2. 숫자 1 ~ 16 중 존재하지 않는 숫자 2개를 찾습니다.
3. 첫 번째 빈칸에 작은 숫자를, 두 번째 빈칸에 큰 숫자를 넣어 행렬이 마방진이 되는지 검사합니다.
  4-1. 마방진이라면 [작은 숫자의 행 번호, 작은 숫자의 열 번호, 작은 숫자, 큰 숫자의 행 번호, 큰 숫자의 열 번호, 큰 숫자]를 return 합니다.
  4-2. 마방진이 아니라면 [큰 숫자의 행 번호, 큰 숫자의 열 번호, 큰 숫자, 작은 숫자의 행 번호, 작은 숫자의 열 번호, 작은 숫자]를 return 합니다.

4 x 4 크기 2차원 배열 matrix가 매개변수로 주어질 때, 이때 빈칸의 위치와 각 칸에 들어갈 수를 담은 배열을 return 하도록 solution 메소드를 작성하려 합니다. 위 구조를 참고하여 코드가 올바르게 동작하도록 빈칸에 주어진 func_a, func_b, func_c 메소드와 매개변수를 알맞게 채워주세요.

• 주어진 행렬은 빈칸을 채우면 반드시 마방진으로 완성할 수 있습니다.

---

#####매개변수 설명

2차원 배열 matrix가 solution 메소드의 매개변수로 주어집니다.

• matrix는 크기가 4 x 4인 2차원 배열입니다.
• matrix에는 0이 반드시 두 개 들었습니다.
• matrix에는 1 이상 16 이하인 자연수 14개가 겹치지 않게 들었습니다.

---

#####return 값 설명

빈칸의 위치와 각 칸에 들어갈 수를 담은 배열을 return 해주세요.

---

#####예시

matrix	return
[[16,2,3,13],[5,11,10,0],[9,7,6,12],[0,14,15,1]]	[4,1,4,2,4,8]

#####예시 설명

예시 #1

위 그림에서 빈칸은 (4, 1)과 (2, 4)입니다. 각 칸에 4와 8을 채우면 마방진이 완성됩니다. 따라서 [작은 숫자의 행 번호, 작은 숫자의 열 번호, 작은 숫자, 큰 숫자의 행 번호, 큰 숫자의 열 번호, 큰 숫자]를 return 해야 합니다. 답은 [4, 1, 4, 2, 4, 8]입니다.

728x90

 

혼자 풀이

빈칸 채우기 문제입니다. func_a, func_b, func_c의 리턴 타입이 모두 다르기 때문에, 각 함수의 리턴 타입을 보면 빈칸을 채우는 것 자체는 어렵지 않습니다. 각 함수의 로직도 brute force 방식으로 짜여져 어렵지 않게 이해가 됩니다.
어렵게 느껴지는 부분은 ArrayList인데요. 아무래도 제네릭 타입이 익숙하지 않다보니 꺽쇠<>만 나오면  정신이 혼미해 지는 부분이 있어서 어떻게 사용이 되는지 자세히 봐두면 좋을 것 같습니다.

※ 제네릭(Generic): 클래스를 선언할 때는 자료형에 의존적이지 않게 작성하고, 인스턴스 생성시에 자료형을 결정하는 것이 제네릭 프로그래밍입니다. 아래의 예에서는 class Pair의 자료형이 선언시에는 T1,T2로 일반화 되어있다가
solution 함수에서 사용될 때 Integer로 자료형을 사용하였습니다. ArrayList도 실제 class에서는 "class ArrayList<E>" 로 선언되어있고, 아래에서 변수, 함수에서 사용할 때 Integer로 자료형이 지정되었습니다.

import java.util.*;

class Main {
    public static final int n = 4; 

    class Pair<T1, T2> { //비어있는 두칸을 나타내는 클래스
        Integer key;
        Integer value;

        public Pair(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }

        public Integer getKey() {
            return key;
        }

        public Integer getValue() {
            return value;
        }
    }
		//matrix에서 존재하지 않는 숫자 찾기
    public ArrayList<Integer> func_a(int[][] matrix) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        boolean [] exist = new boolean[n * n + 1];
        Arrays.fill(exist, false);
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j++)
                    exist[matrix[i][j]] = true;
        for (int i = 1; i <= n * n; i++)
            if (exist[i] == false)
                ret.add(i);		
        return ret;
    }
    //matrix에서 빈칸 찾기
    public ArrayList<Pair<Integer, Integer> > func_b(int[][] matrix) {
        ArrayList<Pair<Integer, Integer> > ret = new ArrayList<Pair<Integer, Integer> >();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == 0)
                    ret.add( new Pair<Integer, Integer>(i, j) );
        return ret;
    }
    //마방진인지 검사하는 함수
    public boolean func_c(int[][] matrix) {
        int sum = 0;
        for (int i = 1; i <= n * n; i++)
            sum += i;
        sum = sum / n;
        for (int i = 0; i < n; i++) {
            int rowSum = 0;
            int colSum = 0;
            for (int j = 0; j < n; j++) {
                rowSum += matrix[i][j];
                colSum += matrix[j][i];
            }
            if (rowSum != sum || colSum != sum)
                return false;
        }
        int mainDiagonalSum = 0;
        int skewDiagonalSum = 0;
        for (int i = 0; i < n; i++) {
            mainDiagonalSum += matrix[i][i];
            skewDiagonalSum += matrix[i][n-1-i];
        }
        if (mainDiagonalSum != sum || skewDiagonalSum != sum)
            return false;
        return true;
    }
    
    public int[] solution(int[][] matrix) {
        int[] answer = new int[6];
        int ansIdx = 0;
		// ArrayList<Pair<Integer, Integer> > coords = func_@@@(@@@);
        ArrayList<Pair<Integer, Integer> > coords = func_b(matrix); //1. 두 빈칸을 찾음 , 리턴값을 보면 뻔함
		// ArrayList<Integer> nums = func_@@@(@@@);
        ArrayList<Integer> nums = func_a(matrix); //2. 1~16중 존재하지 않는 숫자 두개를 찾기
        
        matrix[coords.get(0).getKey()][coords.get(0).getValue()] = nums.get(0);  //3. 첫번째 빈칸에 작은수를 두번째 빈칸에 큰 수를 넣어
        matrix[coords.get(1).getKey()][coords.get(1).getValue()] = nums.get(1);
        // if (func_@@@(@@@)) {
		if (func_c(matrix)) {  //4-1. 마방진이라면...
            for (int i = 0; i <= 1; i++) {
                answer[ansIdx++] = coords.get(i).getKey() + 1;    
                answer[ansIdx++] = coords.get(i).getValue() + 1;
                answer[ansIdx++] = nums.get(i);
            }
        }
        else {  //4-2. 마방진이 아니라면...
            matrix[coords.get(0).getKey()][coords.get(0).getValue()] = nums.get(1);
            matrix[coords.get(1).getKey()][coords.get(1).getValue()] = nums.get(0);
            for (int i = 0; i <= 1; i++) {
                answer[ansIdx++] = coords.get(1-i).getKey() + 1;
                answer[ansIdx++] = coords.get(1-i).getValue() + 1;
                answer[ansIdx++] = nums.get(i);
            }
        }
        return answer;
    }

 

정답

혼자 풀이와 정답이 동일합니다.

실습은 아래 참고

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

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