[백준 2714] 문자를 받은 승환이 - JAVA

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

 

이왜실

 

주어진대로 달팽이를 구현했을 때,

 

행렬의 {r,c} 좌표 값과

입력 문자열의 r*C + c번째 값이 대응된다.

이를 통해 어떤 알파벳을 썼는지 확정하며 찾을 수 있다.

 

확정하지 않으면 alpha^(R*C / 5bit) = 27^(21*21/5) = 27^88개의 경우의 수가 존재한다.

 

 

+ rtim해야하는데 trim해도 통과돼서 요청올림

https://www.acmicpc.net/board/view/157658

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    // 달팽이 순서 -> 오, 밑, 왼, 위
    int[] dr = {0, 1, 0, -1};
    int[] dc = {1, 0, -1, 0};
    int d = 0;

    Map<Character, String> dic = new HashMap<>();

    dic.put('@', "00000"); // @을 공백으로 가정

    // key: 알파벳  value: 5자리 이진수
    for (int i = 0; i < 26; i++) {
      String bit = Integer.toBinaryString(i + 1);
      dic.put((char) (65 + i), "0".repeat(5 - bit.length()) + bit);
    }

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int T = Integer.parseInt(br.readLine());

    for (int t = 0; t < T; t++) {
      st = new StringTokenizer(br.readLine());
      int R = Integer.parseInt(st.nextToken());
      int C = Integer.parseInt(st.nextToken());
      String bin = st.nextToken();

      int r = 0;
      int c = -1; // 맨 처음 오른쪽으로 이동했을 때 {0, 0} 값이 기록되어야 함 -> {0, -1} 에서 시작

      int size = R * C;
      int cnt = size / 5; // 문제에서, mod 5한 값 외에 나머지는 안채운 값
      boolean[][] vst = new boolean[R][C];
      StringBuilder sb = new StringBuilder();

      for (int i = 0; i < cnt; i++) {
        // 0 -> 64(@), 1 -> 65(A), 26 -> 90(Z)
        boolean[] except = new boolean[27];

        for (int j = 0; j < 5; j++) {

          int tr = r + dr[d];
          int tc = c + dc[d];

          if (tr >= 0 && tr < R && tc >= 0 && tc < C && !vst[tr][tc]) {
            r = tr;
            c = tc;
            vst[r][c] = true;
            int at = C * r + c;

            for (Map.Entry<Character, String> entry : dic.entrySet()) {

              int key = entry.getKey() - 64;

              if (except[key]) {
                continue;
              }

              String value = entry.getValue();

              if (value.charAt(j) != bin.charAt(at)) { // 행렬 위치와 문자 위치 문자가 같은지 비교
                except[key] = true;
              }
            }
          } else { // 더 이상 진행 안되면 방향을 바꿈
            d++;
            d %= 4;
            j--;
          }
        }

        for (int j = 0; j <= 26; j++) {
          if (!except[j]) {
            // '@' -> ' '로 맵핑
            if (j == 0) {
              sb.append(' ');
            } else {
              sb.append((char) (j + 64));
            }
            break;
          }
        }
      }
      System.out.println(sb.toString().trim()); // 원래 문자 메시지가 공백으로 끝난다면, 그 공백을 모두 제거한 뒤에 출력한다.
    }
  }
}