[PS] 백준15684 : 사다리 조작(Java)

문제

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

15684번: 사다리 조작

---

풀이

DFS로 간단하게 풀 수 있는 문제

접근법

간단한 접근법으로 최대 3개까지의 사다리를 두었을 때의 모든 형태에서 유효성 검사를 수행하는 식으로 접근할 수 있음.

 

우선 입력으로 들어오는 모든 M개의 사다리를 배열에 저장

• 주의할 점으로 배열의 크기는 NM이 아닌 NH임

사다리를 표시할 때는 두가지 방법이 존재

1. 해당 좌표에만 1이라는 값으로 표시 → 오른쪽에서 왼쪽으로 가는 경우는 [r][c-1] 좌표를 확인
2. 해당 좌표와 이동하는 좌표인 [r][c+1]에도 표시

DFS 로직에 대해서는

1. 매개변수 : 사다리를 놓은 횟수
2. 기저조건(백트래킹)
   • 횟수가 3을 초과할 때는 탐색 종료
   • 횟수가 이미 구해진 최소값 res와 같거나 넘어갈 때는 탐색 종료
   • 유효성 검사를 성공할 경우에도 탐색 종료
3. 사다리 추가하는 로직
   • 맵 완전탐색을 통해 사다리가 놓여지지 않는 자리에 대해서 값 갱신 후 DFS 재귀호출
   • 재귀호출이 끝난 후 사다리를 제거함으로 백트래킹 수행

💡 주의점으로 사다리를 3개 다 놓았음에도 사다리를 추가로 탐색할 수 있기에 3개가 다놓였을 경우엔 탐색하지 않도록 로직 작성해야함! // 8% 혹은 9% 시간초과 발생이유

 

마지막으로는 해당 사다리에 대한 유효성 검사로직이 있는데

1부터 N개 까지의 사다리에 대해 사다리 유무를 판단 후 행(r)과 열(c)을 적절하게 조절하면서 마지막 도착지점 비교를 함으로써 로직 작성.

 

---

소스코드

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

//BOJ_15684 사다리 조작
public class Main {
    static int N, M, H, res;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();

        N = Integer.parseInt(st.nextToken()); //세로선
        M = Integer.parseInt(st.nextToken()); //가로선
        H = Integer.parseInt(st.nextToken()); //세로선마다 가로선을 놓을 수 있는 위치의 개수

        map = new int[H+2][N+2];
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = 1;
        }

        res = Integer.MAX_VALUE; //최소값 비교를 위한 초기화
        
        //사다리를 내려가는 시뮬레이션
        dfs(0);

        System.out.println(res == Integer.MAX_VALUE ? -1 : res); //최소값을 못 구한 경우 -1 출력
    }

    private static void dfs(int cnt) {
        //기저조건
        if(cnt > 3) return; //사다리 추가 개수가 3을 넘어가면 탐색종료
        if(cnt >= res) return; //백트래킹 : 최소값을 구하는 문제이기 때문에 최소값과 같거나 넘을 경우 탐색 종료

        boolean flag = true;
        for(int i=1; i<=N; i++) {
            flag = game(i);
            if(!flag) break;
        }

        if(flag) { //각각의 사다리가 자기번호로 도착할 수 있는 경우
            res = cnt;
            return;
        }

        //사다리게임이 실패할 경우 사다리 추가 로직
        if(cnt < 3) { //cnt가 3일 경우 탐색을 할 필요가 없음.(3일 때도 탐색하면 8% 시간초과 발생)
            for (int i = 1; i <= H; i++) {
                for (int j = 1; j < N; j++) {
                    if (map[i][j] != 1 && map[i][j - 1] != 1) { //사다리를 놓을 수 있는 자리에 대해
                        map[i][j] = 1;
                        dfs(cnt + 1);
                        //백트래킹
                        map[i][j] = 0;
                    }
                }
            }
        }
    }

    private static boolean game(int start) {
        int r = 1;
        int c = start;
        while(r <= H+1) {
            if(map[r][c] == 1) { //해당 좌표에 사다리가 존재할 경우 오른쪽으로 이동
                c += 1;
            }
            else if(map[r][c-1] == 1) { //해당 좌표의 왼쪽에 사다리가 있는 경우 왼쪽으로 이동
                c -= 1;
            }
            r += 1;
        }

        if(c == start) return true; //자기 번호에 맞게 도착한 경우
        return false;
    }
}

 

---

정리

• DFS 풀이한지가 좀 오래되었는데 리마인드 느낌으로 풀어보기 딱 적당했던 문제였던것 같음.
• 이번 문제를 풀이하면서 DFS 로직을 세울 때 중요한 점은 역시 불필요한 탐색에 대한 제거와 기저조건에 대한 정의를 하는 부분이라 생각함!
• 추가적으로 이번 풀이의 경우 1880ms로 상당히 느린 시간복잡도를 가진 풀이였는데 최적화에 대해서 추후에 추가해보면 좋을 것 같음!