문제 이해 단계
우리가 익히 아는 사다리 타기인데, 입력으로 인원수 K와 가로줄의 개수 N이 들어온다.
그다음에는 사다리 타기의 결과가 문자열로 주어진 후,
사다리 타기의 모양이 주어진다.
사다리 타기의 시작은 무조건 알파벳순대로 들어온다. (ABCDE..)
사다리 타기가 종료되면 입력됐던 결과가 출력되도록
"???"를 구성하는 것이 해당 문제.
만약 구성하지 못할 경우 인원수만큼 x를 출력한다.
문제 접근 단계
사다리 타기에서 처음 상태에서 마지막 상태까지 가능한가를 따져보려면,
일단 최대한 두 상태가 근접해야 한다.
다행히도 "?????"로 들어오는 가로는 무조건 한 줄이기 때문에
직선은 하나 차이로 들어온다.
아래 그림과 같이 "???"에 최대한 가까이 붙여주면 이를 판단하기 훨씬 더 쉬워진다.
그럼 결국에 문제는 사다리 타기를 구현해야 한다는 것인데, 어떤 방식으로 구현해야 할까?
여기서도 사다리 타기를 가로에 따라 나눠놨으니까
가로 단위 즉, 가로로 한 칸씩 내려가보자.
로직은 굉장히 간단하다.
넘어가는 선(가로선)을 만나면 배열적으로 보면, 두 배열이 교환되는 것이다.
그래서 정리하자면, 내려가다가 *을 만나면 그 배열은 가만히 두고
"-" 그 작대기와 연결된 두 배열을 교환하는 것이다.
이는 나중에 문제 구현 단계에서 자세히 살펴보겠다.
구성 가능한지 판단하기
사다리 타기 하는 방법도 알았고, 판단하기 쉽게 두 결과를 가까이 붙여주었으니
이제 이 두 개를 비교해서 판단해 보자.
해당 케이스는 예제 케이스 1번을 가져온 것이다.
물음표 부분을 조정해서 위에 문자를 아래 문자처럼 만들어보자.
"???"로 이루어진 가로는 무조건 한 칸이기 때문에 한 알파벳의 자리를 최대 1번밖에 교환할 수 없다.
즉 한 알파벳의 관점에서 보면
1. 그대로 내려감
2. 한 칸 움직임
이 두 가지 중 하나를 선택해야 한다.
이를 다른 의미로 말하면 한 알파벳이라도
두 칸 이상 차이 나면 구성할 수 없다는 뜻이다.
모든 알파벳 배열 이 한 칸밖에 차이 나지 않는다는 뜻은,
모든 알파벳 배열에 대해서 위와 아래 알파뱃 배열이 동일하거나,
두 알파벳이 한 번의 움직임으로 같아지는 상태(교환하면 같아지는 상태)여야 한다.
해당 사다리 타기는 A와 B 때문에 구성할 수 없다.
왜냐하면 A와 B가 2칸 이상 차이 나기 때문에 가로 한 칸으로는 없다.
위 경우는 구성 가능하다.
모든 알파벳 배열이 1칸 이하로 차이나고, 무엇보다 E와 G가 서로 교환을 통해 같아지기 때문이다.
오른쪽처럼 가로선을 그으면 완성된다.
즉 위의 내용을 요약해 보면, 사다리 타기가 성립하기 위해서는
1. 모든 알파벳 배열들이 1칸 이상 차이가 나면 안 된다.
2. 두 알파벳이 교환했을 때 서로 같아져야 한다.
이제 이 로직을 통해 사다리 타기를 구현하고 문제를 풀면 된다.
문제 구현 단계
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> k >> n;
string result; // 나와야 하는 알파벳 배열
cin >> result;
string start; // 시작하는 알파벳 배열 (ABCDE..)
for(int i = 0; i < k; i++) start.push_back('A'+i);
int delim; // ???의 인덱스
for(int i = 0; i < n; i++){
string str;
cin >> str;
for(int j = 0; j < str.length(); j++){
if(str[j] == '?') delim = i; // 경계선의 인덱스를 저장
map[i][j] = str[j];
}
}
for(int i = 0; i < delim; i++){
for(int j = 0; j < start.length(); j++){
// '-'를 만나면 j와 j+1 알파벳을 교환
if(map[i][j] == '-') swap(start[j],start[j+1]);
}
}
// 위와 똑같으나 이건 올라오는 것이기 때문에 역순 진행
for(int i = n - 1; i > delim; i--){
for(int j = 0; j < result.length(); j++){
if(map[i][j] == '-') swap(result[j],result[j+1]);
}
}
string ans = findSolution(start,result);
// 구성 불가능 시 k 개수만큼 인원수 - 1 만큼 x가 나오게 함
if(ans[0] == 'x') for(int i = 0; i < k-1; i++) cout << ans[0];
else cout << ans;
}위 코드는 main 함수 부분이자, 사다리 타기를 구현한 부분이다.
결과적으로 나와야 할 알파벳 배열 result와 출발할 때 사다리 배열 ABCDE를 미리 정의해 두고,
"???"가 나오는 delim을 기준으로 나눠둔다.
그 기준을 통해 start에서부터 사다리 타기를 해서 내려오고,
result에서는 delim을 향해 올라오도록 한다.
이렇게 비교할 두 알파벳 배열을 최대한 근접하게 해 둔 뒤
findSolution(start, result)를 통해 두 배열이 구성 가능한지를 판단한다.
// 구성가능한지 판단하는 함수
string findSolution(string start, string result){
int idx = 0;
string ans = ""; // 반환할 알파벳 배열
while(idx < start.length()-1){
// 알파벳이 서로 같을 경우
if(start[idx] == result[idx]) {
ans.push_back('*'); // 가로선을 그을 필요 없음
}
// 교환하면 알파벳이 같아질 경우
else if(start[idx] == result[idx+1]
&& start[idx+1] == result[idx]) {
swap(start[idx],start[idx+1]);
ans.push_back('-'); // 가로선을 그음
}
// 두 경우에 해당하지 않으면 구성X
else return "x";
idx++; // 알파벳 하나하나씩 살펴봄
}
return ans;
}해당 배열이 구성가능한지를 판단하는 findSolution함수이다.
idx는 알파벳 배열 인덱스를 뜻하며 0번 인덱스부터 순차적으로 살펴본다.
출력으로는 가로선을 그으면 -, 긋지 않으면 *을 출력해야 하므로,
위아래가 서로 같으면 *교환해서 같아질 수 있으면 -을 추가한다.
두 경우에 해당하지 않으면 구성하지 못하는 것이므로 "x"를 반환한다.
핵심적인 함수에 대한 설명은 여기가 끝이다.
이제 모든 전체코드에 대해 아래에 올리고 설명을 끝내겠다.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int k, n;
char map[1001][27];
// 구성가능한지 판단하는 함수
string findSolution(string start, string result){
int idx = 0;
string ans = ""; // 반환할 알파벳 배열
while(idx < start.length()-1){
// 알파벳이 서로 같을 경우
if(start[idx] == result[idx]) {
ans.push_back('*'); // 가로선을 그을 필요 없음
}
// 교환하면 알파벳이 같아질 경우
else if(start[idx] == result[idx+1]
&& start[idx+1] == result[idx]) {
swap(start[idx],start[idx+1]);
ans.push_back('-'); // 가로선을 그음
}
// 두 경우에 해당하지 않으면 구성X
else return "x";
idx++; // 알파벳 하나하나씩 살펴봄
}
return ans;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> k >> n;
string result; // 나와야 하는 알파벳 배열
cin >> result;
string start; // 시작하는 알파벳 배열 (ABCDE..)
for(int i = 0; i < k; i++) start.push_back('A'+i);
int delim; // ???의 인덱스
for(int i = 0; i < n; i++){
string str;
cin >> str;
for(int j = 0; j < str.length(); j++){
if(str[j] == '?') delim = i; // 경계선의 인덱스를 저장
map[i][j] = str[j];
}
}
for(int i = 0; i < delim; i++){
for(int j = 0; j < start.length(); j++){
// '-'를 만나면 j와 j+1 알파벳을 교환
if(map[i][j] == '-') swap(start[j],start[j+1]);
}
}
// 위와 똑같으나 이건 올라오는 것이기 때문에 역순 진행
for(int i = n - 1; i > delim; i--){
for(int j = 0; j < result.length(); j++){
if(map[i][j] == '-') swap(result[j],result[j+1]);
}
}
string ans = findSolution(start,result);
// 구성 불가능 시 k 개수만큼 인원수 - 1 만큼 x가 나오게 함
if(ans[0] == 'x') for(int i = 0; i < k-1; i++) cout << ans[0];
else cout << ans;
}
시행착오
1시간 시간제한을 두고 풀어봤는데, 역시 1시간 안에는 못 풀겠더라.
처음에는 BFS로 풀려고 했는데, 그렇게 어렵게 접근할 필요가 없었다.
역시 효율 측면에서는 이런 식으로 하는 게 맞는 것 같다.
그리고 인터넷을 참고할 때 더 공부가 잘되는 것 같다.
앞으로는 이런 식으로 하는 방향으로 해야겠다.
인원수랑 작대기의 개수가 달라서 엄청나게 헷갈렸다.