백준 15684 [사다리 조작]

구현하기 너무 귀찮은 문제 중 하나이다...

기존 문제와는 다르게 x, y가 바뀌었고, 그에따라 구현하기 너무 귀찮은 문제이다..

쉽게 생각하면 쉽다. DFS로 구현을 했다

(1,1) 좌표부터 (n,m)좌표까지 가로선을 설치하거나 설치하지 않거나 하며 최소값을 구하면 된다.

1. 종료조건

가로선을 3개보다 많이 설치했을 경우, 또는 (n,m)에 도착했을 경우

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

import java.util.*; public class Main {       static int n,m,h,ans=4;     static boolean[][] a;     static boolean check(boolean[][] a) {         for(int i=1; i<=m; i++) {             int start = i, end = i;             for(int j=1; j<=n; j++) {                 if(a[j][end]) {                     ++end;                     continue;                 }                 if(end==1) continue;                 if(!a[j][end]) {                     if(a[j][end-1]) --end;                 }             }             if(start!=end) return false;         }         return true;     }     static void go(int x, int y, int cnt, boolean[][] a) {         if(y==m+1) {             ++x;             y=1;         }         if(cnt==3 || (x==n && y==m)) {             if(check(a))                 ans = Math.min(ans, cnt);             return;         }                   //설치 안하거나         go(x, y+1, cnt, a);                   //인접한 가로선이 있을 때         if(y==m || a[x][y] || (y!=1 && a[x][y-1]) || a[x][y+1]) return;                   //설치하거나         a[x][y] = true;         go(x, y+1, cnt+1, a);         a[x][y] = false;     }     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         m = in.nextInt();         h = in.nextInt();         n = in.nextInt();         a = new boolean[n+2][m+2];                   for(int i=0; i<h; i++) {             int x = in.nextInt();             int y = in.nextInt();             a[x][y] = true;         }                   go(1,1,0,a);         System.out.println(ans==4?-1:ans);         in.close();     } }