[C/C++] 백준 - 15684번 : 사다리 조작 및 4-1학기 코딩 테스트 복기

 

약 2년 전에 풀었던 문제를 다시 풀어보았다.

기억보다는 기록에 의존하라는 말이 이래서 있는건가. 풀 때는 몰랐는데 당시에 풀었던 게시글을 보니 2일이나 걸려 해결했던 문제였다.

 

이번 4학년 1학기 때 정확히 기억은 안나지만 대략 5-6회 코딩테스트를 응시했다.

 

프로그래머스 ,유니콘 기업, 우테캠 등등 적지 않은 코딩테스트를 응시했다.

난 2023년 2월까지만 코딩테스트를 공부하고 그 뒤로는 한 번도 문제를 풀지 않았고 그 전까지 공부했던 내 기억에만 의존한 채 할 수 있을거라는 근자감으로 코딩테스트를 응시했었다.

 

결과는 당연히 처참했다. C++ 문법도 헷갈려서 많은 시간을 뺏기고 구현 문제 외에는 다른 알고리즘을 해결할 수 없었다.

약 2년 간 양치기로 해결했던 문제들은 모두 나 자신도 속이는 겉핥기식 공부였다는 것을 이번에 깨달았다. 

이번 방학에는 다시 초심으로 강의를 들으며 내가 부족한 부분이 무엇인지 찾아가며 공부하고 있다.

 

4학년 2학기 때 하반기 취업 준비 때 위 깨달음을 얻지 않은 것에 불행 중 다행이라고 생각한다. 양치기라도 했으니 처음부터 시작하는 것보다는 빠르게 공부하고 채워나갈 수 있다.

 

아래 문제를 처음 접했을 때는 2일이나 걸렸지만 이번에는 약 45분 걸렸다. 처음보다는 많은 시간을 줄였으나 아직 부족한 것은 마찬가지다.

나를 속이는 공부를 더 이상 하는 것은 무의미하다. 이제부터라도 느리더라도 꾸준히 채워나가는 것을 목표로 하고 있다.

 

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

 

https://wonsjung.tistory.com/77

[C/C++] 백준 - 15684번 : 사다리 조작

 

N과 H를 곱해도 300밖에 되지 않는다. 시간 제한은 2초이므로 모든 경우의 수를 확인해도 시간 내 해결이 가능하다.

따라서 완전탐색으로 문제를 해결한다. 내가 생각하고 구현한 알고리즘은 아래와 같다.

 

1. 입력을 통해 주어지는 정보를 이용하여 초기 사다리를 설치한다.
2. 위 1번 정보를 이용하여 아직 설치되지 않은 곳에 사다리 정보를 다른 자료구조에 저장한다.
3. 완전탐색을 이용하여 i번에서 시작하여 i번에 도착 가능한지 확인하는 함수를 구현한다.
4. 완전탐색을 시작한다.
   1. 가장 먼저 아무런 사다리를 설치하지 않고도 3번에서 구현한 함수에 만족하는지 검사한다.
   2. 만족하지 않는다면 최대 3개까지 설치가 가능하므로 1개 ~ 3개씩 설치하여 확인한다. 이는 백트래킹으로 설치 후 제거 동작을 반복하여 구현한다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 1e9 + 3
#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int N, M, H, answer = INF;
bool visited[300], isCan;
bool link[30 + 1][10 + 1][10 + 1];
vector<pair<int, int>> unlink, temp;

void input(){
	cin >> N >> M >> H;
	for(int i=0;i<M;i++){
		int a, b;
		cin >> a >> b;
                // 사다리 설치
		link[a][b][b+1] = true;
		link[a][b+1][b] = true;
	}
}

// 설치한 사다리 정보를 이용하여 아직 설치되지 않는 위치 정보를 얻어낸다.
void getUnlinkBridge(){
	for(int i=1;i<=H;i++){
		for(int j=1;j<N;j++){
			if(!link[i][j][j+1]){
				unlink.push_back({i, j});
			}
		}
	}
}

// i->i가 일치하는지 확인하는 함수
void go(int depth, int start, int pos){
	if(depth > H){
		if(start == pos) isCan = true;
		return;
	}

	if(link[depth][pos][pos+1] || link[depth][pos][pos-1]) {
		if(link[depth][pos][pos+1]) go(depth+1, start, pos+1);
		else go(depth+1, start, pos-1);
	} else{
		go(depth+1, start, pos);
	}
}

bool isComplete(){
	for(int i=1;i<=N;i++){
		isCan = false;
		go(1, i, i);
		if(!isCan) return false;
	}
	return true;
}

void getLinkBridge(int cnt, int start, int purpose){
    // 원하는 사다리 개수를 설치했을 경우 i->i가 가능한지 검사한다.
    // i->i가 가능할 때만 최소 개수로 초기화한다.
	if(cnt == purpose){
		if(isComplete()) answer = min(answer, purpose);
		return;
	}

    // 백트래킹을 이용하여 사다리를 설치한다.
	for(int i=start;i<unlink.size();i++){
		if(!visited[i]){
			visited[i] = true;
			link[unlink[i].first][unlink[i].second][unlink[i].second+1] = true;
			link[unlink[i].first][unlink[i].second+1][unlink[i].second] = true;

			getLinkBridge(cnt+1, i+1, purpose);

			visited[i] = false;
			link[unlink[i].first][unlink[i].second][unlink[i].second+1] = false;
			link[unlink[i].first][unlink[i].second+1][unlink[i].second] = false;
		}
	}
}

void solution(){
    // 아무런 사다리를 설치하지도 않고 i->i가 가능한지 확인한다.
	if(isComplete()) {
		answer = 0;
		return;
	}

	// 사다리는 최대 3개 설치 가능하므로 개수 제한을 둔다.
	for(int i=1;i<=3;i++){
		getLinkBridge(0, 0, i);	
	}
	if(answer == INF) answer = -1;
}

int main(){
	fastio;	
	input();
	getUnlinkBridge();
	solution();
	cout << answer << endl;

	return 0;
}