[백준] 2469 - 사다리 타기

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

2469번: 사다리 타기

 

일반적인 사다리 게임에서 시작 값과 결과 값을 알려주고 숨겨놓은 가로 한 줄을 찾는 문제이다.

 

문제를 처음 볼 때는 오직 가로 한 줄만 숨겨져 있기 때문에 브루트포스로 해결할까 생각했지만,

숨겨진 가로 한 줄의 경우의 수 -> 수백 ~ 수천만

하나의 경우 당 사다리 타기 시간 복잡도 -> O(kn)

k는 최대 26, n은 최대 1000이므로 시간초과가 날 것이 뻔했다. 그래서 다른 방법을 생각해 보았다.

 

잘 생각해 보면, 사실 사다리 게임은 시작과 끝을 서로 바꾸어도 된다.

즉, 맨 아래를 맨 위라 생각하고 그대로 사다리 게임을 위아래로 뒤집어서 해도 처음 시작 결과가 나온다는 뜻이다.

이런 점에서 착안하여,

1. 시작점부터 숨겨진 가로 줄 위까지 사다리 게임을 진행한다.
2. 끝점(n - 1)부터 숨겨진 가로 줄 아래까지 사다리 게임을 진행한다.
3. 1번의 결과 -> 숨겨진 가로줄 -> 2번의 결과가 되므로, 숨겨진 가로줄을 구할 수 있다.

 

그렇다면 사다리 게임의 결과(1, 2)는 어떻게 구할 수 있을까?

매우 간단하다.

내가 있는 위치(j)에 사다리가 있다면 j번째 문자와 j+1번째 문자를 swap 하기만 하면 된다.

 

마지막으로 3을 구해보자.

1. 가로줄 하나를 통과하므로 같은 위치에 문자열의 서로 같다면 그 자리에는 사다리가 없을 것이다.
2. 만약 현재 위치와 다음 위치의 문자열이 바뀌어있다면 그 자리에는 사다리가 있을 것이다.
3. 1도 아니고 2도 아니면 구할 수 없다.

 

#include <iostream>
using namespace std;
int n, m, hideLine = -1;
string s2;
char map[1000][27];

void outError()
{
	for (int i = 0; i < m - 1; i++)
	{
		cout << "x";
	}
}

int main()
{
	cin >> m >> n >> s2;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m - 1; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == '?')
			{
				hideLine = i;
			}
		}
	}
	string s(m, ' ');
	for (int j = 0; j < m; j++)
	{
		s[j] = (j + 'A');
	}
	for (int i = 0; i < hideLine; i++)
	{
		for (int j = 0; j < m - 1; j++)
		{
			if (map[i][j] == '-')
			{
				swap(s[j], s[j + 1]);
			}
		}
	}
	for (int i = n - 1; i > hideLine; i--)
	{
		for (int j = 0; j < m - 1; j++)
		{
			if (map[i][j] == '-')
			{
				swap(s2[j], s2[j + 1]);
			}
		}
	}
	string ans = "";
	for (int i = 0; i < m - 1; i++)
	{
		if (s[i] == s2[i])
		{
			ans += "*";
		}
		else
		{
			if (s[i + 1] == s2[i])
			{
				ans += "-";
				if (i < m - 2)
				{
					ans += "*";
					i++;
				}
			}
			else
			{
				outError();
				return 0;
			}
		}
	}
	cout << ans;
	return 0;
}