[JAVA] baekjoon 1891 사분면

문제

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

1891번: 사분면

 

나의 풀이

1. 주어진 사분면 정보를 기반으로 위치 (row, column) 찾는다.

2. 찾은 위치를 이동시키고 범위를 확인한다.

  - 범위가 벗어나면 -1을 출력하고 종료한다.

3. 이동한 위치의 사분면을 찾는다.

 

 

코드 뜯어보기

초기화 및 입력을 받는 코드입니다.

저는 변수 d를 이용해서 한 변의 길이를 의미하는 size 변수를 미리 할당해놓았습니다.

d는 최대 50까지 들어올 수 있기 때문에 size도 long 타입으로 선언합니다.

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int d = Integer.parseInt(st.nextToken());
    String quadrantInfo = st.nextToken();
    long size = (long)Math.pow(2, d);

    st = new StringTokenizer(br.readLine());
    long moveCol = Long.parseLong(st.nextToken());
    long moveRow = Long.parseLong(st.nextToken());

 

String타입인 사분면으로 위치를 찾는 메서드입니다.

각 사분면에 따라 크기를 더해나갔고, 점점 사분면이 분할될 수록 size도 절반으로 줄도록 했습니다. 

반복문은 크기만큼 돕니다. (변수 d와 같은 값)

private static void findLocation(String quadrantInfo, long size) {
    for (int i=0; i<quadrantInfo.length(); i++) {
        size/=2;
        int quardrant =quadrantInfo.charAt(i) - '0';
        switch (quardrant) {    // 2사분면은 그대로
            case 1 : colLoc += size; break;
            case 3 : rowLoc += size; break;
            case 4 :
                rowLoc += size;
                colLoc += size;
        }
    }
}

 

위치를 찾았다면 해당 위치를 이동시킨 후 범위에 있는지 확인하는 코드입니다.

이동시킬 때 row는 위아래로 이동시키는데 문제에서 위로 이동시킬 때 양수라고 했으므로 row에 대해서만 마이너스로 진행하면 됩니다.

만약 이동할 수 있다면 findQuadrant 메서드를 호출합니다.

// main 메서드
        //2. 위치 이동
        rowLoc -= moveRow;   // +1이 위로 이동=> 좌표 상은 -
        colLoc += moveCol;
        // 3. 이동한 위치의 사분면 찾기
        if (outOfBoundary(rowLoc, colLoc, size)) System.out.println("-1");
        else
            findQuadrant(rowLoc, colLoc, size);
	//생략
    }
    
// main메서드 외부
    private static boolean outOfBoundary(long row, long col, long size) {
            return (row<0 || row>= size || col<0 || col>= size);
    }

 

이동한 최종 위치에 대해서 정답을 찾기 위해 분할을 반복하는 메서드입니다. (재귀 이용)

그리고 어떤 사분면이냐에 따라 위치를 size만큼 -(마이너스) 하는데 

해당 문제에서는 2사분이 왼쪽&위에 위치해서 위치를 이동시킬 필요가 없는 위치입니다.

 

매 재귀에서 어떤 사분면에 속하는지 StringBuilder에 추가해주었습니다.

size가 계속해서 반씩 줄다가 길이가 1이 됐을 때 종료합니다. 

// 위치에 따른 사분면 String을 찾는다.
private static void findQuadrant(long row, long col, long size) {
    if (size == 1) {
        System.out.println(answerSB);
        return;
    }
    if (row < size / 2 && col >= size / 2) {//1
        answerSB.append(1);
        findQuadrant(row, col - size / 2, size / 2);
    }
    if (row < size / 2 && col < size / 2) {//2
        answerSB.append(2);
        findQuadrant(row, col, size / 2);
    }
    if (row >= size / 2 && col < size / 2) {//3
        answerSB.append(3);
        findQuadrant(row - size / 2, col, size / 2);
    }
    if (row >= size/2 && col >= size/2) {//4
        answerSB.append(4);
        findQuadrant(row - size / 2, col - size / 2, size / 2);
    }
}

 

 

NumberFormatException 에러

혹시 계속 NumberFormatException 에러가 발생한다면 아래 반례를 실행해봅시다.

50 12341234123412341234123412341234123412341234123412
500000 3000000000

반례 출처

 

원인은?

문제에서 두번째 줄에 입력받는 이동 x, y는 2의 50승까지 들어올 수 있습니다.

그렇기 때문에 int 타입으로는 (위 반례와 같이) 크기가 큰 수가 들어왔을 때 잘못된 답이 나옵니다.

 

필자는 위 에러를 해결하기 위해 (타입이 문제라는 생각을 못해서..) 괜한 곳을 많~이 수정했습니다.

그래서 아래 코드는 초기 코드에서 많이 수정된 코드입니다.

• 인자로 StringBuilder를 넘겨주던 코드  => static으로 선언
  • 그래서 초기에는 StringBuilder에 값을 추가해주는 것과 동시에 넘겨주도록 했습니다.
    findQuadrant(row - size / 2, col - size / 2, size / 2, answerSB.append(4));
• 인자로 row, col을 갖고있는 배열을 넘겨주는 것 => 배열이 아닌 각각의 변수로 넘겨줌

 

나의 전체 코드

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

public class boj_1891_13 {
    static long rowLoc = 0;
    static long colLoc = 0;
    static StringBuilder answerSB = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int d = Integer.parseInt(st.nextToken());
        String quadrantInfo = st.nextToken();
        long size = (long)Math.pow(2, d);

        st = new StringTokenizer(br.readLine());
        long moveCol = Long.parseLong(st.nextToken());
        long moveRow = Long.parseLong(st.nextToken());

        //1. 사분면에 따라 위치 찾기
        findLocation(quadrantInfo, size);
        //2. 위치 이동
        rowLoc -= moveRow;   // +1이 위로 이동=> 좌표 상은 -
        colLoc += moveCol;
        // 3. 이동한 위치의 사분면 찾기
        if (outOfBoundary(rowLoc, colLoc, size)) System.out.println("-1");
        else
            findQuadrant(rowLoc, colLoc, size);
    }

    // 위치에 따른 사분면 String을 찾는다.
    private static void findQuadrant(long row, long col, long size) {
        if (size == 1) {
            System.out.println(answerSB);
            return;
        }
        if (row < size / 2 && col >= size / 2) {//1
            answerSB.append(1);
            findQuadrant(row, col - size / 2, size / 2);
        }
        if (row < size / 2 && col < size / 2) {//2
            answerSB.append(2);
            findQuadrant(row, col, size / 2);
        }
        if (row >= size / 2 && col < size / 2) {//3
            answerSB.append(3);
            findQuadrant(row - size / 2, col, size / 2);
        }
        if (row >= size/2 && col >= size/2) {//4
            answerSB.append(4);
            findQuadrant(row - size / 2, col - size / 2, size / 2);
        }
    }

    private static boolean outOfBoundary(long row, long col, long size) {
        return (row<0 || row>= size || col<0 || col>= size);
    }

    private static void findLocation(String quadrantInfo, long size) {
        for (int i=0; i<quadrantInfo.length(); i++) {
            size/=2;
            int quardrant =quadrantInfo.charAt(i) - '0';
            switch (quardrant) {    // 2사분면은 그대로
                case 1 : colLoc += size; break;
                case 3 : rowLoc += size; break;
                case 4 :
                    rowLoc += size;
                    colLoc += size;
            }
        }
    }
}