📃 문제
[BOJ] 사다리 타기 🔗링크
❓ 문제 접근
- 처음에는 Brute Force로 접근했는데, 그렇게 되면 타임아웃이 나올 것 같아 다른 방법을 고민했다.
?
로 이루어진 사다리에 도달하기 전과 후의 참가자 위치는 주어진 사다리를 통해 구할 수 있다.
그렇다면 전/후 참가자의 위치를 통해 사다리의 배열은 손쉽게 구할 수 있다.
- 사다리에 도달하기 전/후 참가자의 위치를 구하는 건
climbLadder
함수를 통해 구현했다.
사다리를 구성하여 주어진 순서를 얻을 수 있는지, 없는지 판단하는 isPossible
함수를 구현하고,
마지막은 조건문을 통해 사다리를 구현한다.
🧠 풀이
#include <iostream>
using namespace std;
void climbLadder(int first, int step, char* data, char* _result);
bool isPossible(char* before, char* after);
int n,k;
char ladder[1000][27];
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
char depart[27];
char arrive[27];
char before[27];
char after[27];
cin >> n >> k;
cin >> arrive;
for(int i=0; i<k; i++){
cin >> ladder[i];
}
for(int i=0; i<n; i++){
depart[i] = char(i+65);
}
climbLadder(0,1,depart, before);
climbLadder(k-1,-1,arrive, after);
bool check = isPossible(before, after);
if(check){
char ans[27];
for(int i=0; i<n-1; i++){
if((before[i] == after[i] or before[i+1] == after[i+1]) or (i>0 and ans[i-1] == '-')){
ans[i] = '*';
}
else{
ans[i] = '-';
}
}
for(int i=0; i<n-1; i++){
cout << ans[i];
}
cout << "\n";
}
else{
for(int i=0; i<n-1; i++){
cout << 'x';
}
cout << "\n";
}
return 0;
}
void climbLadder(int first, int step, char* data, char* _result){
int floor = first;
bool questionMarkFlag = false;
char result[2][27];
int index = (floor) % 2;
int nextIndex = (floor + 1) % 2;
for(int i=0; i<n; i++){
result[index][i] = data[i];
}
while(!questionMarkFlag){
for(int j=0; j<n; j++){
int dest;
if(ladder[floor][j] == '?'){
questionMarkFlag = true;
break;
}
else if(ladder[floor][j] == '-')
dest = j + 1;
else if(j-1 >= 0 && ladder[floor][j-1] == '-')
dest = j - 1;
else
dest = j;
result[nextIndex][dest] = result[index][j];
}
floor += step;
index = (floor) % 2;
nextIndex = (floor + 1) % 2;
}
for(int i=0; i<n; i++){
_result[i] = result[nextIndex][i];
}
return;
}
bool isPossible(char* before, char* after){
int count = 0;
for(int i=0; i<n; i++){
for(int step=-1; step<=1; step++){
int idx = i + step;
if(idx>=0 and idx<n){
if(before[i] == after[idx]){
count++;
break;
}
}
}
}
if(count == n) return true;
return false;
}