SWEA :: [모의 SW 역량테스트] 등산로 조성

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

SW Expert Academy

SW 익스퍼트에서 지원해주는 A형 시험 모의고사

1. 가장 높은 봉우리를 먼저 저장한다.

   1-1. 이걸 먼저 안하면 마지막 테스트케이스에서 틀린다 .. ㅠㅠ(예시는 문제 댓글에 있다.

2. 공사를 통해 한칸의 봉우리를 깍을 수 있다.

   2-1. 여기서 중요한거 K가 주어지면 1 ~ K 마음대로 높이를 낮출 수 있다.

3. 4방 탐색하면서 등산로 길이를 측정한다.

4. 최장 등산로를 찾는다.

 

아이디어는 비슷한데 1등 코드와 시간 차이가 상당하다.. 하지만 1등 코드는 항상 어렵다 ㅠㅠㅠㅠ

아무튼 깎았을때 가장 높은 봉우리를 찾으면 틀리는게 이문제 함정인듯하다.

 

 

import java.util.*;
 
public class Solution_모의SW역량테스트_등산로조성 {
    static int map[][],n,top, 
                di[] = {-1,1,0,0}, dj[] = {0,0,-1,1}, ans;//사방 탐색
    static ArrayList<int[]> top_list, top_list2;
    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();
            int k = sc.nextInt();
            map = new int[n][n];
            top_list = new ArrayList<int[]>();
            top_list2 = new ArrayList<int[]>();
            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; i++) {
                for (int j = 0; j < n; j++) {
                    //가장 높은 봉우리 찾기
                    if(map[i][j] > top) {
                        top = map[i][j];
                    }
                }
            }
            //가장 높은 봉우리 저장하기
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(map[i][j] == top) {
                        top_list2.add(new int[] {i,j,1});
                    }
                }
            }
            
            ans = Integer.MIN_VALUE;
            //1. k만큼 봉우리 높이 낮추기
            for(int i = 0; i < n; i++) {
                for(int j=0; j<n; j++) {
                    for (int depth = 1; depth <= k; depth++) {
                        //depth만큼 공사 해보고
                        map[i][j] -= depth;
                        //탐색 하고
                        top = -1;// 최대 높이 봉우리 초기화
                        top_list.addAll(top_list2); // top_list 초기화
                        //등산로 길이 찾기
                        find_load();
                        //원상 복구
                        map[i][j] += depth;
                        
                    }
                }
            }
            System.out.println("#"+tc+" "+ans);
            
        }//tc end
    }//main end
    //2. 가장 높은 봉우리에서 탐색
    static void find_load() {
        while(!top_list.isEmpty()) {
            int temp[] = top_list.remove(0);
            int x = temp[0];
            int y = temp[1];
            int cnt = temp[2];
            for (int i = 0; i < 4; i++) {
                int nx = x + di[i];
                int ny = y + dj[i];
                if(nx>=0&& ny>=0 && nx<n&& ny<n
                        && map[x][y] > map[nx][ny] 
                                ) {
                    cnt++;
                    top_list.add(new int[] {nx,ny,cnt});
                    cnt--;
 
                }
            }
            ans = Math.max(cnt, ans);
        }
        
    }//find_load end
    
    
    
}