백준 15684번
https://www.acmicpc.net/problem/15684
문제
사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.
i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.
생각하기
동작
사다리의 선을 어떻게 표현하는지가 가장 중요하다
사다리선 자체를 2차원 배열로 만들어서 행렬로 표시한다고 생각하면 된다.
배열의 값이 1일 경우 우측으로 이동하고 2일 경우 좌측으로 이동한다.
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; // 우측으로 이동
arr[x][y+1] = 2; // 좌측으로 이동
}백트래킹은 선을 만들면서 탐색하기 때문에 1과 2를 넣었던 배열 자리를 다시 0으로 만들어주면 백트래킹 탐색을 구현할 수 있다.
for(int i=x; i<H+1; i++) {
for(int j=1; j<N; j++) {
if(arr[i][j] == 0 && arr[i][j + 1] == 0) {
arr[i][j] = 1;
arr[i][j+1] = 2;
DFS(i, depth+1);
// 가로선 백트래킹
arr[i][j] = 0;
arr[i][j+1] = 0;
}
}
}
static boolean check() {
for(int i=1; i<=N; i++) {
int x = 1, y = i;
for(int j=0; j<H; j++) {
if(arr[x][y] == 1) {
y++;
}
else if(arr[x][y] == 2) {
y--;
}
x++;
}
if(y != i) return false;
}
return true;
} // End of checkcheck메소드는 만들어진 사다리 배열이 정답이 될 수 있는지 확인하는 메소드 이다.
여기서 true를 반환하게 되면 정답이 되기 때문에 finish를 true로 만둘고 종료할 수 있다.
코드
Java
import java.util.*; import java.io.*; public class Main { static int N, M, H, ans; static boolean visit[][]; static int arr[][]; static boolean finish = false; public static void main(String[] args) throws Exception { 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; // 우측으로 이동 arr[x][y+1] = 2; // 좌측으로 이동 } for(int i=0; i<=3; i++) { ans = i; DFS(1, 0); if(finish) break; } System.out.println(finish ? ans : -1); } // End of main static void DFS(int x, int depth) { // 재귀 탈출 조건 if(finish) return; // 재귀 탈출 조건 if(ans == depth) { if(check()) { finish = true; } return; } for(int i=x; i<H+1; i++) { for(int j=1; j<N; j++) { if(arr[i][j] == 0 && arr[i][j + 1] == 0) { arr[i][j] = 1; arr[i][j+1] = 2; DFS(i, depth+1); // 가로선 백트래킹 arr[i][j] = 0; arr[i][j+1] = 0; } } } } // End of DFS static boolean check() { for(int i=1; i<=N; i++) { int x = 1, y = i; for(int j=0; j<H; j++) { if(arr[x][y] == 1) { y++; } else if(arr[x][y] == 2) { y--; } x++; } if(y != i) return false; } return true; } // End of check } // End of Main class
Kotlin
import java.util.* import java.io.* private lateinit var arr : Array<Array<Int>> private var N = 0; private var M = 0; private var H = 0 private var result = 0 private var finish = false fun main() { val br = BufferedReader( InputStreamReader(System.`in`) ) var st = StringTokenizer(br.readLine()) N = st.nextToken().toInt() M = st.nextToken().toInt() H = st.nextToken().toInt() arr = Array(H+1){Array(N+1) {0}} for(i in 0 until M) { st = StringTokenizer(br.readLine()) var x = st.nextToken().toInt() var y = st.nextToken().toInt() arr[x][y] = 1 arr[x][y+1] = 2 } // i=0은 사다리를 하나도 추가하지 않았을 때, 정답이 될 수 있는지를 체크 // 만약, 정답이 3보다 큰 값이면 -1을 출력한다. -> 사다리 개수가 3개를 초과할 경우 더 이상 탐색할 필요가 없음 for(i in 0..3) { result = i DFS(1, 0) // 무조건 1부터 시작 if(finish) break // 문제가 해결되어서 끝내도 된다를 알 수 있는 변수 finish } if(finish) { print(result) } else { print(-1) } } // End of main private fun DFS(x : Int, depth : Int) { //println("DFS(${x} , ${depth})") if(finish) return if(result == depth) { if(check()) { finish = true } return } for(i in x..H) { for(j in 1 until N) { if(arr[i][j] == 0 && arr[i][j+1] == 0) { arr[i][j] = 1 arr[i][j+1] = 2 DFS(i, depth+1) // 백트래킹 // 만들어 놓은 사다리를 다시 돌려놓음 arr[i][j] = 0 arr[i][j+1] = 0 } } } } // End of DFS // 만들어진 사다리가 정답이 될 수 있는지 체크하는 함수 private fun check() : Boolean { for(i in 1..N) { var x = 1; var y = i for(j in 0 until H) { if(arr[x][y] == 1) { // 1이면 우측으로 가기때문에 y를 1증가시킴 y++ } else if(arr[x][y] == 2) { // 2이면 좌측으로 가기때문에 y를 1감소시킴 y-- } x++; // 다음 행으로 넘어감 } if(y != i) return false // 출발한 i와 마지막 도착지 인 y의 값이 다를 경우, 출발지와 도착지가 다름을 의미하기 때문에 정답이 될 수 없음 } return true } // End of check
