이번에 풀어본 문제는
백준 2469번 사다리 타기 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int K,N;
    static char [][] map;
    static int blankLine;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(br.readLine());
        N = Integer.parseInt(br.readLine());

        // 최초 순서
        char [] origin = new char[K];
        for (int i = 0; i < K; i++) {
            origin[i] = (char)('A' + i);
        }
        // 결과 순서
        char [] result = br.readLine().toCharArray();

        map = new char[N][K - 1];

        for (int i = 0; i < N; i++) {
            String input = br.readLine();

            //?로 채워진 blank 찾아두기
            if (input.charAt(0) == '?') {
                blankLine = i;
                continue;
            }
            map[i] = input.toCharArray();
        }


        // 최초 알파벳 순서로 blankLine 까지 사다리 진행
        for (int i = 0; i < blankLine; i++) {
            for (int j = 0; j < K - 1; j++) {
                // 가로 막대를 만났을 때 swap
                if (map[i][j] == '-') {
                    char tmpChar = origin[j];
                    origin[j] = origin[j + 1];
                    origin[j + 1] = tmpChar;
                }
            }
        }

        //최종 결과도 반대로 blankLine 까지 사다리 진행
        for (int i = N - 1; i > blankLine; i--) {
            for (int j = 0; j < K - 1; j++) {
                if (map[i][j] == '-') {
                    char tmpChar = result[j];
                    result[j] = result[j + 1];
                    result[j + 1] = tmpChar;
                }
            }
        }

        //최종 두 결과를 비교하여 결과 문자열 완성시킴
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < K - 1; i++) {
            // 서로 같으면 그대로 내려가야 하므로 *
            if (origin[i] == result[i]) {
                sb.append("*");
            }
            // 인덱스 하나 차이라면 가로막대를 놔야하므로 -
            else if (origin[i] == result[i + 1]) {
                sb.append("-");
                // 그대로 진행하면 다음 반복에서 또 가로막대를 놓기 때문에 swap
                char tmpChar = origin[i];
                origin[i] = origin[i + 1];
                origin[i + 1] = tmpChar;
            }
            // 이외 경우는 2칸 이상 차이나므로 x로 채운 후 break
            else {
                sb = new StringBuilder();
                sb.append("x".repeat(K - 1));
                break;
            }
        }
        System.out.print(sb);
    }

}

📝 풀이

우리가 흔히 아는 사다리 게임입니다.
이 문제에서는 사다리 게임의 결과를 미리 입력받습니다.
이후 ''은 세로 막대, '-'는 가로 막대를 의미하는 입력이 주어집니다.
하지만 그 중 한 줄은 '?'로 채워진 빈칸 입니다.
알파벳 순서로 게임을 시작하여, 입력으로 주어진 게임의 결괏값과 동일한 결과를 도출해 낼 수 있도록 '?'로 채워진 빈칸을 완성하여 출력해봅시다.
빈 칸을 목적지로 하여 위아래(위 = 시작순서, 아래 = 입력된 결괏값)에서 각자 사다리 게임을 시작한 후 두 값을 비교하면, 빈칸이 어떤 막대로 이루어져 있는지 알아낼 수 있습니다.
세로 막대는 그대로 내려가고, 가로 막대를 만났을때는 사실상 우측에 있는 알파벳과 자리를 변경하면 되기 때문에, 이 방법으로 사다리 게임을 진행한 후 결과 문자열을 비교해줍니다.
두 값이 같다면 , 다르다면 -로 결과 문자열을 채워 출력하면 해결할 수 있습니다.

📜 후기

나올 수 있는 모든 경우의 수를 조합하여 해결하려 했는데, 풀다보니 경우의 수가 너무 방대하고 뭔가 해답이 아닌 것 같아서 다른 풀이를 참고했습니다. 정말 머리가 좋은 풀이 인 것 같네요...