[백준] 2469. 사다리 타기
문제 링크
풀이 과정
처음에 생각했던 방법은 다음과 같습니다.
- 사다리의 감춰진 한 줄을 직접 그린다.
- 한 명씩 완성된 사다리를 통해 아래로 내린다.
- 도달한 순서에 맞게 배치한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class BOJ_2469_사다리타기 {
static int N, K;
static char[][] map;
static int row, col;
static int target_row;
static String target;
static char[] order;
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());
row = N;
col = K + K - 1;
target = br.readLine();
map = new char[N][K + K - 1];
order = new char[col];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < input.length(); j++) {
map[i][j * 2 + 1] = input.charAt(j);
}
if (map[i][1] == '?') target_row = i;
}
draw(1, false);
draw(1, true);
StringBuilder sb = new StringBuilder();
for (int j = 0; j < K - 1; j++) sb.append('x');
System.out.println(sb);
}
static void draw(int idx, boolean isHor) {
if (idx == col) {
reach();
return;
}
if (isHor) {
map[target_row][idx] = '*';
draw(idx + 2, false);
}
if (!isHor) {
map[target_row][idx] = '*';
draw(idx + 2, false);
map[target_row][idx] = '-';
draw(idx + 2, true);
}
}
static void reach() {
for (int person = 0; person < col; person += 2) {
int i = 0;
int j = person;
while (true) {
while (i < row && ((isRange(i, j - 1) && map[i][j - 1] == '*' && isRange(i, j + 1) && map[i][j + 1] == '*')
|| (!isRange(i, j - 1) && isRange(i, j + 1) && map[i][j + 1] == '*')
|| (isRange(i, j - 1) && map[i][j - 1] == '*') && !isRange(i, j + 1)
)) {
i++;
}
if (i == row) {
order[j] = (char) (person / 2 + 65);
break;
}
if (isRange(i, j + 1) && map[i][j + 1] == '-') {
i++;
j += 2;
}
if (isRange(i, j - 1) && map[i][j - 1] == '-') {
i++;
j -= 2;
}
}
}
StringBuilder sb = new StringBuilder();
for (int j = 0; j < col; j++) {
if (order[j] == '\0') continue;
sb.append(order[j]);
}
if (sb.toString().equals(target)) {
sb = new StringBuilder();
for (int j = 0; j < col; j++) {
if (map[target_row][j] == '\0') continue;
sb.append(map[target_row][j]);
}
System.out.println(sb.toString());
System.exit(0);
}
}
static boolean isRange(int x, int y) {
return x >= 0 && x < row && y >= 0 && y < col;
}
}
하지만 위 방식으로는 시간 초과가 발생하고, 그 이유는 다음과 같이 생각해볼 수 있습니다.
- 감춰진 줄을 그리기 위해 매번 순열을 만드는 작업.
- 상단에서 하단으로 모든 사람들을 내리는 작업.
- 하단에서 완성된 순서가 저장된 문자 배열을 문자열로 변경하는 작업.
사다리를 타기 전과 타고 난 후의 순서는 정해져 있습니다. 이를 이용해 최상단에서 ?줄을 만나기 전까지의 순서를 구하고, 거꾸로 최하단에서 ?줄을 만나기 전까지의 순서를 구한 뒤, 페어를 이루어 자리를 바꿔주면 완성이 됩니다.
주황색 박스 는 위에서부터 사다리를 태워 각 줄에 도착한 참가자들의 순서를 왼쪽부터 나열한 것을 표현합니다. 반대로, 녹색 박스 는 아래서부터 사다리를 태워 각 줄에 도착한 참가자들의 순서를 왼쪽부터 나열한 것을 표현합니다.
주황색 박스는 ? 줄 바로 윗줄에 도착한 참가자들의 순서를 보여줍니다. 반대로 녹색 박스는 ? 줄 바로 아랫줄에 도착한 참가자들의 순서를 보여줍니다. 결과적으로, 주황색 박스에 적힌 문자열을 녹색 박스 안에 적힌 문자열로 변경하면서, 자리바꿈이 필요하다면 - 를, 자리를 바꾸지 않아도 되면 * 를 사다리에 표기하면 정답이 됩니다.
K = Integer.parseInt(br.readLine());
N = Integer.parseInt(br.readLine());
StringBuilder topDown = new StringBuilder();
StringBuilder bottomUp = new StringBuilder(br.readLine());
Deque<String> deque = new LinkedList<>();
boolean isFound = false;
초기에 설정하는 변수입니다.
- 문제의 K와 N을 입력받아 저장합니다.
- topDown : 위로부터 아래로 진행되는 순서를 저장하기 위한 StringBuilder 객체입니다.
setCharAt 메소드로 두 문자의 자리를 바꾸기 위해 StringBuilder 클래스를 사용했습니다. - bottomUp : 아래로부터 위로 진행되는 순서를 저장하기 위한 StringBuilder 객체입니다.
- deque : ? 줄을 기준으로 그 후의 줄 입력은 거꾸로 진행하기 위해 스택이 필요합니다.
- isFound : ? 줄을 찾았음을 저장하는 변수입니다. 위에서 설명했듯이, ? 줄 이후의 사다리 줄 정보들은 스택에 담기 위한 조건에 필요해 사용했습니다.
for (int i = 0; i < K; i++) {
topDown.append((char) (i + 65));
}
먼저 topDown 문자열에는 초기 순서를 입력해줍니다. 예를 들어, 참가자가 10명이라면, 인덱스 값에 65를 더하여 만들어진 아스키코드를 문자(A-J)로 변환하여 뒤에 붙여줍니다.
for (int i = 0; i < N; i++) {
String command = br.readLine();
if (command.charAt(0) == '?') {
isFound = true;
continue;
}
if (isFound) {
deque.add(command);
} else {
topDown = swap(topDown, command);
}
}
사다리 모든 줄을 각각 변수 command 에 담습니다. ? 줄을 만나기 전이라면 swap 메소드 를 통해 자리 조정을 진행한 뒤 바뀐 순서를 다시 topDown 에 담아주고, ? 줄을 만난 후라면 스택에 해당 사다리 줄 정보를 담아둡니다.
while (!deque.isEmpty()) {
bottomUp = swap(bottomUp, deque.pollLast());
}
스택을 의미하는 변수 deque 에는 사다리 정보들이 순서대로 담겨있습니다. top 을 하나씩 꺼내 해당 사다리 줄을 이용해 swap 메소드를 호출해 자리를 조정해줍니다. 조정 결과를 다시 bottomUp 에 담습니다.
StringBuilder answer = new StringBuilder();
for (int i = 0; i < topDown.length() - 1; i++) {
if (topDown.charAt(i) == bottomUp.charAt(i)) answer.append('*');
else {
answer.append('-');
topDown = swap(topDown, i);
}
}
topDown 의 최종 문자열을 bottomUp 으로 변화시키는 과정입니다.
- i 번 문자가 서로 같다면 * 을 붙여줍니다.
- 다르다면, i번 문자와 i+1번 문자의 위치를 바꿔줍니다. 또한 건너갈 막대가 필요하므로
-를 붙여줍니다.
static StringBuilder swap(StringBuilder sb, String command) {
for (int i = 0; i < command.length(); i++) {
if (command.charAt(i) == '-') {
sb = swap(sb, i);
}
}
return sb;
}
static StringBuilder swap(StringBuilder sb, int x) {
char tmp = sb.charAt(x);
sb.setCharAt(x, sb.charAt(x + 1));
sb.setCharAt(x + 1, tmp);
return sb;
}
swap 메소드는 오버로딩 메소드입니다. 둘 다 인자로 StringBuilder 를 받습니다.
- 위의 swap 메소드는 인자로 사다리 하나의 줄 정보를 추가로 받습니다. 한 줄 각각의 command.charAt(i) 는 가로 막대 유무 정보를 의미합니다. - 라면, i번째 문자와 i+1번째 문자를 바꾸는 아래의 swap 메소드를 호출합니다.
- 아래의 swap 메소드는 인자로 인덱스를 받습니다. x 번째 문자와 x+1 번째 문자의 위치를 바꿉니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
public class Main {
static int K, N;
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());
StringBuilder topDown = new StringBuilder();
StringBuilder bottomUp = new StringBuilder(br.readLine());
Deque<String> deque = new LinkedList<>();
boolean isFound = false;
for (int i = 0; i < K; i++) {
topDown.append((char) (i + 65));
}
for (int i = 0; i < N; i++) {
String command = br.readLine();
if (command.charAt(0) == '?') {
isFound = true;
continue;
}
if (isFound) {
deque.add(command);
} else {
topDown = swap(topDown, command);
}
}
while (!deque.isEmpty()) {
bottomUp = swap(bottomUp, deque.pollLast());
}
StringBuilder answer = new StringBuilder();
for (int i = 0; i < topDown.length() - 1; i++) {
if (topDown.charAt(i) == bottomUp.charAt(i)) answer.append('*');
else {
answer.append('-');
topDown = swap(topDown, i);
}
}
System.out.println(topDown.toString().equals(bottomUp.toString()) ? answer : "x".repeat(K - 1));
}
static StringBuilder swap(StringBuilder sb, String command) {
for (int i = 0; i < command.length(); i++) {
if (command.charAt(i) == '-') {
sb = swap(sb, i);
}
}
return sb;
}
static StringBuilder swap(StringBuilder sb, int x) {
char tmp = sb.charAt(x);
sb.setCharAt(x, sb.charAt(x + 1));
sb.setCharAt(x + 1, tmp);
return sb;
}
}
댓글남기기