SWEA 2105 디저트 카페

문제

대각선 방향으로 이동하여 디저트를 중복하지않고 최대한 많이 먹을 수 있는 경우를 구하라

풀이

<사전 세팅>
기존 상하좌우 격자 탐색과 같이 대각선 탐색할 dx, dy
static int[]dx= {-1,1,1,-1};// 상우 , 하우, 하좌,상좌
static int[]dy= {1,1,-1,-1};
<풀이>
=dfS를 이용하여 탐색한다.
1. 카페를 돌고 다시 원점으로 돌아오려면 위 아래 오른쪽 왼쪽을 모두 사용해야한다.
boolean 배열로 i번째 방향으로 갔는지 방문 체크를 한다. 단 한방향으로 연속해서 가는건 가능하기 때문에 before라는 변수에 이전 방향을 넣어주고 체크해준다.

2. 방문한 카페를 다시가면 안되기때문에 visited2 배열로 방문체크 해준다. 단 원점으로 다시돌아와야하기때문에 nx, ny가 원점인 경우는 예외처리 해준다

3. 원점으로 돌아오면 depth와 max를 비교한다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
    static class pos{
        int x,y;
        public pos(int x,int y) {
            this.x=x;
            this.y=y;
        }
    }
    static int[]dx= {-1,1,1,-1};// 상우 , 하우, 하좌,상좌
    static int[]dy= {1,1,-1,-1};
    static int MAX,N;
    static  int[][] arr;
    static Scanner scan=new Scanner(System.in);

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int t=scan.nextInt();
    
        
        for(int o=1;o<=t;o++) {
            MAX=-1;
            N=scan.nextInt();
            arr=new int[N][N];
            
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    arr[i][j]=scan.nextInt();
                }
            }
            //모든 점에서 탐색 시작
            
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    pos p=new pos(i,j);
                    boolean visited[]=new boolean[4];
                    boolean visited2[][]=new boolean[N][N];
                    boolean desert[]=new boolean[101];
                    visited2[p.x][p.y]=true;
                    sol(p.x,p.y,p,visited,visited2,-1,desert,0);
                }
            }
            
            System.out.println("#"+o+" "+MAX);
        }
        
    }
    public static void sol(int startx,int starty,pos p,boolean [] visited,boolean[][] visited2,int before,boolean []desert,int sum) {
        //자기 좌표로 다시 돌아올때까지      DX DY의 I VISITED 표시해서 한번씩만 쓰기
                                    // 한번만 쓰는게 아니라 
        if(p.x==startx&&p.y==starty&&sum>=4) {
            if(sum>MAX) {
                MAX=sum;
            }
            return;
        }
     // 상우 , 하우, 하좌,상좌
            for(int i=0;i<4;i++) {
                if(visited[i]&&i!=before)continue;          //이전 방향도 아니고 방문도 했을 때 continue
                

                int nx=p.x+dx[i];
                int ny=p.y+dy[i];
                
                if(nx>=0&&ny>=0&&nx<N&&ny<N&&!desert[arr[nx][ny]]) {// 안먹은 디저트를 파는 가게이고 격자를 벗어나지 않음
                   if(!visited2[nx][ny]||(nx==startx&&ny==starty)) {
                       sum++;          //합계
                       desert[arr[nx][ny]]=true;   //방문 표시
                       visited2[nx][ny]=true;
                       visited[i]=true;
                       sol(startx,starty,new pos(nx,ny),visited,visited2,i,desert,sum);
                       
                       //초기화
                       if(i!=before) {
                           visited[i]=false;
                       }
                       sum--;
                       desert[arr[nx][ny]]=false; 
                       visited2[nx][ny]=false;
                   }
                }               
            }
    }

}