BOJ 2469 사다리 타기

사용한 알고리즘

구현

알고리즘 설명

몇 번째 줄을 찾아야 하는지에 대해서 unknown에 저장한다
위쪽에서 unknown전까지, 아래쪽에서 unknown전까지의 알파펫 상황을 구한다.
위 아래가 같아 바꾸지 않아도 되는 경우에는 ‘* ‘를 출력하고 둘을 바꿔서 가능한 경우에는 “* - “를 추가한다. 이 두가지 경우로 성립되지 않는 경우에는 순서를 얻을 수 없는 경우로 “x”를 한줄 출력하면 된다.

풀이

// baekjoon 2469 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_K=27;
const int MAX_N=1001;

int K, N, unknown, uppos, downpos;
int up[MAX_K], down[MAX_K];
char ladder[MAX_N][MAX_K];
char bottom[MAX_K];
char ans[MAX_K];
bool visited[MAX_K];

int main() {
	scanf("%d%d", &K, &N);
	scanf("%s", bottom);
	for (int i=0; i<N; i++) {
		scanf("%s", ladder[i]);
		if (ladder[i][0] == '?') unknown = i;
	}
	for (int i=0; i<K; i++) {
		up[i] = i;
		down[i] = bottom[i]-'A';
	}

	while (uppos < unknown) {
		memset(visited, 0, sizeof(visited));
		for (int i=0; i<K-1; i++) {
			if (!visited[up[i]] && ladder[uppos][i] != '*') {
				visited[up[i]]=visited[up[i+1]]=true;
				swap(up[i], up[i+1]);
			}
		}
		uppos++;
	}
	downpos=N-1;
	while (downpos > unknown) {
		memset(visited, 0, sizeof(visited));
		for (int i=0; i<K-1; i++) {
			if (!visited[down[i]] && ladder[downpos][i] != '*') {
				visited[down[i]]=visited[down[i+1]]=true;
				swap(down[i], down[i+1]);
			}
		}
		downpos--;
	}

	for (int i=0; i<K-1; i++) {
		if (up[i] == down[i]) ans[i]='*';
		else {
			if ((up[i] == down[i+1]) && (down[i] == up[i+1])) {
				ans[i]='-';
				ans[i+1]='*';
				i++;
			}
			else {
				for (int i=0; i<K-1; i++) {
					printf("x");
				}
				puts("");
				return 0;
			}
		}
	}

	ans[K-1]='\0';
	puts(ans);
	return 0;
}