[BOJ] 15684 - 사다리 조작
📌 문제 정보
- 문제 번호: BOJ 15684
- 문제 이름: 사다리 조작
- 난이도: Gold
- 분류: 백트래킹
🧩 문제 요약
- 주어지는 입력
n = 사다리 타기의 세로선
h = 사다리 타기의 가로선
m = 초기 사다리 게임에서 존재하는 가로선
- a = 주어진 가로선의 행 번호
- b = 주어진 가로선의 열 번호
만약 a행 b가 주어진다면
a행 b열과 b+1열이 가로선을 통해 연결되어 있음- 무엇을 구해야 하는지
가로선을 **최대 3번**까지 놓을 수 있을 때,
모든 사다리의 출발점과 도착점의 번호를 같게 하는 가로선을 놓는 횟수의 최솟값
- 중요한 조건 및 제한 사항
1. 주어지는 입력에서 인덱스는 1부터 시작
2. 가로선이 서로 연속하는 경우는 없음.
3. 정답이 3보다 크거나 불가능한 경우 -1 출력💡 접근 아이디어
- 처음 떠올린 방법
이 문제를 보고 수학 유형의 알고리즘인 것 같아 규칙을 파악하고자 했다.
해당 문제의 테스트 케이스 1, 2, 3을 생각한 알고리즘으로 해결할 수 있다고 판단했고
아래와 같은 규칙의 알고리즘을 고안하게 되었다.
1. 출발지와 가장 먼 거리인 지점을 찾는다.
2. 도착지에 담긴 사다리번호 위에서 부터 다리를 놓을 곳을 탐색한다.
3. 만약 다리를 놓을 수 없다면 아래로 1칸씩 이동한다.
4. 다리를 놓을 수 있는 경우 다리를 놓는다.
5. 모든 번호가 제자리에 갈 때까지 1에서 4의 과정을 반복한다.
해당 알고리즘으로 문제에서 공개된 테스트 케이스 1~6을 통과할 수 있었지만
7번 테스트 케이스를 보자마자 이 알고리즘으로는 절대 풀 수 없겠구나를 확신하여
다른 알고리즘을 생각하게 되었다.- 다음으로 선택한 방법
다음으로 선택한 방법은 백트래킹이었다.
해당 방법을 선택한 이유는
우선 사다리를 놓을 수 있는 위치 중 최대 3곳을 선택한다는 점에서 조합을 생각했다.
또한 사다리를 놓을 수 있는 위치 중 절대 도달할 수 없는 한 점을 조합에 포함 시켰을 때
해당 경로를 선택안한 경우로 되돌아가야 한다고 생각했기 때문에 백트래킹을 선택하였다.
🛠️ 해결 전략
구현 흐름을 단계별로 정리합니다.
- 상태 정의
먼저 주어진 h 와 n 길이를 h * (n-1) 크기의 이차원 배열로 생성하였다.
그 이유는 바로 주어지는 값은 점을 기준으로 입력이 주어졌는데 가로선을 놓을 수 있는 위치는
열과 열 사이기 때문에 h * (n-1) 배열로 만드는 것이 더 효과적이라고 생각했다.- 핵심 로직(점화식 / 이동 규칙)
1.
사다리를 놓을 위치를 정하는 방법은 map[h][n-1] 배열 전체를 탐색해 나가면서
현재 위치한 지점과 양 옆에 사다리가 없다면 선택 후 depth에 1더하여 처리하는 DFS 방식을 채택하였다.
2.
이 문제는 조건을 만족하는 경우의 depth 최솟값을 구하는 문제이기 때문에
0부터 3까지 for문을 통해 전체 알고리즘을 동작하게 했으며
해당 분기에서 조건을 통과했다면 결과를 출력하게 설계했다.
- 종료 조건
열 우선탐색을 사용하여 i번째 열이 0부터 (h-1)행까지 거치면서
값이 그대로 유지가 되면 분기를 탈출하게 설계했다.⚠️ 주의할 점
풀이 중 헷갈리거나 실수하기 쉬운 부분입니다.
- 방문 처리 시점
처음에는 map[r][c]를 방문하면 map[r][c-1] 과 map[r][c+1]을 -1로 설정하여
분기를 조금 더 빠르게 동작할 수 있도록 설계했었는데 초기에 설정한 -1과
분기를 거치면서 생성한 -1을 구분할 방법이 없어 해당 코드가 실패하게 되었다.- 조건 분기 순서
// 조건문 안에서 조건 분기를 착각하여 예측하지 못한 결과가 나오게 되었다.
/*
3-1. 코드
모든 사다리가 제자리를 찾는 경우가 있음에도
재귀가 반복되면서 isFinish 값이 덮여짐
*/
if (depth == maxDepth) {
isFinish = checkMap();
}
/*
3-2. 코드
재귀를 반복할 수 있는 횟수가 최대에 도달하더라도
checkMap이 false인 경우 탐색을 이어나감
*/
if (depth == maxDepth && checkMap()) {
isFinish = true;
}
if (depth == maxDepth) {
if (checkMap())
isFinish = true;
}✅ 코드
package ac.p15684;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int [][] map;
static int n, m, h;
static boolean isFinish =false;
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());
map = new int [h][n-1];
// 이미 놓인 사다리 위치 입력받기
for (int i=0;i<m;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;
// a행 b열과 b+1열은 연결되어있음을 표시
map[a][b] = 1;
}
// 사다리 놓는 갯수를 0부터 탐색하며 찾은 경우 더 이상 탐색하지 않음
for (int maxDepth=0;maxDepth<4;maxDepth++) {
dfs(0, 0, 0, maxDepth);
if (isFinish) {
System.out.println(maxDepth);
break;
}
}
if (!isFinish) System.out.println(-1);
}
static void dfs(int r, int c, int depth, int maxDepth) {
if (depth == maxDepth) {
if (checkMap())
isFinish = true;
} else {
if (isFinish) return;
for (int i=r;i<h;i++) {
for (int j=c;j<n-1;j++) {
if (map[i][j] != 0) continue;
if (j-1 >= 0 && map[i][j-1] != 0) continue;
if (j+1 < n-1 && map[i][j+1] != 0) continue;
map[i][j] = 1;
dfs(i, j+1, depth+1, maxDepth);
map[i][j] = 0;
}
c = 0;
}
}
}
static boolean checkMap() {
// 행 우선탐색
for (int c=0;c<n;c++) {
int pos = c;
for (int r=0;r<h;r++) {
// 왼쪽에 다리가 있으면 왼쪽으로 이동
if (pos-1 >= 0 && map[r][pos-1] == 1)
pos--;
// 오른쪽에 다리가 있으면 오른쪽으로 이동
else if (pos < n-1 && map[r][pos] == 1)
pos++;
}
if (pos != c) return false;
}
return true;
}
}
돈 많이 벌래