SWEA 모의 2105 디저트 카페

SWEA 모의 2105 디저트 카페

 

 

문제링크

http://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

 [고려사항]
 디저트 카페를 돌아다니며 디저트를 먹는데 이동 방향을 대각선이다.
 이동 시 주의 사항이 여러가지 존재하는데
 1. 어느 한  카페에서 출발한다 -- 어딘지 특정할 수 없기 때문에 모든 점에서 탐색 해볼 필요가 있다.
 2. 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
 3. 왔던 길을 다시 되돌아 갈 수 없다. 
  -- 2, 3의 조건에 의해 회전을 해서 출발지로 돌아와야 함을 알 수 있다.
  -- 어차피 회전해서 돌아오기 때문에 오른쪽 또는 왼쪽을 모두 고민할 필요가 없다. 우리는 오른쪽으로 돈다고 생각하자.
  -- 회전의 방향이 정해져있기 때문에 대각선 사방 탐색을 할 때 탐색 방향의 순서가 정해진다.
  -- 회전 회수가 4인 상황에서 출발지와 현재 지점의 좌표가 동일하면 목적지를 잘 찾아온 것이다.
 4. 투어 도중 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안된다.
 -- 중복 방문을 하지 않기 위해서 일반적으로 visited를 사용할 수 있는데 
 -- 지도 전체에 대한 점검 보다는 먹은 디저트로 한정하는 것이 유리하다.
 -- 따라서 이 문제에서 visited의 역할은 해당 디저트를 먹었는지에 대한 고민으로 대체한다.
 5. 한 곳에서 하나만 먹고 끝내는 행위는 허용되지 않는다.
 6. 어떤 지점에서 다른 지점으로 방문 시 가능한 모든 노드의 경우를 따져야 하는데
 -- 이 문제에서는 회전해야 하기 때문에 매번 한칸 전진과 우회전만 고민하면 된다.
  

 [입력 사항]
 지도는 N*N으로 주어지고 N은 4 이상 20 이하의 정수이다. (4 ≤ N ≤ 20)
 디저트의 종류는 1~100이하
  
 [출력 사항]
 가장 많이 먹을 때의 디저트 수를 출력하고 먹을 수 없는 경우 정답은 -1
  
 * 분류: #dfs

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=f9MCBzZHrso&feature=youtu.be

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.모의;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

public class SWEA_모의_2105_디저트카페 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    // 대각선 사방탐색
    private static int[][] dirs = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};

    private static int TC;
    private static int N; // 지도의 크기 N
    private static int MAX; // 최대 디저트 개수

    private static int[][] map;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));

        TC = Integer.parseInt(input.readLine());

        for (int t = 1; t < TC + 1; t++) {
            N = Integer.parseInt(input.readLine());
            map = new int[N][N];
            StringTokenizer tokens = null;
            for (int r = 0; r < N; r++) {
                tokens = new StringTokenizer(input.readLine());
                for (int c = 0; c < N; c++) {
                    map[r][c] = Integer.parseInt(tokens.nextToken());
                }
            }

            // 입력 완료
            MAX = Integer.MIN_VALUE;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    // 각각의 지점에서 디저트를 먹고 출발해본다.
                    Node node = new Node(r, c, 0);
                    boolean[] eatenDeserts = new boolean[101];
                    findPath(node, node, eatenDeserts);
                }
            }

            output.append("#").append(t).append(" ").append(MAX == Integer.MIN_VALUE ? -1 : MAX).append("\n");

        } // for
        System.out.println(output);
    }// main

    static void findPath(Node start, Node current, boolean[] eatenDeserts) {
        // current가 목적지라면 별 고민없지롱~ - 최대값 비교 후 종료
        if (current.d == 4) {
            if (current.r == start.r && current.c == start.c) {
                // System.out.println("출발지점에 왔어.!!!");
                int cnt = 0;
                for (int i = 0; i < eatenDeserts.length; i++) {
                    if (eatenDeserts[i]) {
                        cnt++;
                    }
                }
                MAX = Math.max(cnt, MAX);
            }
            return;
        }

        // 목적지가 아니라면 일단은 무조건 현재 방향으로 한칸은 전진한다.
        int nr = current.r + dirs[current.d][0];
        int nc = current.c + dirs[current.d][1];
        // System.out.println(current.r + " : " + current.c + "> " + nr + " : " + nc);

        if (isIn(nr, nc)) {
            // 전진한 곳에 있는 디저트가 처음 본거라면..
            if (eatenDeserts[map[nr][nc]] == false) {
                // 먹어서 방문 처리 방문 처리
                eatenDeserts[map[nr][nc]] = true;
                // 자식 노드 찾기 - 직진이거나 방향 회전 하거나.
                // 현재 방향으로 직진하는 경우
                Node nodeDirect = new Node(nr, nc, current.d);
                findPath(start, nodeDirect, eatenDeserts);

                // 방향 회전 고민 : 아직 방향이 3이하면 방향 회전 해보자.
                Node nodeTurn = new Node(nr, nc, current.d + 1);
                findPath(start, nodeTurn, eatenDeserts);

                // 흐름이 실패했다면 방문 안한척 하기 - 그냥 int를 이용한 삭제는 index를 의미하므로 주의할것!!!
                eatenDeserts[map[nr][nc]] = false;
            }
        }
    }

    private static boolean isIn(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < N;
    }

    static class Node {
        int r, c, d;// row, col, dir
        int t; // 디저트 타입

        public Node(int r, int c, int d) {
            super();
            this.r = r;
            this.c = c;
            this.d = d;
            t = map[r][c];
        }

        @Override
        public String toString() {
            return "[r=" + r + ", c=" + c + ", t=" + t + ", d=" + d + "]";
        }

    }

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