반응형
1. 언어 : JAVA
2. 난이도 : Gold 4
3. 풀이
생각해보면 쉬운 문제다 2개의 함수의 구현이 필요하다.
DPS와 check 함수
dps 는 말그래도 depth 탐색 함수고
check는 사다리가 정답(1->1, 2->2, 3->3 .. N->N)인지 확인해주는 함수이다.
또한 map[][] 에 넣을때 오른쪽으로 갈수 있는 아이는 1, 왼쪽으로 갈수있는 아이는 -1로 저장하였다.
그리고 알아야 할 점은, 브루트포스이며 백트래킹을 사용한다.
소스코드는 다음과 같다.
4. 소스코드
import java.util.*;
import java.io.*;
public class Main {
public static BufferedReader br = null;
public static BufferedWriter bw = null;
public static int N = 0;
public static int M = 0;
public static int H = 0;
public static int result = 4;
public static void main(String [] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
String [] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
H = Integer.parseInt(input[2]);
int [][] map = new int[H+2][N+1];
for(int i=0; i<M; i++) {
input = br.readLine().split(" ");
int a = Integer.parseInt(input[0]);
int b = Integer.parseInt(input[1]);
map[a][b] = 1;
map[a][b+1] = -1;
}
dfs(1, 1, map, 0);
if(result <= 3) {
bw.write(result + "\n");
}
else {
bw.write("-1");
}
bw.flush();
}
public static void dfs(int y, int x, int [][] map, int ladder) throws IOException {
if(ladder > 3) {
return;
}
if(check(map)) {
result = Math.min(result, ladder);
}
for(int i=y; i<=H; i ++) {
for(int j=1; j<=N-1; j ++) {
if(map[i][j] == 0 && map[i][j+1] == 0) {
map[i][j] = 1;
map[i][j+1] = -1;
dfs(i, j, map, ladder+1);
map[i][j] = 0;
map[i][j+1] = 0;
}
}
}
}
public static int [][] copy(int [][] map) {
int [][] copy = new int[H+2][N+1];
for(int i=0; i<H+2; i++) {
for(int j=0; j<N+1; j++) {
copy[i][j] = map[i][j];
}
}
return copy;
}
public static boolean check(int [][] map) throws IOException {
int y = 0;
int x = 0;
for(int n=1; n<=N; n++) {
y = 1;
x = n;
while(true) {
if(map[y][x] == 1) {
y ++;
x ++;
}
else if (map[y][x] == -1) {
y ++;
x --;
}
else if(map[y][x] == 0) {
y ++;
}
if(y == H+1) {
if(x == n) {
}
else {
return false;
}
break;
}
}
}
return true;
}
}반응형
'Algorithm > DFS' 카테고리의 다른 글
| BOJ No.1043[거짓말] (0) | 2021.03.11 |
|---|
