문제

BOJ

핵심

• 입력의 크기가 $10, 30$이라 구현에 초점을 맞춘다.
• 사다리 게임으로 세로선 개수와 세로선마다 놓을 수 있는 가로선 개수가 주어진다. n번에서 출발하면 n번으로 도착할 수 있게 최대 3개의 사다리를 설치할 수 있다. 예를 들어 세로선이 6개 있고 1번에서 출발했다면 사다리를 타고 1번에 도착해야 한다. 2번에서 출발하면 2번에 도착해야 한다.
• 설치할 수 있는 모든 사다리 위치를 구한 후 사다리 {0, 1, 2, 3}개를 차례로 골라 n번에서 n번으로 도착하는 조건이 성립하는지 판단할 수 있다. n개의 사다리 중 {0, 1, 2, 3}개 사다리를 선택하는 조합 문제로 볼 수 있다. dfs 반환 값을 이용해 찾았을 경우 탐색을 종료하는 효율적인 방법을 알 수 있었다.
• 크게 두 가지 구현 사항이 있다. 첫째로 사다리를 타는 작업이다. 사다리를 입력을 받을 때 사다리의 시작 위치를 1로 두고, 끝 위치를 2로 두어 사다리를 타고 내려갈 때 방향을 정하도록 하였다.

lad[l][r] = 1;
lad[l][r + 1] = 2;

• 예를 들어, 사다리가 1이라면 사다리는 내려가면서 오른쪽으로 이동하고 사다리가 2라면 왼쪽으로 이동하게 끔 구현하였다. n번 사다리가 n번에 도착하지 않다면 조건을 만족하지 않으므로 false를 반환한다.

bool isStraight() {
	for (int col = 1; col <= n; ++col) {
		int sCol = col;
		int row = 0;
		while (row <= h) {
			if (lad[row][col] == 1)
				++col;
			else if (lad[row][col] == 2)
				--col;
			++row;
		}
		if (sCol != col)
			return false;
	}
	return true;
}

• 둘째로 전체 사다리 중 n개의 사다리를 고르는 조합을 구현하는 것이다. 먼저 가로선을 연속해서 놓을 수 없다는 것을 고려하여 사다리를 설치할 수 있는 모든 위치를 emp 배열에 담는다.

for (int i = 1; i <= h; ++i) {
	for (int j = 1; j < n; ++j) {
		if (lad[i][j] == 0 && lad[i][j + 1] == 0)
			emp.push_back({i, j});
	}
}

• 전체 사다리 중 n개를 고르기 위해 dfs 함수를 사용한다. dfs 반환 값으로 조건을 충족했다면 사다리를 고른 개수를 반환하며 못 찾았을 경우 -1을 반환한다. 아래와 같이 작성하였다.

int ans = -1;
for (int i = 0; i <= 3; ++i) {
	ans = dfs(0, i, 0); 
	if (ans != -1) // 찾았을 경우 0, 1, 2, 3(전체 갯수)를 반환한다.
		break;
}

• dfs는 효율적인 탐색을 위해 인자로 깊이, 찾을 개수, 탐색을 시작할 위치를 받는다. 해당 사다리를 설치할 경우 lad 배열에 1, 2로 표시하고 다음 사다리를 선택하는 식으로 구현하였다.

int dfs(int depth, int mx, int start) {
	if (depth == mx) {
		if (isStraight())
			return depth;
		return -1;
	}
	for (int i = start; i < (int)emp.size(); ++i) {
		if (lad[emp[i].first][emp[i].second] || lad[emp[i].first][emp[i].second + 1]) 
			continue;
		lad[emp[i].first][emp[i].second] = 1;
	   	lad[emp[i].first][emp[i].second + 1] = 2;
		if (dfs(depth + 1, mx, i + 1) > 0)
			return mx;
		lad[emp[i].first][emp[i].second] = 0;
	   	lad[emp[i].first][emp[i].second + 1] = 0;
	}
	return -1;
}

개선

코드

시간복잡도

• k가 emp길이일 때,
• $O(kC3 \times n + ... + kC0 \times n)$

C++

#include <iostream>
#include <vector>
using namespace std;

int n, m, h;
int lad[34][14];
vector<pair<int, int>> emp;
bool isStraight() {
	for (int col = 1; col <= n; ++col) {
		int sCol = col;
		int row = 0;
		while (row <= h) {
			if (lad[row][col] == 1)
				++col;
			else if (lad[row][col] == 2)
				--col;
			++row;
		}
		if (sCol != col)
			return false;
	}
	return true;
}

int dfs(int depth, int mx, int start) {
	if (depth == mx) {
		if (isStraight())
			return depth;
		return -1;
	}
	for (int i = start; i < (int)emp.size(); ++i) {
		if (lad[emp[i].first][emp[i].second] || lad[emp[i].first][emp[i].second + 1]) 
			continue;
		lad[emp[i].first][emp[i].second] = 1;
	   	lad[emp[i].first][emp[i].second + 1] = 2;
		if (dfs(depth + 1, mx, i + 1) > 0)
			return mx;
		lad[emp[i].first][emp[i].second] = 0;
	   	lad[emp[i].first][emp[i].second + 1] = 0;
	}
	return -1;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> h;
	for (int i = 0; i < m; ++i) {
		int l, r;
		cin >> l >> r;
		lad[l][r] = 1;
		lad[l][r + 1] = 2;
	}
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j < n; ++j) {
			if (lad[i][j] == 0 && lad[i][j + 1] == 0)
				emp.push_back({i, j});
		}
	}
	int ans = -1;
	for (int i = 0; i <= 3; ++i) {
		ans = dfs(0, i, 0);
		if (ans != -1)
			break;
	}
	cout << ans;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int n, m, h;
    static int[][] lad = new int[34][14];
    static ArrayList<int[]> emp = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            lad[a][b] = 1;
            lad[a][b + 1] = 2;
        }
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j < n; ++j) {
                if (lad[i][j] == 0 && lad[i][j + 1] == 0)
                    emp.add(new int[]{i, j});
            }
        }
        int ans = -1;
        for (int i = 0; i <= 3; i++) {
            ans = dfs(0, i, 0);
            if (ans != -1)
                break;
        }
        System.out.println(ans);
    }

    static int dfs(int depth, int mx, int start) {
        if (depth == mx) {
            if (isStraight())
                return depth;
            return -1;
        }
        for (int i = start; i < emp.size(); ++i) {
            int[] cur = emp.get(i);
            if (lad[cur[0]][cur[1]] != 0 || lad[cur[0]][cur[1] + 1] != 0)
                continue;
            lad[cur[0]][cur[1]] = 1;
            lad[cur[0]][cur[1] + 1] = 2;
            if (dfs(depth + 1, mx, i + 1) > 0)
                return mx;
            lad[cur[0]][cur[1]] = 0;
            lad[cur[0]][cur[1] + 1] = 0;
        }
        return -1;
    }

    static boolean isStraight() {
        for (int col = 1; col <= n; ++col) {
            int sCol = col;
            int row = 0;
            while (row <= h) {
                if (lad[row][col] == 1)
                    ++col;
                else if (lad[row][col] == 2)
                    --col;
                ++row;
            }
            if (sCol != col)
                return false;
        }
        return true;
    }
}