문제
https://www.acmicpc.net/problem/15684
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.
초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.
위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.
사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.
위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.
입력
첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)
둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.
가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.
가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.
입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.
출력
i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.
예제 입력 1
2 0 3
예제 출력 1
0
예제 입력 2
2 1 3
1 1
예제 출력 2
1
예제 입력 3
5 5 6
1 1
3 2
2 3
5 1
5 4
예제 출력 3
3
예제 입력 4
6 5 6
1 1
3 2
1 3
2 5
5 5
예제 출력 4
3
예제 입력 5
5 8 6
1 1
2 2
3 3
4 4
3 1
4 2
5 3
6 4
예제 출력 5
-1
예제 입력 6
5 12 6
1 1
1 3
2 2
2 4
3 1
3 3
4 2
4 4
5 1
5 3
6 2
6 4
예제 출력 6
-1
예제 입력 7
5 6 6
1 1
3 1
5 2
4 3
2 3
1 4
예제 출력 7
2
접근
정답이 3보다 크면 더 이상 탐색하지 않고 그냥 -1을 출력하고 끝내기 때문에 사다리를 0개 추가하는 경우부터 3개 추가하는 경우까지 완전 탐색을 해도 풀리는 문제였다.
구현
사다리 구현
사다리를 어떻게 구현해야 할지가 처음에 좀 막막했는데,
ladder[i][j]에 (i, j)에 도달한 경우 이동해야 할 다음 세로선의 위치를 저장하는 식으로 구현했다.
예를 들어, 위 사진에서 빨간 점은 세 번째 가로 점선과 두 번째 세로선이 교차하는 지점에 있으니 위치를 (3, 2)라고 표현할 수 있다. 그리고 이 지점에는 세 번째 세로선으로 연결되는 사다리가 놓여 있기 때문에 (3, 2) 위치에 도달하면 사다리를 타고 파란 점 위치, 즉 세 번째 세로선으로 이동하게 된다. 그러므로 ladder[3][2]에는 3이라는 값을 저장하는 것이다.
반면, 위 사진에서 노란 별이 있는 위치인 (4, 4)은 어떠한 사다리와도 연결되어 있지 않다. 그러니 이 위치에 도달하면 이동 없이 4번째 세로선에 그대로 머물게 된다. 그러므로 ladder[4][4]에는 4라는 값을 저장한다.
처음에는 사다리가 하나도 없다고 가정하고 모든 ladder[i][j] 값을 j로 초기화했고, 그 후 입력으로 주어진 초기 사다리 위치에 따라 이 ladder에 값을 저장했다.
사다리 타기 구현
이렇게 하면 가로 점선인 i의 값을 1에서부터 H까지 증가시켜가며 각 가로선 위치에서의 세로선 위치를 추적할 수 있었다.
문제에 나와 있던 위 그림을 예로 들어보자.
1번 세로선에서 사다리 타기를 시작하니 현재 위치를 저장하는 변수인 loc의 값을 1로 초기화한다.
그리고 i를 1부터 H(6)까지 증가시키며 다음과 같이 사다리 타기를 수행한다.
i = 1일 때 ladder[i][loc] = ladder[1][1] = 2, loc = 2 (2번 세로선으로 이동)
i = 2일 때 ladder[i][loc] = ladder[2][2] = 2, loc = 2 (2번 세로선 유지)
i = 3일 때 ladder[i][loc] = ladder[3][2] = 3 , loc = 3 (3번 세로선으로 이동)
i = 4일 때 ladder[i][loc] = ladder[4][3] = 3 , loc = 3 (3번 세로선 유지)
i = 5일 때 ladder[i][loc] = ladder[5][3] = 3 , loc = 3 (3번 세로선 유지)
i = 6일 때 ladder[i][loc] = ladder[6][3] = 3 , loc = 3 (3번 세로선 유지)i값을 H까지 증가시키며 순회가 완료된 후, 최종적으로 loc에 저장된 값(3)이 도착점이다.
이런 식으로 위 사다리 그림에서 1번에서 시작했을 때의 도착점이 3임을 알 수 있다.
가로선을 추가할 위치 탐색
도달 가능한 모든 위치 (row, col)에 대해, 어떤 위치에 도달했을 때 해당 위치에서 col + 1로 이동하는 가로줄을 (추가하는 것이 가능하다면) 추가해보고, 제거해 보는 방식으로 백트래킹을 해보면 된다.
이때, 사다리를 추가하는 것이 불가능한 경우는 다음과 같다.
- 해당 위치에 가로선이 이미 추가되어 있는 경우
- 가로선을 추가하면 이미 추가되어 있는 다른 가로선과 연속하게 되는 경우
위 두 경우를 어떻게 판별할까?
앞서 ladder[row][col]의 값을 col로 초기화했기 때문에, (row, col)에서 col + 1로 이동하는 가로줄이 존재하지 않는다면 ladder[row][col]의 값이 여전히 col일 것이다. 반면, 가로줄이 추가된 상태라면 사다리를 타고 다른 위치로 이동되어야 하기 때문에 ladder[row][col]의 값이 col과는 달라졌을 것이다.
따라서,
1. 해당 위치에 가로선이 이미 추가되어 있는 경우
-> ladder[row][col]의 값이 col + 1일 것이다.
2. 가로선을 추가하면 이미 추가되어 있는 다른 가로선과 연속하게 되는 경우
-> ladder[row][col - 1]의 값이 col과 같다면, 바로 왼쪽에 가로선이 이미 존재한다는 뜻이다.
ladder[row][col + 1]의 값이 col + 2와 같다면, 바로 오른쪽에 가로선이 이미 존재한다는 뜻이다.
위 두 경우에 해당한다면 사다리를 추가할 수 없으니 추가하지 않고 넘어가면 된다.
코드
import java.io.*;
import java.util.*;
class Main {
static int N;
static int H;
static int[][] ladder;
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());
int M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
ladder = new int[H + 1][N + 2];
// ladder 배열 초기화
for (int i = 0; i <= H ; i++) {
for (int j = 0; j <= N + 1; j++) {
ladder[i][j] = j;
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
ladder[a][b] = b + 1; // (a, b) -> (a, b + 1)
ladder[a][b + 1] = b; // (a, b + 1) -> (a, b)
}
// cnt: 추가할 가로줄 개수
for (int cnt = 0; cnt < 4; cnt++) {
// 가로줄을 cnt개 추가하는 모든 경우 탐색 -> 문제의 조건을 만족하는지 확인
addLine(cnt, 0, 1, 1);
}
// 프로그램이 종료되지 않았다면 System.exit(0);에 도달하지 않았다는 뜻.
// 문제의 조건을 만족시키는 경우를 찾지 못했다는 뜻이므로 -1을 출력.
System.out.println(-1);
}
// 백트래킹으로 가로줄을 추가할 위치 탐색
private static void addLine(int goal, int curr, int row, int col) {
if (row > H) {
return;
}
// 가로줄 추가가 끝난 경우
if (goal == curr) {
// 문제의 조건을 만족시키면 출력하고 프로그램 종료
if (isManipulationCompleted()) {
System.out.println(goal);
System.exit(0);
}
return;
}
if (ladder[row][col] != col + 1 // 이미 가로줄이 놓여 있는 게 아니라면
// 이미 놓여 있는 다른 가로줄과 연속하게 되는 게 아니라면
&& ladder[row][col - 1] != col && ladder[row][col + 1] != col + 2) {
// col -> col+1로 이동하는 가로줄을 추가하고 다음 위치로 이동
ladder[row][col] = col + 1;
ladder[row][col + 1] = col;
addLine(goal, curr + 1, (col == N)? row + 1 : row, (col == N)? 1 : col + 1);
// 가로줄 제거(원복)
ladder[row][col] = col;
ladder[row][col + 1] = col + 1;
}
// 해당 위치에 가로줄을 추가하지 않고 다음 위치로 이동
addLine(goal, curr, (col == N)? row + 1 : row, (col == N)? 1 : col + 1);
}
private static boolean isManipulationCompleted() {
// i: 사다리 타기 시작점 (세로선 번호)
for (int i = 1; i <= N; i++) {
int loc = i;
for (int j = 1; j <= H; j++) {
loc = ladder[j][loc];
}
// 시작점과 도착점이 하나라도 일치하지 않는다면 false 반환
if (loc != i) {
return false;
}
}
return true;
}
}
