[SWEA] 2105.디저트 카페.java

#. Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

조건 먼저 천천히 정리해보자.

1. 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.

단! 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다.

2. 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다.

그래서! 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.

3. 서로 다른 디저트를 먹으면서 사각형 모양을 그리며 다시 출발점으로 돌아오는 경우,

디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 출력하자.

4. 디저트를 먹을 수 없는 경우 -1

이 조건을 받아적듯이 코드로 써내려가면 된다.

나는 단순하게 그러했다.

하지만, 이 방법 말고도 정말 효율적이고 색다른 다양한 방법이 있는 것 같다.

만들 수 있는 가장 큰 사각형의 크기를 구한 후,

시도할 수 있는 시작점을 찾아서 조건에 맞게 디저트 수를 구하고 바로 종료하는 방법.

이 방법은 가장 큰 사각형의 크기를 갖는 경우부터 시도하니까

답이 구해지면 바로 가장 많은 디저트를 먹는 해를 구할 수 있게 된다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Solution2105 {       static int N, map[][], res, startX, startY;     static boolean isAte[];     // 우하, 좌하, 좌상, 우상     static int[] dx = {1, 1, -1, -1}, dy = {1, -1, -1, 1};          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  int T = Integer.parseInt(br.readLine());         for (int tc = 1; tc <= T; tc++) {                          N = Integer.parseInt(br.readLine());             map = new int[N][N];             res = -1;                          // 디저트 카페의 디저트 종류 입력             for (int i = 0; i < N; i++) {                 st = new StringTokenizer(br.readLine());                 for (int j = 0; j < N; j++) {                     map[i][j] = Integer.parseInt(st.nextToken());                 }             }                          // 사각형 모양을 만들 수 있는 최소의 범위만 확인             for (int i = 0; i < N - 2; i++) {                 for (int j = 1; j < N - 1; j++) {                     // 여기부터 디저트 카페 투어 시작                     isAte = new boolean[101];                     isAte[map[i][j]] = true;                     // 시작점                     startX = i;                     startY = j;                                          go(i, j, -1, -1, 0, 0);                 }             }                          // 디저트를 가장 많이 먹을 때의 디저트 수             System.out.println("#" + tc + " " + res);         }       }       /**      *       * @param x    행 좌표      * @param y    열 좌표      * @param prevX    이전 행 좌표      * @param prevY    이전 열 좌표      * @param cnt    먹은 디저트 개수      * @param sd    이동 방향      */     private static void go(int x, int y, int prevX, int prevY, int cnt, int sd) {           // 대각선 방향으로 이동         for (int d = sd; d < 4; d++) {             int xx = x + dx[d];             int yy = y+ dy[d];             // 지역을 벗어나면 pass                         if(xx < 0 || yy < 0 || xx >= N || yy >= N) continue;             // 이전 카페로 되돌아갈 경우             if(xx == prevX && yy == prevY) continue;             // 시작점으로 도착할 경우             if(xx == startX && yy == startY) {                 // 디저트를 먹은 최대 개수 갱신                 res = Math.max(res, cnt + 1);                 return;             }             // 이미 먹은 디저트일 경우 pass             if(isAte[map[xx][yy]]) continue;                          // 디저트 냠냠             isAte[map[xx][yy]] = true;             go(xx, yy, x, y, cnt + 1, d);                          // 디저트 퉤퉤                         isAte[map[xx][yy]] = false;         }              }   } Colored by Color Scripter

cs

line 11) 무조건 우하, 좌하, 좌상, 우상 순서대로 이동하도록 지정해주었다.

line 65) 해당 방향(sd)부터 이동한 이유는 사각형 모양이 아닌 다른 방향으로 튀는 경우를 

처리해주고자 우하, 좌하, 좌상, 우상 순서대로 이동하도록 하였다.

line 71) 이전 좌표로 되돌아가는 경우가 생겨서 그 경우를 처리해주고자 이전 좌표를 들고 재귀 호출을 하였다.

line 73) 시작점에 도착하면 디저트를 먹은 최대 개수를 갱신해주고 바로 return 처리

line 79) 이미 먹은 디저트일 경우 pass

#. Other Code

만들 수 있는 가장 큰 사각형의 크기를 구한 후,

시도할 수 있는 시작점을 찾아서 조건에 맞게 디저트 수를 구하고 바로 종료하는 방법이다.

잘 짠 코드를 보면서 각성해야지...!

/*
*
* reference : 남우진_0411857
*
*/
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
    static class Node {
        int r, c; // 좌표
        int dir; // 내려가는 방향(0 : 왼쪽아래, 1: 오른쪽 아래)
        int move; // 이동횟수
        int change; // 방향회전 횟수
 
        Node(int r, int c, int dir, int move, int change) {
            this.r = r;
            this.c = c;
            this.dir = dir;
            this.move = move;
            this.change = change;
        }
    }
 
    static int[][] array;
    static int[] dr = { 1, 1 };
    static int[] dc = { -1, 1 };
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        for (int tc = 1; tc <= T; ++tc) {
            StringTokenizer st;
            int N = Integer.parseInt(in.readLine());
            array = new int[N][N];
            for (int i = 0; i < N; ++i) {
                st = new StringTokenizer(in.readLine());
                for (int j = 0; j < N; ++j) {
                    array[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            int ans = -1;
            out: for (int k = N - 1; k > 1; --k) {   //마름모 전체 길이 지정
                for (int l = 1; l < k; ++l) {
                    int d1 = l;
                    int d2 = k - l;
                    for (int i = 0; i < N - 2; ++i) {
                        for (int j = 1; j < N - 1; ++j) {
                            if (i + d1 + d2 < N && j + d2 < N && j - d1 >= 0) {
                                if (makeSquare(i, j, d1, d2)) {
                                    ans = 2 * k;
                                    break out;
                                }
                            }
                        }
                    }
                }
            }
            System.out.println("#" + tc + " " + ans);
        }
 
    }
 
    private static boolean makeSquare(int i, int j, int d1, int d2) {
        boolean[] met = new boolean[101];
        Queue<Node> queue = new LinkedList<>();
        met[array[i][j]] = true;
                            // 좌표, 방향, 이동횟수, 방향전환횟수
        queue.offer(new Node(i + dr[0], j + dc[0], 0, 1, 0));
        queue.offer(new Node(i + dr[1], j + dc[1], 1, 1, 0));
 
        while (!queue.isEmpty()) {
            Node n = queue.poll();
 
            if (met[array[n.r][n.c]])
                return false;
 
            met[array[n.r][n.c]] = true;
 
            if (n.dir == 0 && n.move == d1) {
                if (n.change == 1) {
                    return true;
                }
                queue.offer(new Node(n.r+dr[1], n.c+dc[1], 1, 1, 1));
                continue;
 
            } else if (n.dir == 1 && n.move == d2) {
                if (n.change == 1) {
                    return true;
                }
                queue.offer(new Node(n.r+dr[0], n.c+dc[0], 0, 1, 1));
                continue;
            }
            queue.offer(new Node(n.r + dr[n.dir], n.c + dc[n.dir], n.dir, n.move + 1, n.change));
        }
 
        return true;
    }
}