SWEA[2105] - 디저트 카페

링크

SWEA[2105]

문제설명

• DFS

문제풀이

• DFS

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Solution2105 {

    public static int[][] dir = {
            {-1,-1},        //좌상
            {-1,1},            //우상
            {1,1},            //우하
            {1,-1}            //좌하
    };

    public static int Ans=0;
    public static int Temp=0;
    public static int sr=0;
    public static int sc=0;
    public static int[][] map;
    public static boolean[][] visit;
    public static ArrayList<Integer> list = new ArrayList<>();
    public static int N;


    public static void DFS(int[] rc, int now_dir) {

        list.add(map[rc[0]][rc[1]]);
        visit[rc[0]][rc[1]] = true;
        Temp++;

        int nr;
        int nc;
//        그대로 진행하거나, 꺾거나
        for (int d = 0; d < 2; d++) {
//            dir이 4미만임(4개까지임)
            if(now_dir+d<4) {
                nr = rc[0] + dir[now_dir+d][0];
                nc = rc[1] + dir[now_dir+d][1];
            }
            else {
                continue;
            }
//            경계 안에서
            if (nr>=0 && nr<N && nc>=0 && nc<N) {
//                방문 가능할 때(방문하지않았고, 디저트가 안겹칠 때)
                if(!visit[nr][nc] && !list.contains(map[nr][nc])) {
                    DFS(new int[] {nr,nc},now_dir+d);
//                    원상복구
                    list.remove(list.size()-1);
                    visit[nr][nc] = false;
                    Temp--;
                }
//                cycle 도달함
                else if(now_dir+d==3 && nr==sr && nc==sc) {
//                    System.out.println("["+nr+","+nc+"]");
                    Ans = Math.max(Ans, Temp);
                    return;
                }
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/2105.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    visit = new boolean[N][N];
                    list.clear();
                    Temp=0;
                    sr=i;
                    sc=j;
                    DFS(new int[] {i,j},0);
                }
            }

            if(Ans<=1)Ans=-1;
            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=0;
        }//end test_case
    }//end main
}//end class

아쉬운점

• 끝나는 조건
  • 방향과 true만 따지면 중간에 끊어도 끝날때로 고려됨
  • sr,sc로 지정하고 도달했을때가 끝날때임
• 사이클 돌 때 방향꺾는걸 dir+(0,1) 할 때 경계검사 안함
  • dir이 4미만이어야 함(4개까지임)
• 모든 좌표에 대해서 DFS 돌리는 데 visit 초기화 안해서 탐색못함
• 완탐인데 필요이상으로 탐색하는 경우도 있긴 함. 좌상->우상3번->우하3번->좌하(벽끝까지) 가는경우

잘한점

• DFS
• 대각선 이동 및 한 사이클 도는 것을 dir +(0,1)로 해결했음.
  • 무조건 현재 방향으로 가거나 오른쪽으로 꺾거나