백준 15684번 _ 사다리 조작

 

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

15684번: 사다리 조작

 

1. 풀이방법

 

 이 문제를 푸는 방식에는 여러가지가 있는것 같지만 나는 dfs 백트랙킹으로 풀었다.

 이때 가지를 잘치는 것이 중요하다. 

 

 내 경우에는 가지를 쳤던곳이 지금 사다리를 놓은게 3개 초과일때, 이미 구해놓은 답이 지금 탐색하는 곳보다 낮을때

 

if (cnt > 3 || cnt >= answer)
	return;

 이렇게 했다.

 

 

 하지만, 이 문제는 이렇게만 자르면 시간초과난다.. 그래서 다른 정답코드들을 참고했더니

void dfs(int idx, int cnt)
{
	if (cnt > 3 || cnt >= answer)
		return;

	if (isSucess())
	{
		answer = min(answer, cnt);
		return;
	}

	for (int i = idx; i <= h; i++)
	{
    	...
    	}
 }   

 지금 내가 탐색한 idx부터 i를 시작해서 더 시간을 줄여준다.

 

 이렇게까지 하면 통과다.

 

---

 

2. 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

int map[33][13];
int n, m, h;
bool visit[33][13];

// i는 i로 가는지 확인함수
int ladderGame (int startPoint)
{
	for (int i = 1; i <= h; i++)
	{
		//내려가다가 사다리가 있으면 오른쪽으로
		if (map[i][startPoint] == 1)
			startPoint++;
		//왼쪽도 봐야함
		else if (map[i][startPoint - 1] == 1)
			startPoint--;
	}
	return startPoint;
}

//조작이 완료되었는지 확인
bool isSucess()
{
	for (int startPoint = 1; startPoint <= n; startPoint++)
	{
		int endPoint = ladderGame(startPoint);
		if (startPoint != endPoint)
			return false;
	}
	return true;
}

int answer = INT_MAX;
void dfs(int idx, int cnt)
{
	if (cnt > 3 || cnt >= answer)
		return;

	if (isSucess())
	{
		answer = min(answer, cnt);
		return;
	}

	for (int i = idx; i <= h; i++)
	{
		for (int j = 1; j < n; j++)
		{
			if (map[i][j] == 0 && visit[i][j] == false)
			{
				if (map[i][j + 1] == 1) continue;
				if (map[i][j - 1] == 1) continue;

				map[i][j] = 1;
				visit[i][j] = true;
				dfs(i, cnt + 1);
				map[i][j] = 0;
				visit[i][j] = false;

			}
		}
	}
}

int main()
{
	cin >> n >> m >> h;
	
	//입력
	int a, b;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		map[a][b]= 1;
	}

	if (isSucess())
		cout << 0 << endl;
	else
	{
		//dfs
		dfs(0);

		if (answer == INT_MAX)
			cout << -1 << endl;
		else
			cout << answer << endl;
	}
	return 0;
}

  

 

---

 

3. 후기

 

 처음에는 시간초과가 계속나서 거의 멘탈이 반 나갔지만 역시 훌륭하신 인터넷형님들의 도움으로 무사히 넘겼다.

 그냥 모르면 객기부리지말고 형님들의 도움을 받자.