[백준] 골드3 15684

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

완전탐색으로 구현을 하려 했지만...

시간복잡도를 계산해보니 시간초과가 날 것 같아서, 백트래킹을 사용해주었다.

 

흐름

임의로 사다리를 놓고, 사다리를 놓은 후 정답 조건을 만족하는지 확인하는 것이다.

 

주의할 점

사다리는 이어질 수 없다는 점

for (int i = here; i <= h; i++) {
            for (int j = 1; j <= n; j++){
                if(visited[i][j] != 0 || visited[i][j-1] != 0 || visited[i][j+1] != 0) continue;
                visited[i][j] = 1;
                go(i, cnt+1);
                visited[i][j] = 0; // 방문했던 곳 취소하기
            }
        }

 

중요한 곳

백트래킹을 위한 한정 조건

if(cnt > 3 || ret <= cnt){ // 이미 3개가 넘은 경우
  return;
}

이미 3개가 넘은 경우는 당연하거니와 정답을 만족하는 ret가 cnt보다 작거나 같은 경우는 더 탐색해줄 필요가 없다.

왜? 최솟값을 찾아야 하기 때문에, 가지를 쳐버리는 것이다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static int n;
    public static int m;
    public static int h;

    public static int[][] visited;

    public static int ret = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        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());

        visited = new int[34][34]; //

        for (int i = 0; i < m; i++) { // 사다리 탐지
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            visited[a][b] = 1; // indexing
        }

        go(1,0);

        System.out.println(ret == Integer.MAX_VALUE ? -1 : ret);

    }

    public static void go(int here, int cnt){
        if(cnt > 3 || ret <= cnt){ // 이미 3개가 넘은 경우
            return;
        }

        if(check()){ // 어라랏 도착 완료!
            ret = Math.min(ret,cnt);
            return;
        }

        for (int i = here; i <= h; i++) {
            for (int j = 1; j <= n; j++){
                if(visited[i][j] != 0 || visited[i][j-1] != 0 || visited[i][j+1] != 0) continue;
                visited[i][j] = 1;
                go(i, cnt+1);
                visited[i][j] = 0; // 방문했던 곳 취소하기
            }
        }

    }

    public static boolean check(){ // 시작 사다리와 도착 사다리가 같은 경우
        for (int i = 1; i <= n; i++) {
            int start = i;
            for (int j = 1; j <= h; j++) {
                if(visited[j][start] == 1){
                    start++;
                }else if(visited[j][start-1] == 1){
                    start--;
                }
            }
            if(start != i){ // 쭉 다 돌았는데도 일치하지 않는 경우
                return false;
            }
        }
        return true;
    }
}