SWEA[1949] - 등산로 조성

링크

SW Expert Academy

문제설명

• 완전탐색+DFS

문제풀이

• 모든 지형을 깎는 경우의 맵에 대해서(완전탐색)
• 모든 봉우리에서 시작해서 DFS 후 MAX 거리 구함

문제코드

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

public class Solution1949 {

    public static int Ans=0;
    public static int Temp=0;
    public static int N;
    public static int K;
    public static int[][] map;
    public static boolean[][] visit;
    public static int[][]dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };
    public static void DFS(int[] rc) {
        visit[rc[0]][rc[1]]=true;    //초기방문.

        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 && !visit[nr][nc] && map[rc[0]][rc[1]]>map[nr][nc]) {
                Temp++;
                visit[nr][nc]=true;    //방문
                DFS(new int[] {nr,nc});
                visit[nr][nc]=false;    //원상복구
                Temp--;
            }
        }
//        4방향 탐색해서 다 막혔을 경우
        Ans = Math.max(Ans, Temp);
        int debug=0;
        visit[rc[0]][rc[1]]=false;    //초기방문.원상복구
    }

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

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

        for(int test_case = 1; test_case <= T; test_case++)
        {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[N][N];
            visit = new boolean[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());
                }
            }


//            봉우리 찾기
            int max=-1;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    max = Math.max(max, map[i][j]);
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(map[i][j]==max) {                        //봉우리가 (i,j)
                        for (int t_i = 0; t_i < N; t_i++) {
                            for (int t_j = 0; t_j < N; t_j++) {    //map[t_i][t_j]를
                                for (int k = 0; k <= K; k++) {    //K이하만큼
                                    map[t_i][t_j]-=k;            //깎고
                                    DFS(new int[] {i,j});                    //탐색(i,j)
                                    map[t_i][t_j]+=k;            //원상복구
                                }
                            }
                        }
                    }
                    else {
                        continue;
                    }
                }
            }

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

아쉬운점

• 출발점 포함해서 ANS 계산하는것임
• 문제 제대로 안읽어서 출발점이 꼭대기만 포함하는건지 몰랐었음.
• BFS로도 풀 수 있음.

잘한점

• O(N) = (N^2*K){맵의 경우의 수}*(5){출발점 수}*(DFS탐색) = 8^2*5*DFS
  • 나름 할만하다고 생각해서 그냥 노가다 했음.
• DFS사용