<Baekjoon> #15684 DFS, BruteForce_사다리 조작 c++

Google 아니고 Joogle·2022년 3월 2일
0

SAMSUNG SW Test

목록 보기
18/39
post-thumbnail

#15684 사다리 조작
참고

💬문제 정리

그림으로 설명해보자면 다음과 같다

  • 여기서 5번째 열은 사용되지 않는다.
    왜냐하면 세로선은 5번까지 있는데, map[a][5]= 5,6번 세로선이 a번째 점선으로 연결된다는 의미이기 때문이다
  • map[a][b]가 연결되었다면 가로선이 서로 연결될 수 없다는 문제 조건 때문에 map[a][b-1], map[a][b+1]은 연결 될 수 없다

👩‍💻1. dfs 함수

  • (1,1)부터 (H,N-1)까지 차례대로 연결선을 추가해보며 사다리 조건에 맞는지 탐색한다
  • void dfs(int cnt, int y, int x)
    cnt: 현재 몇 개의 연결선을 추가했는지이고,
    문제에서 최대 3개까지 추가할 수 있다고 했으므로 3개가 되기 전까지는 계속 사다리 조건에 맞는지 탐색한다
    (y,x): 연결선을 추가할 시작점. 매번 dfs를 다시 호출할 때마다 x1 늘려준다
  • map[a][b]에 연결선을 추가하려면 map[a][b],map[a][b-1],map[a][b+1]에 다 연결선이 없는지 확인해야 한다
  • 연결선을 그어주고 모든 탐색을 마치고 왔을 때는 다시 연결선을 없애주어 (map[a][b]=0) 다른 곳에 연결선을 그었을 때를 탐색해준다
void dfs(int cnt, int y, int x) {
	if (cnt >= minCnt) return;
	if (check()) {
		minCnt = cnt; return;
	}
	if (cnt == 3) return;

	for (int i = y; i <= H; i++) {
		for (int j = x; j < N; j++) {
			if (map[i][j] != 1 && map[i][j - 1] != 1 && map[i][j + 1] != 1) {
				map[i][j] = 1;
				dfs(cnt + 1, y, x+1);
				map[i][j] = 0;
			}
		}
	}
}

👩‍💻2. i번 세로선의 결과가 i번인지 check

  • 각 세로선마다 한 단계씩 내려가면서 가로선이 그어진 게 있는지 확인해야 한다.
  • 현재 위치에서 그어진 것이 있다면 오른쪽으로 이동했다는 뜻이니까 현재 위치 pos++해준다
  • 현재 위치 앞에서 그어진 것이 있다면 다시 왼쪽으로 이동한다는 뜻이니 pos--해준다
  • 마지막 위치 posi번에 있는지 확인
bool check() {
	for (int i = 1; i <= N; i++) {
		int pos = i;
		for (int j = 1; j <= H; j++) {
			if (map[j][pos] == 1)
				pos++;
			else if (map[j][pos - 1] == 1)
				pos--;
		}
		if (pos != i) return false;
	}
	return true;
}

전체코드

#include <iostream>
#include <vector>

using namespace std;

int minCnt=4;
int N, M, H;
vector<vector<int>> map;

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

void dfs(int cnt, int y, int x) {
	if (cnt >= minCnt) return;
	if (check()) {
		minCnt = cnt; return;
	}
	if (cnt == 3) return;

	for (int i = y; i <= H; i++) {
		for (int j = x; j < N; j++) {
			if (map[i][j] != 1 && map[i][j - 1] != 1 && map[i][j + 1] != 1) {
				map[i][j] = 1;
				dfs(cnt + 1, y, x+1);
				map[i][j] = 0;
			}
		}
	}
}

void init() {
	cin >> N >> M >> H;
	map = vector<vector<int>>(H + 1, vector<int>(N + 1, 0));
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
	}
}

int main() {
	init();
	dfs(0, 1,1);
	if (minCnt == 4) cout << "-1" << endl;
	else cout << minCnt << endl;
	return 0;
}

profile
Backend 개발자 지망생

0개의 댓글