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

SWEA] 1949. (모의 SW 역량테스트) 등산로 조성

SWEA 1949. (모의 SW 역량테스트) 등산로 조성
문제의 저작권은 SWEA에 있습니다

---

문제의 핵심은 위 규칙 중 3번을 고려하는 것.
처음에는 bfs에 조건을 걸고 산을 깎을 때 dfs로 확인하는 방법을 고려했으나,
결국 dfs 백트래킹으로 하는 것이 확실하고 직관적으로 보여 수정해서 다시 푼 문제.

dfs + 백트래킹 방법을 처음부터 적용했더라면, 30분-1시간내에 풀었겠지만,
방황하다가 시간을 조금 더 소요했던 문제였다.

코딩하기 전, 여러 상황을 고려하고 글로 써보고 타이핑을 진행하지만 아직도 많이 부족하다.
그래도 dfs 백트래킹을 적용해서 한번에 성공했을 때는 나름 기뻤던 문제.

dfs 백트래킹을 연습하기에 좋은 문제.

import java.util.ArrayList;
import java.util.Scanner;
 
public class swea_등산로조성 {
    static class POS {
        int r;
        int c;
        int cnt;
        int chance;
 
        public POS(int r, int c, int chance, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
            this.chance = chance;
        }
    }
 
    static int N;
    static int K;
    static int[][] map;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    static int ans;
    static boolean[][] visited;
    
    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();
            K = sc.nextInt();
            map = new int[N][N];
            visited = new boolean[N][N];
            ans = 0;
            int max = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = sc.nextInt();
                    max = Math.max(max, map[i][j]);
                }
            }
 
            ArrayList<POS> startlist = new ArrayList<POS>();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == max) {
                        startlist.add(new POS(i, j, 1, 1));
                    }
                }
            }
 
            for (int i = 0; i < startlist.size(); i++) {
                visited[startlist.get(i).r][startlist.get(i).c]=true;
                dfs(startlist.get(i));
                visited[startlist.get(i).r][startlist.get(i).c]=false;
            }
            System.out.println("#" + tc + " " + ans);
        } // end test cases
    }// end main
 
    static void dfs(POS p) {
        ans = Math.max(ans, p.cnt);
        for(int i=0; i<4; i++) {
            int nr = p.r + dr[i];
            int nc = p.c + dc[i];
            if(nr<0 || nc <0 || nr >= N || nc>=N) continue;
            if(visited[nr][nc])continue;
            if(map[p.r][p.c] > map[nr][nc]) {
                visited[nr][nc]=true;
                dfs(new POS(nr,nc,p.chance, p.cnt+1));
                visited[nr][nc]=false;
            }
            if(p.chance ==1) {
                for(int h=1; h<=K; h++) {
                    if(map[p.r][p.c]>map[nr][nc]-h) {
                        int origin = map[nr][nc];
                        map[nr][nc] = map[nr][nc]-h;
                        visited[nr][nc]=true;
                        dfs(new POS(nr,nc,0,p.cnt+1));
                        map[nr][nc]=origin;
                        visited[nr][nc]=false;
                    }
                }
            }
        }//end for
    }//end dfs
}