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

2105.(모의 SW 역량테스트) 디저트 카페

2105. (모의 SW 역량테스트) 디저트 카페
문제의 저작권은 SWEA에 있습니다

대각선을 잘 그리면 되는 문제.
삼성공채 SW 역량테스트를 준비하기 전날에 풀까말까 하다가 안풀고 다른 구현문제를 풀었었는데,

이 문제를 풀고 시험을 봤다면 시간이 부족하지는 않았을텐데 라는 후회를 하게 만든 문제.

여하튼, 나중에 이 문제를 풀때 역시 2019 하반기 공채 삼성 SW역량테스트 오전 1번문제를 풀듯이 풀어봤는데,

생각보다 빡빡하고 시간도 오래걸렸다. (모든 경우의 수를 조건문으로 고려하는 구현방법으로 풀어서)

단순히, 방향과 프루닝(가지치기), 조건을 건 백트래킹을 사용하면 굉장히 파워풀하고 직관적이며 간단한 코드를 짤 수 있다.

dfs 백트래킹 짱짱

혹시 비슷한 문제를 풀어보고 싶으시다면 아래 링크를 들어가서 풀어보세요!
삼성 SW역량테스트 오전 1번문제 입니다.
백준 - 게리맨더링2

import java.util.Scanner;
 
public class Solution {
     
    static int[][] map;
    static int[] dr = {1,1,-1,-1};
    static int[] dc = {1,-1,-1,1};
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int tc=1; tc<=T; tc++) {
            N = sc.nextInt();
            map = new int[N][N];
            ans = -1;
            for(int i=0; i<N; i++) for(int j=0; j<N; j++) map[i][j] = sc.nextInt();
             
            for(int i=0; i<N-2; i++) {
                for(int j=1; j<N-1; j++) {
                     
                    recur(i,j, i ,j , new boolean[101], 0, 1);
                }
            }
            System.out.println("#"+tc+" "+ans);
        }//end test cases
    }//end main
     
    static int ans;
    static void recur(int tr, int tc, int nr, int nc, boolean[] desert, int dir, int sum) {
        desert[map[nr][nc]]=true;
        // 방향 초과(0~3)
        if(dir>3) return;
        // 각 방향에 따른 좌표 변화
        nr += dr[dir];
        nc += dc[dir];
         
        //돌아서 원래 점으로 돌아옴
        if(nr==tr && nc==tc) {
            ans = Math.max(ans, sum);
            return;
        }
         
        // 가장 위에 찍힌 점보다 더 위에 올라갈 수 없음.(작을 수 없음)
        if(nr<tr) return;
        if(nr<0 || nc<0 || nr> N-1|| nc>N-1) return;
         
        //이미 방문했던 디저트 가게라면 return
        if(desert[map[nr][nc]]) return;
         
        desert[map[nr][nc]]=true;
        recur(tr,tc,nr,nc,desert, dir, sum+1);
        recur(tr,tc,nr,nc,desert, dir+1, sum+1);
        desert[map[nr][nc]]=false;
    }//end recur 
}