15684번 사다리 조작
난이도
골드 3
문제 설명
https://www.acmicpc.net/problem/15684
문제
입력
첫째 줄에 세로선의 개수 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
2 1 3
1 1
예제 입력 3
5 5 6
1 1
3 2
2 3
5 1
5 4
예제 출력 3
3
요구사항
이 문제는 사다리 게임의 결과를 원하는 형태로 조작하기 위해 가로선을 추가하는 문제이다.
- 세로선 개수 N, 가로선 개수 M, 가로선을 놓을 수 있는 개수 H
- 가로선은 인접한 두 세로선을 연결하며, 연속하거나 인접하게 놓을 수 없다.
- i번 세로선에서 출발하였을 때 i번 세로선에 도착해야 한다.
- 추가할 가로선의 최솟값을 구해야하며, 불가능하거나 추가한 가로선의 수가 3개를 넘기면 -1을 출력한다.
접근 방식
(H+1)*(N+1) 크기의 2차원 배열을 만들어 사다리 게임을 구현하였다. 문제 해결의 핵심은 가로선을 어디에 추가할지 결정하는 것이다. 이중 반복문으로 탐색한다면 비효율적으로 탐색하기 때문에 가로선을 추가할 후보 위치를 미리 ArrayList에 담아놓고, 조합으로 탐색하는 방식을 사용하여 한 번의 반복문으로 가로선을 추가할 수 있었다.
또한, 가로선은 인접하거나 연속으로 놓을 수 없기 때문에, 현재 후보 위치가 배열 범위 안에 위치하는지, 인접한 위치에 가로선이 존재하지 않는지 검사하는 함수도 필요하다.
가로선을 추가한 후, 해당 배열의 상태를 바탕으로 사다리 게임 시뮬레이션을 하는 함수가 필요하다. 현재 위치가 (x, y)라고 가정하자. (x, y)에 가로선이 있다면 y+1로 이동하고, (x, y-1) 위치에 가로선이 있다면 y-1로 이동하여 시뮬레이션을 구현하였다.
마지막으로 가로선은 3개까지만 추가할 수 있기 때문에, 0~3개까지만 시도하고 종료하도록 하였다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Point{
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main{
static int n, m, h, answer = Integer.MAX_VALUE;
static int[][] arr;
static ArrayList<Point> al = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
arr = new int[h+1][n+1];
for(int i=0; i<m; i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y] = 1;
}
for(int i=1; i<=h; i++){
for(int j=1; j<n; j++){
if(arr[i][j] == 1) continue;
al.add(new Point(i, j));
}
}
// 3이 넘어가면 더 이상 확인할 필요 X.
for(int i=0; i<=3; i++){
comb(0, i, 0);
}
System.out.println((answer==Integer.MAX_VALUE)?-1:answer);
}
// 가로선 추가
static void comb(int L, int cnt, int x){
if(L == cnt){
if(simulation()){
answer = Math.min(answer, cnt);
}
}
else{
for(int i=x; i<al.size(); i++){
Point now = al.get(i);
if(canPos(now.x, now.y)){
arr[now.x][now.y] = 1;
comb(L+1, cnt, i+1);
arr[now.x][now.y] = 0;
}
}
}
}
// 세로선의 결과가 변하지 않는 지 시뮬레이션
static boolean simulation(){
for(int col=1; col<=n; col++){
int pos = col;
for(int row=1; row<=h; row++){
if(pos<n && arr[row][pos] == 1){
pos = pos+1;
}
else if(pos>1 && arr[row][pos-1] == 1){
pos = pos-1;
}
}
if(col != pos) return false;
}
return true;
}
// 사다리를 놓을 수 있는 위치인지 확인
static boolean canPos(int x, int y){
if(y<1 || y>=n) return false;
if(arr[x][y] == 1) return false;
if(y+1 < n && arr[x][y+1]==1) return false;
if(y-1 >= 1 && arr[x][y-1]==1) return false;
return true;
}
}
느낀점
문제를 읽고 난 뒤, 가로선을 추가한 후 해당 상태에서 사다리 게임 시뮬레이션하여 i번 세로선이 i번에 도착하는지 검사하고, 이를 통해 추가해야 할 가로선의 최솟값을 구해야 한다고 생각했다.
처음에는 사다리판의 가로선을 어떻게 구현해야할지 고민이 많았다. 결국, 2차원 배열을 선언하여 사다리판을 표현하는 방식으로 해결하였다. 현재 세로선에 가로선이 연결되어 있다면 열을 +1 이동하고, 왼쪽에 가로선이 연결되어 있다면 열을 -1 이동하는 것으로 시뮬레이션을 구현하였다.
또한, 가로선 추가할 후보 위치를 선택하는 과정에서 단순히 이중 반복문을 돌려 모든 경우를 다 탐색하는 것 보다, 조건을 잘 설계하여 후보군을 줄이고 복잡도를 낮춰 효율적으로 구현하는 것이 매우 중요한 핵심이라는 것을 느낄 수 있었다.
