[Java] BOJ 2469 | 사다리타기

어제 저녁에 건드렸는데 어제 완성은 못하고 다음날 저녁에 구현완료했다.

처음부터 깔끔하게 구현하지는 못해서 3번이나 갈아엎었지만,

꼭 될 것만 같아서 포기하지는 못했던 문제다.

 

성공!

 

 

https://www.acmicpc.net/problem/2469

2469번: 사다리 타기

 

간단히 푸는 방법 소개

 

 

 

 

---

소스코드

내 코드는 다소 길지만 로직 설명은 크게 복잡하지 않다.

- afterReach() 메서드

- afterBackReach() 메서드

이정도다. 

동일한 로직인데, afterReach()는 방향이 위에서 아래로 가는 사다리고, afterBackReach는 그 반대이다.

 

afterReach()를 통해 얻어낸 midList,

afterBackReach()를 통해 얻어낸 midList2를 서로 비교하면서,

result array (정답) 을 채워나가면 된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.*;


public class Main {

  public static char[][] map;
  public static int questionLine, k, n;

  public static char[] afterReach(char[] origin, char[] after, int idx) {    
    // reach
    int j = idx;
    char ch = origin[idx];
    for(int i = 0; i < n; i++){
      if ( i == questionLine ){
        after[j] = ch;
        break;
      }
      if (map[i][j] == '-')
        j++;
      else if (j > 0 && map[i][j-1] == '-')
        j--;
      else 
        continue;
    }
    // list after
    return after;
  }

  public static char[] afterBackReach(char[] origin, char[] after, int idx) {
    // back reach
    int j = idx;
    char ch = origin[idx];
    for(int i = n-1; i >= 0; i--){
      if ( i == questionLine ){
        after[j] = ch;
        break;
      }
       if (map[i][j] == '-')
        j++;
      else if (j > 0 && map[i][j-1] == '-')
        j--;
      else 
        continue;
    }
    // list after
    return after;
  }

  public static void main(String[] args) throws IOException{
    // treatment of input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    k = Integer.parseInt(br.readLine());
    n = Integer.parseInt(br.readLine());
    String target_str = br.readLine();
    char[] target = new char[k];
    for(int i = 0; i < k; i++){
      target[i] = target_str.charAt(i);
    }
    map = new char[n][k];
    for(int i = 0; i < n; i++){
      String str_ = br.readLine();
      if (str_.charAt(0) == '?') questionLine = i;
      for(int j = 0; j < k-1; j++){
        map[i][j] = str_.charAt(j);
      }
    }

    // list of man
    char[] man = new char[k];
    for (int i = 0; i < k; i++){
      man[i] = (char) (65 + i);
    }
	
    // get midList
    char[] after = new char[k];
    char[] after2 = new char[k];
    char[] midList = new char[k];
    char[] midList2 = new char[k];
    for(int i = 0; i < k; i++){
      midList = afterReach(man, after, i);
      midList2 = afterBackReach(target, after2, i);
    }

    // complete 'result' array by comparing midList with midList2
    char[] result = new char[k-1];

    boolean flag = false;
    for(int i = 0; i < k-1; i++){
      if(flag){
        result[i] = '*';
        flag = false;
        continue;
      }
      if (midList[i] == midList2[i]) {
        result[i] = '*';
      } else if (midList[i] == midList2[i+1]
                && midList[i+1] == midList2[i]){
        result[i] = '-';
        flag = true;
        continue;
      }
    }
    
    // print 'result' array
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    boolean notDetermined = false;
    for(int i = 0; i < k-1; i++){
      if (result[i] == '\0')
        notDetermined = true;
    }

    if (notDetermined == true){
      for(int i = 0; i < k-1; i++)
        bw.write("x");
    }
    if (notDetermined == false){
      for(int i = 0; i < k-1; i++)
        bw.write(result[i]);
    }

    bw.flush();
    bw.close();
    br.close();
  }
}