SWEA[1861] - 정사각형 방[D4]

링크

SWEA[1861]

문제설명

• DFS

문제풀이

• DFS

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class Solution1861 {

    public static int Temp;
    public static int Temp_len;
    public static void DFS(int[] rc) {
        int nr=0;
        int nc=0;
        for (int d = 0; d < 4; d++) {
            nr = rc[0] + dir[d][0];
            nc = rc[1] + dir[d][1];
//            경계 안이고, 이동가능할 때
            if(nr>=0 && nr<N && nc>=0 && nc<N && map[rc[0]][rc[1]]+1==map[nr][nc]) {
                Temp++;
                DFS(new int[] {nr,nc});
                Temp--;
            }
        }
//        4방탐색 막혔을 경우
        Temp_len = Math.max(Temp_len, Temp);
    }

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };
    public static int Ans_len=Integer.MIN_VALUE;
    public static int Ans_map=Integer.MAX_VALUE;
    public static int[] Ans_ij;
    public static int N;
    public static int[][] map;
    public static void main(String args[]) throws Exception
    {
        System.setIn(new FileInputStream("res/swea/1861.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T;
        T=Integer.parseInt(br.readLine().trim());

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = Integer.parseInt(br.readLine().trim());
            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++) {
                    Temp_len=0;
                    Temp=0;
                    DFS(new int[] {i,j});    //Temp_len가 최대값
                    if(Ans_len<Temp_len) {
                        Ans_len=Temp_len;
                        Ans_map=map[i][j];
                        Ans_ij = new int[] {i,j};
                        int debug=0;
                    }
//                    길이같은방 여럿일 경우 작은거
                    else if(Ans_len==Temp_len && Ans_map>map[i][j]) {
                        Ans_map=map[i][j];
                        Ans_ij = new int[] {i,j};
                        int debug=0;
                    }
                }
            }

            System.out.println("#"+test_case+" "+Ans_map+" "+(Ans_len+1));

            /*
             * 초기화
             */
            Ans_len=Integer.MIN_VALUE; 
            Ans_map=Integer.MAX_VALUE;     

        }
    }
}

아쉬운점

• 출력조건 제대로 안봐서 i,j 좌표 출력하려고 Ans_ij변수 만듦
• 방 길이는 자신도 포함임 test_case보면 추측 가능 
  • Ans+1
• Visit check 안해줘도됨.
  • 한칸 올라갔으면 그 뒤로는 한칸 내려가야하기때문에 

잘한점

• DFS