[SW Expert] 2105. [모의 SW 역량테스트] 디저트 카페

생각

디저트 카페가 2차 배열에 숫자로 주어진다. 각 디저트 카페에서 아래 사진과 같이 대각선으로 다른 카페로
이동할 수 있다.

이 때, 같은 숫자를 가진 카페로는 이동을 하지 못할 때, 가장 많이 디저트를 먹을 수 있는 수를 출력하여라.

풀이후 생각

이 문제를 풀이도중 하반기 서류탈락을 했습니다. 당분간은 역량 테스트용 문제는 조금 줄이고 일반 알고리즘 문제 위주로 풀어야겠네요. 서류 붙으신 분들은 축하드리고 이 글을 읽고 계시다는 자체가 테스트 통과를 위해 노력하고 계신다는 거니 잘 치루셔서 좋은 결과 있으시길 바라겠습니다!

처음 생각

1

static int[][] dir = {{1,1},{1,-1},{-1,-1},{-1,1}};

cs

맵을 탐색하는데 상 하 좌 우가 아닌 대각선 방향으로 탐색을 진행하기 위해 위와같이 좌표 설정을 하였다.

▶ 대각선 4방향을 모두 탐색 진행하였더니 시간 초과를 얻었다. 생각해보면 4방향 탐색을 진행하지 않아도 되는것을 알 수 있다. 왜냐면 사각형만 만들면 되기 때문에 왼쪽으로 사각형을 만드는 것과 오른쪽으로 사각형을 만드는 것 둘다 똑같기 때문이다. 그 다음 오른쪽 아래로 방향을 정했다면 사각형을 만들기 위한 형태는 똑같다. 우측 하단 진행 -> 좌측하단 진행 -> 좌측 상단 진행 -> 우측 상단 진행으로 만들어 진다. 

▶ 아래 그림과 같이 탐색을 진행할 때 항상 위쪽에서 내려가는 방향으로 진행하기 때문에 위에서 살펴본 방향만 따져주면 된다.

다음 생각

기존 4방향 탐색을 위한 반복문을 지워준 후 특정 케이스(범위를 벗어났을 때, 같은 카페에 들렀을 때, 중복된 숫자일 때) 에서 다음 방향으로 바꿔주고, 갈 수 있는 방향일 때도 기존 방향 진행과 다음 방향 진행 2가지로 DFS를 진행시켜 주었습니다.

▶ 어차피 마지막에 말한 2방향 탐색으로 모든 방향 탐색이 가능하기 때문에 특정 케이스에서 방향을 바꿔주는 것은 지워주었습니다.

방안

1) 방향을 살펴보는게 일관성 있기 때문에 2차 배열 dir을 순서대로 진행할 수 있도록 해준 뒤 방향 변수 d를 +1씩 증가시키며 진행하였다.

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

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   class Solution {     static int n;     static int[][] arr;     public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringBuilder sb = new StringBuilder();         int tc = Integer.parseInt(br.readLine());         for(int i=1;i<=tc;i++) {             n = Integer.parseInt(br.readLine());             arr = new int[n][n];             // 입력 받기             for(int j=0;j<n;j++) {                 StringTokenizer st = new StringTokenizer(br.readLine());                 for(int k=0;k<n;k++)                     arr[j][k] = Integer.parseInt(st.nextToken());             }             // 방문 체크             visited = new boolean[n][n];             // 중복 숫자 체크(1~100)             nVisited = new boolean[101];             // result 초기화             result = 0;             // 50개 케이스 3초 n=20개 최대             for(int j=0;j<n;j++) {                 for(int k=0;k<n;k++) {                     startX = j;                     startY = k;                     visited[j][k] = true;                     nVisited[arr[j][k]] = true;                     // 왼쪽으로 도나 오른쪽으로 도나 똑같기 때문에 한 쪽 아래로만 돌면 된다.                     solve(j,k,1,0);                     visited[j][k] = false;                     nVisited[arr[j][k]] = false;                 }             }             if(result<4) result = -1;             sb.append("#"+i+" "+result+"\n");         }         System.out.print(sb);     }          static int startX,startY,result;     static boolean[] nVisited;     static boolean[][] visited;     static int[][] dir = {{1,1},{1,-1},{-1,-1},{-1,1}};     private static void solve(int x,int y,int cnt,int d) {         if(d==4) return;         int tx = x+dir[d][0];         int ty = y+dir[d][1];         if(tx<0 || ty<0 || tx>=n || ty>=n) return;         if(visited[tx][ty]||nVisited[arr[tx][ty]]) {             // 이미 갔던 지점이 시작 점일 경우 개수 따지기             if(tx==startX&&ty==startY)                 result = Math.max(result, cnt);             return;         }         // 숫자 사용 & 방문 표시         nVisited[arr[tx][ty]] = true;         visited[tx][ty] = true;         // 한 방향으로 쭉         solve(tx,ty,cnt+1,d);         // 그 때 그 때 다음 방향으로 틀기         solve(tx,ty,cnt+1,d+1);         visited[tx][ty] = false;         nVisited[arr[tx][ty]] = false;     } } Colored by Color Scripter

cs