[BOJ/백준 15684/C++] 사다리 조작

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

15684번: 사다리 조작

 

[문제 요약]

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

이때 추가해야되는 가로선의 최솟값을 구하여라

 

[문제 조건]

- 첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

- 둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

- 가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

- 가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

- 입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

- 시간 제한 : 2초

- 메모리 제한 : 256MB

 

[문제 풀이]

문제가 요구하는 바는 의외로 간단하다.

 

주어진 사다리타기 표에다가 조건에 맞게 가로선을 추가해서 1번은 1번으로 2번은 2번으로 .... n번은 n번에 도착하게 만들면 되는데 가로선은 최대 3개 까지만 사용해서 판별하면 된다.

 

필자는 사다리타기 표를 배열로 나타내기 위해 3차원 배열을 사용하였다. ( 2차원 배열로도 풀 수 있음. 필자는 복잡해서 포기했음 )

 

3차원 배열 mp[i][j][k]가 의미 하는 바는 i번째 가로줄에 j와 k를 잇는 가로선이 존재한다. 가로선의 존재여부만 판단하면 됨으로 자료형은 bool형을 사용하였다.

 

입력으로 가로선의 정보가 주어일때, 예를들어 2, 3이 입력으로 들어오면 mp[2][3][4] = true로 변경하고 양 옆을 -1로 갱신함으로써 양 옆에는 가로선을 놓을 수 없다는 것을 표시했다.

int a, b;
for (int i = 0; i < M; i++)
{
    cin >> a >> b;
    mp[a][b][b + 1] = 1;
    //양 옆 선택 불가 표시
    if (b - 1 >= 1) mp[a][b - 1][b] = -1;
    if (b + 2 <= N) mp[a][b + 1][b + 2] = -1;
}

다음으로는 배열상 값이 0인 부분은 able 배열에 추가하여 가로선을 추가할 수 있는 좌표들을 저장하였다.

for (int i = 1; i <= H; i++)
{
    for (int j = 1; j < N; j++)
    {
        if (mp[i][j][j + 1] == 0) able.push_back({ i,{j,j + 1} });
    }
}

문제에서 정답이 3보다 크면 -1을 출력하라고 했음으로, 선택하는 가로선의 갯수는 최대 3개로 제한하여 시뮬레이션을 돌리면된다.

for (int i = 0; i <= 3; i++)
{
    simulation(0, i);
    if (end_program) break;
}
if (!end_program) cout << "-1";

 

그 다음으로는 simulation함수의 첫번째 인자 만큼 able에서 가로선 위치를 선택하여 시뮬레이션을 돌리는 작업을 하면된다. 먼저 아래 코드는 able에서 선택하는 부분의 코드이다.

for (int i = start; i < able.size(); i++)
{
    bool flag2 = false;
    if (mp[able[i].first][able[i].second.first][able[i].second.second] == 0)
    {
        selected.push_back(able[i]);

        mp[able[i].first][able[i].second.first][able[i].second.second] = 1;
        if (able[i].second.first - 1 >= 1) mp[able[i].first][able[i].second.first - 1][able[i].second.first] = -1;
        if (able[i].second.second + 1 <= N) mp[able[i].first][able[i].second.second][able[i].second.second + 1] = -1;
        flag2 = true;
    }
    else continue;
    simulation(i + 1, cnt);

    if (end_program) return;

    if (flag2)
    {
        selected.pop_back();
        mp[able[i].first][able[i].second.first][able[i].second.second] = 0;
        if (able[i].second.first - 1 >= 1) mp[able[i].first][able[i].second.first - 1][able[i].second.first] = 0;
        if (able[i].second.second + 1 <= N) mp[able[i].first][able[i].second.second][able[i].second.second + 1] = 0;
    }
}

복잡해보이지만 pair를 겹쳐서 쓰다보니 길어진거지 사실상 별거 없는 코드다.

 

만약 able에서 선택한 좌표가 mp배열에서 값이 0이면 selected 배열에 추가하고, simulation이 끝나면 selected배열에서 제거한뒤 배치했던 표시들을 원래대로 되돌리는 부분이다.

 

다음은 실질적으로 시뮬레이션을 돌리는 부분이다.

if (selected.size() == cnt)
{
    bool promising = true;
    for (int i = 1; i <= N; i++)
    {
    	//시작위치는 i
        int cur = i;
        for (int j = 1; j <= H; j++)
        {
        	//오른쪽으로 가는 가로선이 있으면 오른쪽으로 이동 1일 경우 2로 이동
            if (cur + 1 <= N && mp[j][cur][cur + 1] == 1) cur++;
            //왼쪽으로 가는 가로선이 있으면 왼쪽으로 이동 2일 경우 1로 이동
            else if (cur - 1 >= 1 && mp[j][cur - 1][cur] == 1) cur--;
        }
        //만약 처음 위치랑 도착 위치가 다르다면
        if (cur != i)
        {
            promising = false;
            break;
        }
    }
    //문제 조건 : i는 i번째 위치에 도착해야된다. 이것에 해당하지 않을경우
    if (!promising) return;
    //성공한 경우
    else
    {
        cout << cnt;
        end_program = true;
        return;
    }
}

 

사실상 이번 문제는 사다리타기 맵을 표현하는 것이 중요했던 문제인 것 같다. 사실상 사다리타기를 수행하는건 어렵지 않았지만 어떤 가로선을 선택하고, 이 맵을 어떻게 배열로 표현할 것인가가 중요했던 거 같다.

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

bool end_program = false;
int N, M, H;
vector<vector<vector<int>>> mp;
vector<pair<int, pair<int, int>>> able;
vector<pair<int, pair<int, int>>> selected;

void simulation(int start, int cnt)
{
	if (selected.size() == cnt)
	{
		bool promising = true;
		for (int i = 1; i <= N; i++)
		{
			//시작위치는 i
			int cur = i;
			for (int j = 1; j <= H; j++)
			{
				//오른쪽으로 가는 가로선이 있으면 오른쪽으로 이동 1일 경우 2로 이동
				if (cur + 1 <= N && mp[j][cur][cur + 1] == 1) cur++;
				//왼쪽으로 가는 가로선이 있으면 왼쪽으로 이동 2일 경우 1로 이동
				else if (cur - 1 >= 1 && mp[j][cur - 1][cur] == 1) cur--;
			}
			//만약 처음 위치랑 도착 위치가 다르다면
			if (cur != i)
			{
				promising = false;
				break;
			}
		}
		//문제 조건 : i는 i번째 위치에 도착해야된다. 이것에 해당하지 않을경우
		if (!promising) return;
		//성공한 경우
		else
		{
			cout << cnt;
			end_program = true;
			return;
		}
	}

	for (int i = start; i < able.size(); i++)
	{
		bool flag2 = false;
		if (mp[able[i].first][able[i].second.first][able[i].second.second] == 0)
		{
			selected.push_back(able[i]);

			mp[able[i].first][able[i].second.first][able[i].second.second] = 1;
			if (able[i].second.first - 1 >= 1) mp[able[i].first][able[i].second.first - 1][able[i].second.first] = -1;
			if (able[i].second.second + 1 <= N) mp[able[i].first][able[i].second.second][able[i].second.second + 1] = -1;
			flag2 = true;
		}
		else continue;
		simulation(i + 1, cnt);

		if (end_program) return;

		if (flag2)
		{
			selected.pop_back();
			mp[able[i].first][able[i].second.first][able[i].second.second] = 0;
			if (able[i].second.first - 1 >= 1) mp[able[i].first][able[i].second.first - 1][able[i].second.first] = 0;
			if (able[i].second.second + 1 <= N) mp[able[i].first][able[i].second.second][able[i].second.second + 1] = 0;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> H;

	mp.resize(H + 1);
	for (int i = 0; i < H + 1; i++)
	{
		mp[i].resize(N + 1);
		for (int j = 0; j < N + 1; j++) mp[i][j].resize(N + 1);
	}

	int a, b;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		mp[a][b][b + 1] = 1;
		//양 옆 선택 불가 표시
		if (b - 1 >= 1) mp[a][b - 1][b] = -1;
		if (b + 2 <= N) mp[a][b + 1][b + 2] = -1;
	}

	for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j < N; j++)
		{
			if (mp[i][j][j + 1] == 0) able.push_back({ i,{j,j + 1} });
		}
	}

	for (int i = 0; i <= 3; i++)
	{
		simulation(0, i);
		if (end_program) break;
	}
	if (!end_program) cout << "-1";

	return 0;
}

 

 

 

아니 근데 맞은신분들 중에 시간이 0초 걸리는 분들 있던데 어떻게 한거지....?

시간 줄여보고 싶었지만 나중에 해보기로 했다.

굳