백준 2713 자바 - 규현이의 사랑을 담은 문자메시지 (boj 2713 java)

문제 : boj2713

 

 

  실버치고 구현이 상당히 빡쌘 문제이다. 아마 곧 골드까지 올라갈 것 같다. 이정도면 아무리 별다른 알고리즘 필요없는 구현문제라도 골드5정도가 맞다.

 

  내 경우엔 최대한 원툴(?)로 구현을 하고 싶었다. 따라서 약간의 아이디어를 써서 좀 쉽게 진행했다. 다음의 입력을 확인해보자.

1
4 4 ACM

  4x4일 경우, 그보다 2칸씩 크게 미리 배열을 만든다. 즉 6x6으로 만들고, 외곽을 1칸씩 띄운 상태로 중앙의 4x4에 '-1'과 같이 나올 수 없는 수를 쓴다. 해당 위치에 들어가야하는데 아직 값이 안들어갔다는 의미로 사용했다. 그리고 (1,0) 지점에서 시작하고, 처음 진행하는 방향은 항상 우측방향이다.

  그리고 방향은 우측:0, 아래:1, 좌측:2, 위:3 으로 정한다. 소용돌이가 진행해야하는 순서와 동일하다! 그럼 이제 'ACM'을 한 글자씩 읽어서 5자리 2진수로 변경해서 소용돌이 형태로 차례대로 넣을 것이다. 우선 시작지점에서 현재 방향대로 1칸을 전진한다. 전진한 곳의 값이 -1이라면 거기에 값을 넣는다! 이 때 입력으로 주어진 문자열을 2진수로 변경했을 때 각 자리수의 값이 무엇인지는 내 경우엔 비트연산으로 찾았다(arr[cr][cc] = (c&1<<bit)!=0?1:0; 부분)

  그렇게 진행하다가 다음에 진행할 곳이 -1이 아닌 곳을 발견한다면 현재 방향값을 +1 시킨다. 그럼 우측->아래->좌측->위 가 차례대로 변경된다. 이 때 해당 값이 4가 된다면 0으로 다시 변경하면 된다. 즉, 배열을 상하좌우로 2칸씩 늘리는 방식을 통해 별도로 인덱스가 넘어갈 것을 걱정하지 않고 하나의 로직으로 원툴로 짤 수 있게 된다.

최종적으로 다음과 같이 될 것이다. 5개씩 3번 진행했으므로 마지막칸에 -1이 하나 남는다.

이후 외곽의 한줄씩은 제외하고, (1,1)부터 (4,4)까지 행 우선으로 출력한다. 이 때 남아있는 -1은 0으로 변경하여 출력해주면 된다. 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int[] dr = {0, 1, 0, -1};
    private static final int[] dc = {1, 0, -1, 0};

    private void add(int[][] arr, String msg) {
        int dir = 0;
        int cr = 1;
        int cc = 0;
        for (int i = 0; i < msg.length(); i++) {
            int c = msg.charAt(i)==' '?0:msg.charAt(i)-'A'+1;
            int bit = 5;
            while (bit-->0) {
                while (arr[cr+dr[dir]][cc+dc[dir]] != -1) {
                    dir++;
                    if (dir == 4)
                        dir = 0;
                }
                cr+=dr[dir];
                cc+=dc[dir];
                arr[cr][cc] = (c&1<<bit)!=0?1:0;
            }
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            String str = br.readLine();
            StringTokenizer st = new StringTokenizer(str);
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            String msg = str.substring((r>=10?2:1) + (c>=10?2:1) + 2);

            int[][] arr = new int[r+2][c+2];
            for (int i = 1; i <= r; i++) {
                for (int j = 1; j <= c; j++) {
                    arr[i][j] = -1;
                }
            }
            add(arr, msg);
            for (int i = 1; i <= r; i++) {
                for (int j = 1; j <= c; j++) {
                    sb.append(arr[i][j]==-1?0:arr[i][j]);
                }
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}