# 유형 : 탐색, DFS

# 난이도 : 골드 5

# 문제를 이해 못해서 한참 걸렸다.. 그냥 가로세로선에 최대 3개 가로선을 추가하며 1에서 출발해서 1로(2->2, 3->3) 도착하는 사다리를 만드는 것이다. DFS의 전형적인 문제라고 할 수 있다. 0~3개의 가로선을 추가하며 지정한 가로선 개수와 추가한 사다리 개수가 일치할 때 반복문을 돌려 추가한 가로선의 개수로 1->1로 돌아오는지를 체크하면 된다.

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
63
64
65
66
67
68
69
70
71
72
package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p15684 {
    static final int maxY = 31, maxX = 11;
    static int N,M,H, result;
    static boolean check[][];
    static boolean isTrue = false;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        check = new boolean[maxY][maxX];
        
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            check[a][b] = true;
        }
        
        for(int i=0; i<=3; i++) {
            result = i;
            dfs(1,0);
            if(isTrue) {
                System.out.println(result);
                return;
            }
        }
        System.out.println("-1");
    }
    private static void dfs(int y, int cnt) {
        // TODO Auto-generated method stub
        if(cnt == result) {
            boolean isPossible = true;
            for(int i=1; i<=N; i++) {
                int col = i;
                for(int j=1; j<=H; j++) {
                    if(check[j][col])
                        col++;
                    else if(col>1 && check[j][col-1])
                        col--;
                }
                
                if(i!=col) {
                    isPossible = false;
                    break;
                }
            }
            if(isPossible)
                isTrue = true;
            return;
        }
        
        for(int i=y; i<=H; i++) {
            for(int j=1; j<N; j++) {
                if(!check[i][j-1&& !check[i][j] && !check[i][j+1]) {
                    check[i][j] = true;
                    dfs(i, cnt+1);
                    check[i][j] = false;
                }
            }
        }
        return;
    }
}
 
cs

+ Recent posts