BOJ_15684_사다리 조작 (Java, C++)
BOJ_15684_사다리 조작 (Java, C++)
[Gold III] 사다리 조작 - 15684
성능 요약
메모리: 14652 KB, 시간: 112 ms
분류
백트래킹, 브루트포스 알고리즘, 구현
제출 일자
2025년 1월 28일 00:52:40
문제 설명
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.
초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.
위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.
사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.
위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.
 |
 |
| 1번 세로선 | 2번 세로선 |
사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세로선의 개수 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을 출력한다.
문제 풀이
코드
첫 Java 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static int N, M, H, a, b, res=-1;
static int[][] ladder;
static boolean flag;
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
// br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_15684_사다리조작/input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
ladder = new int[H+1][N+1];
if(M==0) {
bw.write(String.valueOf(0));
bw.flush();
bw.close();
br.close();
return;
}
else if(M==1) {
if(H==1) bw.write(String.valueOf(-1));
else bw.write(String.valueOf(1));
bw.flush();
bw.close();
br.close();
return;
}
for(int i=0; i<M; i++){
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
// a번째 높이에 b와 b+1을 연결
ladder[a][b] = 1; // 오른쪽으로 연결
ladder[a][b+1] = -1; // 왼쪽으로 연결
}
if(needMoreThan4()){
bw.write(String.valueOf(-1));
bw.flush();
bw.close();
br.close();
return;
}
if(check()) {
bw.write(String.valueOf(0));
bw.flush();
bw.close();
br.close();
return;
}
dfs(0, 1);
bw.write(String.valueOf(res));
bw.flush();
bw.close();
br.close();
}
private boolean needMoreThan4(){
int sum = 0;
for(int i=1; i<N; i++){
int cnt = 0;
for(int j=1; j<=H; j++){
if(ladder[j][i] == 1) cnt++;
}
// 한 사다리에서 우측으로 짝수개가 붙어있어야함.
if(cnt %2 != 0) sum++;
}
return sum >= 4;
}
private int goDown(int start) {
int r = 1;
int c = start;
while(r <= H) {
c += ladder[r][c];
r++;
}
return c;
}
private boolean check(){
for(int i=1; i<=N; i++){
if(goDown(i) != i) return false;
}
return true;
}
private void dfs(int cnt, int depth){
if(cnt > 3) return;
if(check()){
if(res == -1 || cnt < res) res = cnt;
return;
}
for(int i=depth; i<=H; i++){
for(int j=1; j<N; j++){
if(ladder[i][j] == 0 && ladder[i][j+1]==0){
if(j>=2 && ladder[i][j-1] == 1) continue; // 본인꺼 이전 -> 본인꺼 연결 x
if(j<N-1 && ladder[i][j+2] == -1) continue; // 본인꺼 다음 <- 다다음꺼 연결 x
ladder[i][j] = 1;
ladder[i][j+1] = -1;
dfs(cnt+1, i);
ladder[i][j] = 0;
ladder[i][j+1] = 0;
}
}
}
}
}
발전된 Java 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static int N, M, H, a, b, res=-1;
static int[][] ladder;
static boolean flag;
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
// br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_15684_사다리조작/input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
ladder = new int[H+1][N+1];
if(M==0) {
bw.write(String.valueOf(0));
bw.flush();
bw.close();
br.close();
return;
}
else if(M==1) {
if(H==1) bw.write(String.valueOf(-1));
else bw.write(String.valueOf(1));
bw.flush();
bw.close();
br.close();
return;
}
for(int i=0; i<M; i++){
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
// a번째 높이에 b와 b+1을 연결
ladder[a][b] = 1; // 오른쪽으로 연결
ladder[a][b+1] = -1; // 왼쪽으로 연결
}
if(needMoreThan4()){
bw.write(String.valueOf(-1));
bw.flush();
bw.close();
br.close();
return;
}
if(check()) {
bw.write(String.valueOf(0));
bw.flush();
bw.close();
br.close();
return;
}
for(int i=0; i<=3; i++) {
dfs(0, 1, i); // i는 목표 가로선 개수
if(res != -1) break; // 답을 찾으면 즉시 종료
}
bw.write(String.valueOf(res));
bw.flush();
bw.close();
br.close();
}
private boolean needMoreThan4(){
int sum = 0;
for(int i=1; i<N; i++){
int cnt = 0;
for(int j=1; j<=H; j++){
if(ladder[j][i] == 1) cnt++;
}
// 한 사다리에서 우측으로 짝수개가 붙어있어야함.
if(cnt %2 != 0) sum++;
}
return sum >= 4;
}
private int goDown(int start) {
int r = 1;
int c = start;
while(r <= H) {
c += ladder[r][c];
r++;
}
return c;
}
private boolean check(){
for(int i=1; i<=N; i++){
if(goDown(i) != i) return false;
}
return true;
}
private void dfs(int cnt, int depth, int line){ // line개만큼 둬야하는데 dfs돌리기
if(cnt > line) return;
if(cnt == line){
if(check()){
res = cnt;
return;
}
return;
}
for(int i=depth; i<=H; i++){
for(int j=1; j<N; j++){
if(ladder[i][j] == 0 && ladder[i][j+1]==0){
if(j>=2 && ladder[i][j-1] == 1) continue; // 본인꺼 이전 -> 본인꺼 연결 x
if(j<N-1 && ladder[i][j+2] == -1) continue; // 본인꺼 다음 <- 다다음꺼 연결 x
ladder[i][j] = 1;
ladder[i][j+1] = -1;
dfs(cnt+1, i, line);
if(res != -1) return;
ladder[i][j] = 0;
ladder[i][j+1] = 0;
}
}
}
}
}
C++ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/**
* Author: nowalex322, Kim HyeonJae
*/
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
int N, M, H, a, b, res = -1;
vector<vector<int>> ladder;
bool flag;
bool needMoreThan4() {
int sum = 0;
for (int i = 1; i < N; i++) {
int cnt = 0;
for (int j = 1; j <= H; j++) {
if (ladder[j][i] == 1) cnt++;
}
if (cnt % 2 != 0) sum++;
}
return sum >= 4;
}
int goDown(int start) {
int r = 1;
int c = start;
while (r <= H) {
c += ladder[r][c];
r++;
}
return c;
}
bool check() {
for (int i = 1; i <= N; i++) {
if (goDown(i) != i) return false;
}
return true;
}
void dfs(int cnt, int depth, int line) {
if (cnt > line) return;
if (cnt == line) {
if (check()) {
res = cnt;
return;
}
return;
}
for (int i = depth; i <= H; i++) {
for (int j = 1; j < N; j++) {
if (ladder[i][j] == 0 && ladder[i][j + 1] == 0) {
if (j >= 2 && ladder[i][j - 1] == 1) continue;
if (j < N - 1 && ladder[i][j + 2] == -1) continue;
ladder[i][j] = 1;
ladder[i][j + 1] = -1;
dfs(cnt + 1, i, line);
if (res != -1) return;
ladder[i][j] = 0;
ladder[i][j + 1] = 0;
}
}
}
}
void solve() {
cin >> N >> M >> H;
ladder.resize(H + 1, vector<int>(N + 1, 0));
if (M == 0) {
cout << 0 << endl;
return;
} else if (M == 1) {
if (H == 1)
cout << -1 << endl;
else
cout << 1 << endl;
return;
}
for (int i = 0; i < M; i++) {
cin >> a >> b;
ladder[a][b] = 1;
ladder[a][b + 1] = -1;
}
if (needMoreThan4()) {
cout << -1 << endl;
return;
}
if (check()) {
cout << 0 << endl;
return;
}
for (int i = 0; i <= 3; i++) {
dfs(0, 1, i);
if (res != -1) break;
}
cout << res << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1; // 기본적으로 1번의 테스트 케이스를 처리
// cin >> tt; // 테스트 케이스 수 입력 (필요 시)
while (tt--) {
solve();
}
return 0;
}
This post is licensed under
CC BY 4.0
by the author.