[백준][삼성 SW 역량 테스트][Gold 5][C++] 15684 사다리 조작

문제

백준 삼성 SW 역량 테스트 기출 문제 - 15684 사다리 조작 (Gold 5)

15684번: 사다리 조작

 

---

문제 풀이

접근 방식

사다리에 가로선을 추가하여 i번 세로선의 결과가 i번이 나오도록 조작할 때,

추가해야 하는 가로선 개수의 최솟값을 구하는 문제이다.

 

우선 H×N 크기의 map 벡터를 만들어 사다리의 가로선들을 저장해주었다.

가로선의 왼쪽 부분과 오른쪽 부분을 구분해주어야 하기 때문에,

왼쪽 부분은 1, 오른쪽 부분은 -1로 저장하였다.

 

그 후, DFS 방식으로 탐색하여 가로선이 없는 곳들에 가로선을 최대 3개까지 추가해보며,

추가해야 하는 가로선의 개수의 최솟값을 구해주었다.

 

원하는 대로 조작되었는지 확인하기 위해 check 함수를 만들어 확인해주었다.

check 함수는 모든 열을 위에서 아래로 탐색하며 1을 만나면 1을 더하고 -1을 만나면 1을 빼서,

최종적으로 모든 인덱스 값이 바뀌지 않는다면 true를 반환해주도록 구현하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>

using namespace std;

int N, M, H, MIN;
vector<vector<int>> map;

bool check() {
	for (int i = 0; i < N; i++) {
		int a = i;
		for (int j = 0; j < H; j++) {
			if (map[j][a] == 1)
				a++;
			else if (map[j][a] == -1)
				a--;
		}
		if (a != i)
			return false;
	}
	return true;
}

void DFS(int x, int y, int cnt) {
	if (cnt >= MIN) return;
	if (check()) {
		MIN = cnt;
		return;
	}

	for (int i = x; i < H; i++) {
		for (int j = y; j < N - 1; j++) {
			if (map[i][j] != 0 || map[i][j + 1] != 0) continue;

			map[i][j] = 1;
			map[i][j + 1] = -1;

			DFS(i, j + 1, cnt + 1);

			map[i][j] = 0;
			map[i][j + 1] = 0;
		}
		y = 0;
	}
}

int main() {
	// 입력 받기
	cin >> N >> M >> H;
	map.assign(H, vector<int>(N));
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		map[a - 1][b - 1] = 1;
		map[a - 1][b] = -1;
	}

	// 최소 횟수로 가로선 추가하기
	MIN = 4;
	DFS(0, 0, 0);
	if (MIN != 4)
		cout << MIN;
	else
		cout << -1;
}

실행 결과

실행 결과 : 통과 (948ms)