<Algorithm> 154. 디저트카페(SWExpert)

1. 디저트카페(SWExpert)

   사용 알고리즘 : DFS, 백트래킹

• 어떻게 알고리즘으로 그려야 하는지 감이 안잡혀서 어렵게 느껴졌던 문제이다.  DFS의 활용 문제중 기본문제가 아닐까 생각이든다. 

• 테트로미노 문제도 그렇고 어떤 도형을 그릴때는 DFS로 하면 될 것 같다.(펜 띠지 않고 그릴수 있는 도형만)

문제에 대한 접근&생각

1. 도형 그리기 -> DFS!
2. 모든 직사각형 영역을 구해야함 -> 백트래킹!
3. 디저트가 같을 경우 갈 수 없음 -> 종료 조건

내 코드 

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

import java.util.LinkedList; import java.util.List; import java.util.Scanner; import java.util.stream.Collectors;   public class Solution {     static int n;     static int[][] map;     static int[][] dist;     static List<Integer> cafes;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int T = sc.nextInt();         /******************************          * DFS와 백트래킹을 이용해서 정사각형          * 직사각형이 이루어질 수 있는 모든 경우를          * 탐색하여 경로의 수를 구한다.          *******************************/         for(int t = 1; t <= T; t++) {             n = sc.nextInt();             map = new int[n][n];             for(int i = 0; i < n; i++) {                 for(int j = 0; j < n; j++ ) {                     map[i][j] =  sc.nextInt();                 }             }                          res = -1;             for(int i = 0; i < n; i++) {                 for(int j = 0; j < n; j++) {                     if(j==0) continue;                     vistied = new boolean[n][n];                     startx = i; starty = j;                     desert = new boolean[101];                     dfs(i, j, 0,0);                 }             }             System.out.println("#"+t+" "+res);             }              }     static int[] dx = {1,1,-1,-1};     static int[] dy = {-1,1,1,-1};     static int startx;     static int starty;     static boolean[][] vistied;     static boolean[] desert;     static int res;     public static void dfs(int x,int y,int curent,int cnt) {                  if(startx == x && starty == y && cnt !=0) {             res = Math.max(res,cnt);             return;         }         for(int i = curent; i <= curent+1; i++) {             if(i == 4) break;             if(startx == x && starty == y && i==1) break;             int nx = dx[i] + x;             int ny = dy[i] + y;             if(isBoundary(nx, ny) && !vistied[nx][ny] && !desert[map[nx][ny]]) {                 vistied[nx][ny] = true;                 desert[map[nx][ny]] = true;                 dfs(nx, ny,i,cnt+1);                 vistied[nx][ny] = false;                 desert[map[nx][ny]] = false;             }         }              }          public static boolean isBoundary(int nx,int ny) {         if(nx >= 0 && ny >= 0 && nx < n && ny < n)              return true;         return false;     }      }   Colored by Color Scripter

cs

 

참고 & 출처