15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선
www.acmicpc.net
문제
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.
초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.
위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.
사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.
위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다.
입력
사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, 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을 출력한다.
예제 입력 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
풀이 1. (틀린 코드 - 시간 초과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int n, h, m, ans = -1;
static int[][] map = null;
static boolean[][] check = null;
// 위는 검사하지 않는다. 양 옆에 1 있는지 먼저 체크. 없으면 아래로
static int[] rArr = {0, 0}; // 좌 우
static int[] cArr = {-1 ,1}; // 좌 우
public static boolean isPossible() {
// i열이 i열로 도작하는지 체크
// 여기서 결국 탐색 한 번 다 돌려야 할 듯?
for(int i = 1; i <= n; i++) {
check = new boolean[h+2][n+1]; // 가로선 계속 타는 무한루프 막기 위한 체킹
check[1][i] = true;
int endCol = search(1, i);
if(endCol != i) {
return false;
}
}
return true;
}
public static int search(int r, int c) {
// 내가 1이면 내 오른쪽 열로 이동
// 내 왼쪽이 1이면 내 왼쪽으로 이동
// 내 아래 행으로는 항상 이동 가능 (우선순위는 열 이동에 있음)
// 가로선은 H행이 끝이지만 완료 검사는 H+1행에서 해야 한다
if(r == h+1) { // 끝에 도착했으면 시작과 동일한지 체크
int endCol = c;
return endCol;
}
for(int i = 0; i < 2; i++) { // 좌우 검사
int nr = r + rArr[i];
int nc = c + cArr[i];
if(0 < nr && nr <= h && 0 < nc && nc <= n && !check[nr][nc]) { // H행 N열 범위 체크
if(i == 0 && map[nr][nc] == 1) { // 좌
check[nr][nc] = true;
check[nr+1][nc] = true; // 어차피 연속으로 열 이동 불가. 열 이동한 이후엔 어차피 아래로 가야함
return search(nr+1, nc);
}
if(i == 1 && map[r][c] == 1) { // 우
check[nr][nc] = true;
check[nr+1][nc] = true;
return search(nr+1, nc);
}
}
}
check[r+1][c] = true;
return search(r+1, c); // 하
}
public static void dfs(int r, int c, int deptNow, int dept) {
if(isPossible()){
if(ans == -1) {
ans = deptNow;
}else {
ans = Math.min(ans, deptNow);
}
return;
}
if(deptNow == dept) {
return;
}
// 이제 여기서 가로실선을 하나씩 놓자
for(int i = r; i <= h; i++) { // 이전 행은 다시 확인할 필요 없음
for(int j = 1; j < n; j++) { // 마지막 열에는 놓을 수 없다
// 0열은 사용하지 않는 열이고 n열은 애초에 1이 올 수 없는 열이므로 범위 문제 없음
if(map[i][j] == 0 && map[i][j-1] == 0 && map[i][j+1] == 0) {
map[i][j] = 1;
dfs(i, j, deptNow + 1, dept);
map[i][j] = 0;
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine()); // N, M, H 순 입력
// N : 세로 실선 (2 ~ 20)
// H : 가로 점선 (1 ~ 30)
// M : 가로 실선
// H행 N열
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new int[h+2][n+1];
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = 1;
}
dfs(1, 1, 0, m);
System.out.println(ans > 3 ? -1 : ans);
}
}
시간 초과 코드이지만 일단 예제 입력은 전부 잘 돌아간다.
이걸 짜는 것만 해도 2시간이 걸렸다;
로직은 이렇다.
백트래킹을 하면서 가로 선을 하나씩 놓는다.
가로선의 최소 개수를 구하는 것이므로 하나 놓을 때마다 맵을 탐색하여 검사한다.
isPossible()에서는 각 열을 시작점으로 하여 n번의 탐색을 실시해야 한다. (도중에 하나라도 false가 뜨면 바로 리턴 한다)
값이 1인 좌표는 해당 좌표의 오른쪽 열로 넘어갈 수 있다는 뜻.
그러므로 탐색을 할 때는 내 좌표가 1인지, 내 왼쪽 좌표가 1인지를 모두 검사해야 한다. 오->왼 이동도 가능하기 때문.
연속된 가로선은 있을 수 없다는 조건이기 때문에 가로 이동을 실시하는 경우 바로 그 아래칸까지 보내버려도 된다.,
가로 이동이 불가할 경우 세로 이동만 실시.
주의할 점은 도착 검사를 h행이 아닌 h+1 행에서 해야 한다는 것이다. h행에서도 다른 열로 이동할 수도 있기 때문이다.
백트래킹하며 가로선을 하나씩 놓는 부분에서 시간 초과를 막기 위해 재귀 후 다음 탐색은 r행부터 실시하도록 했지만 시간 초과를 막는 데는 역부족이었다. 결국 시간 초과..
풀이 2. (정답 코드 - 3276ms)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int n, h, m, ans = -1;
static int[][] map = null;
static boolean[][] check = null;
static boolean complete;
// 위는 검사하지 않는다. 양 옆에 1 있는지 먼저 체크. 없으면 아래로
static int[] rArr = {0, 0}; // 좌 우
static int[] cArr = {-1 ,1}; // 좌 우
public static boolean isPossible() {
// i열이 i열로 도작하는지 체크
// 여기서 결국 탐색 한 번 다 돌려야 할 듯?
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= h+1; j++) {
Arrays.fill(check[j], false); // 가로선 계속 타는 무한루프 막기 위한 체킹
}
check[1][i] = true;
int endCol = search(1, i);
if(endCol != i) {
return false;
}
}
return true;
}
public static int search(int r, int c) {
// 내가 1이면 내 오른쪽 열로 이동
// 내 왼쪽이 1이면 내 왼쪽으로 이동
// 내 아래 행으로는 항상 이동 가능 (우선순위는 열 이동에 있음)
// 가로선은 H행이 끝이지만 완료 검사는 H+1행에서 해야 한다
if(r == h+1) { // 끝에 도착했으면 시작과 동일한지 체크
int endCol = c;
return endCol;
}
for(int i = 0; i < 2; i++) { // 좌우 검사
int nr = r + rArr[i];
int nc = c + cArr[i];
if(0 < nr && nr <= h && 0 < nc && nc <= n && !check[nr][nc]) { // H행 N열 범위 체크
if(i == 0 && map[nr][nc] == 1) { // 좌
check[nr][nc] = true;
check[nr+1][nc] = true; // 어차피 연속으로 열 이동 불가. 열 이동한 이후엔 어차피 아래로 가야함
return search(nr+1, nc);
}
if(i == 1 && map[r][c] == 1) { // 우
check[nr][nc] = true;
check[nr+1][nc] = true;
return search(nr+1, nc);
}
}
}
check[r+1][c] = true;
return search(r+1, c); // 하
}
public static void dfs(int r, int c, int deptNow, int dept) {
if(complete) return;
if(deptNow == dept) {
if(isPossible()) {
ans = deptNow; // dept는 1~3 순서로 올라가므로 굳이 대소비교 하지 않고 바로 넣어도 된다
complete = true;
}
return;
}
// 이제 여기서 가로실선을 하나씩 놓자
for(int i = r; i <= h; i++) { // 이전 행은 다시 확인할 필요 없음
for(int j = 1; j < n; j++) { // 마지막 열에는 놓을 수 없다
// 0열은 사용하지 않는 열이고 n열은 애초에 1이 올 수 없는 열이므로 범위 문제 없음
if(map[i][j] == 0 && map[i][j-1] == 0 && map[i][j+1] == 0) {
map[i][j] = 1;
dfs(i, j, deptNow + 1, dept);
map[i][j] = 0;
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine()); // N, M, H 순 입력
// N : 세로 실선 (2 ~ 20)
// H : 가로 점선 (1 ~ 30)
// M : 가로 실선
// H행 N열
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new int[h+2][n+1];
check = new boolean[h+2][n+1];
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = 1;
}
for(int i = 0; i <= 3; i++) {
dfs(1, 1, 0, i);
if(complete)
break;
}
System.out.println(ans);
}
}
무작정 가로선 하나를 놓을 때마다 검사를 한 번 씩 하는 게 문제였다.
목표 dept를 1~3으로 두고 목표 dept에 달성할 때까지는 그냥 놓기만 한 다음 다 놓고서 검사를 하는 방식으로 고쳤다.
정답이 3보다 클 경우 -1을 출력해야하므로 dept는 3까지만 해보면 된다.
처음으로 나오는 정답이 최소값이기 때문에 그 이후엔 재귀나 반복을 더 들어가지 않고 탈출하도록 boolean complete를 사용했다.
통과하긴 했지만 아직도 너무 느리다. (3276ms)
풀이 3. (정답 코드 - 428ms)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int n, h, m, ans = -1;
static int[][] map = null;
static boolean complete;
public static boolean isPossible() {
for(int i = 1; i <= n; i++) { // 모든 열 검사
int r = 1;
int c = i;
for(int j = 1; j <= h; j++) {
if(map[r][c-1] == 1) { // 왼쪽 이동 가능?
c -= 1;
r += 1;
continue;
}
if(map[r][c] == 1) { // 오른쪽 이동 가능?
c += 1;
r += 1;
continue;
}
r += 1; // 양 옆 이동 불가면 아래로 이동
}
if(c != i) return false;
}
return true;
}
public static void dfs(int r, int c, int deptNow, int dept) {
if(complete) return;
if(deptNow == dept) {
if(isPossible()) {
ans = deptNow; // dept는 1~3 순서로 올라가므로 굳이 대소비교 하지 않고 바로 넣어도 된다
complete = true;
}
return;
}
// 이제 여기서 가로실선을 하나씩 놓자
for(int i = r; i <= h; i++) { // 이전 행은 다시 확인할 필요 없음
for(int j = 1; j < n; j++) { // 마지막 열에는 놓을 수 없다
// 0열은 사용하지 않는 열이고 n열은 애초에 1이 올 수 없는 열이므로 범위 문제 없음
if(map[i][j] == 0 && map[i][j-1] == 0 && map[i][j+1] == 0) {
map[i][j] = 1;
dfs(i, j, deptNow + 1, dept);
map[i][j] = 0;
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine()); // N, M, H 순 입력
// N : 세로 실선 (2 ~ 20)
// H : 가로 점선 (1 ~ 30)
// M : 가로 실선
// H행 N열
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new int[h+2][n+1];
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = 1;
}
for(int i = 0; i <= 3; i++) {
dfs(1, 1, 0, i);
if(complete)
break;
}
System.out.println(ans);
}
}
시간이 확 줄어들었다.
가로선을 다 놓은 후 검사하는 방식에 문제가 있었다.
검사 코드를 너무 DFS 식으로 짜버려서 생긴 문제였다.
굳이 재귀와 check배열을 사용해가며 탐색할 필요 없다.
그냥 간단한 인덱스 조작을 통해 빠르게 검사할 수 있었다.
매번 check배열을 초기화하는 부분도 너무 시간낭비였는데 check 자체가 필요없어지니 속도도 빨라졌다.
여기까지 3시간 반이 걸렸네... 미치겠다...
'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글
| [BOJ] 2304 - 창고 다각형 JAVA (0) | 2021.02.24 |
|---|---|
| [BOJ] 11403 - 경로 찾기 JAVA (0) | 2021.02.24 |
| [BOJ] 1937 - 욕심쟁이 판다 JAVA (0) | 2021.02.23 |
| [BOJ] 17069 - 파이프 옮기기 2 JAVA (0) | 2021.02.23 |
| [BOJ] 17070 - 파이프 옮기기 1 JAVA (0) | 2021.02.23 |