백준 15684 : 사다리 조작 C++

www.acmicpc.net/problem/15684

15684번: 사다리 조작

문제 설명은 넘나 길어서 생략

 

풀이

1) 주어진 다리들 다 입력 받고 적용

 

2) 다리 놓을 수 있는 곳들을 q라는 벡터에 다 저장해 둔다

 

3) 순열써서 다리 '0개 추가' '1개 추가' '2개 추가' '3개 추가' 각각 실행

 

4) 다리 추가 후 lets_go() 라는 함수로 원하는 대로 움직이는지 체크!

 

5)  자기자신으로 잘 도착했다면, flag를 1로 만듬

 

6) flag가 1일때의 다리 갯수를 출력 후 프로그램 종료

 

6) 모든 경우 다 해봐도 안되면 -1 출력

 

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

int n, m, h;
int flag = 0; //이게 1이 안되면 답은 -1

int bridge[100][100] = { 0, }; //bridge[1][1]이 1이면 1,1과 1,2가 연결되어있는거다!!
 // [ 1~h ]  [ 1~n-1] 까지 가능
vector<pair<int, int> > q;
int checked_q[3000] = { 0, };

bool possible(int i, int j)
{
	if (bridge[i][j] == 1)//이미 설치된 곳!
		return false;
	if (j >= 2)
	{
		if (bridge[i][j - 1] == 1) //왼쪽에 다리 있으면 못 둠!
			return false;
	}
	if (j <= n-1)
	{
		if (bridge[i][j + 1] == 1)//오른쪽에 다리 있으면 못 둠!
			return false;
	}

	return true;
}

int lets_go() //움직여 보기
{
	int result = 1;
	int cnt = 1;
	int start;
	for (int i = 1; i <= n; i++)
	{
		start = i;
		cnt = 1;
		while (true)
		{
			if (cnt == h + 1) // 마지막에 도달
			{
				if (start != i)//하나라도 틀렸으면
				{
					result = 0;
					return result;
				}
				break;
			}

			if (bridge[cnt][start] == 1)
			{
				start = start + 1;//다리 있으면 오른쪽으로
				cnt++;
				continue;
			}

			if (start >= 2)//이전을 확인할 수 있는 상태
			{
				if (bridge[cnt][start-1] == 1)
				{
					start = start - 1;
					cnt++;
					continue;
				}
			}
			cnt++;

		}
	}

	return result;
}


void choose(int num,int cnt,int index)
{
	if (num == cnt) //원하는 갯수만큼 다리 뒀음!
	{
		if (lets_go() == 1) // 놓인 다리 대로 움직였는데 잘 됬따!
		{
			flag = 1;
		}
		return;
	}

	for (int i = index; i < q.size(); i++)
	{
		if (checked_q[i] == 0)//선택 안됬으면
		{
			if (possible(q[i].first, q[i].second))//쓸수 있는 다리면!! 이거ㅓ 추가한 이유는 새로 둘 다리 때문에 안될 수도 있으니까
			{
				checked_q[i] = 1;
				bridge[q[i].first][q[i].second] = 1;

				choose(num, cnt + 1, i);

				checked_q[i] = 0;
				bridge[q[i].first][q[i].second] = 0;
			}
		}
	}

}

int main()
{
	int data_1, data_2;
	cin >> n >> m >> h;

	for (int i = 0; i < m; i++) //m이 지금 있는 다리 갯수
	{
		cin >> data_1 >> data_2;
		bridge[data_1][data_2] = 1;
	}

	for (int i = 1; i <= h; i++) //설치 가능한 다리들 벡터로 만들기
	{
		for (int j = 1; j < n; j++)
		{
			if (possible(i, j))
			{
				q.push_back(make_pair(i, j));
			}
		}
	}

	for (int num = 0; num <= 3; num++)//놓을 다리 갯수 각각 brute force
	{
		choose(num,0,0); // 사용할 다리 정하고 성립하면 flag 1로 바꾸기
		if (flag == 1)
		{
			cout << num << endl;
			return 0;
		}
	}

	cout << -1 << endl;
	return 0;
}

 

 

 

 

다른사람들 풀이보니까 훨씬 짧고 보기 좋다...

분발하자...