[백준] 1074 - Z JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

1074번: Z

문제

문제
한수는 크기가 2N × 2N인 2차원 배열을 ZZ 모양으로 탐색하려고 한다. 예를 들어, 2 × 2 배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

sample 1

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

sample2

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

sample3

입력
첫째 줄에 정수 N, r, c가 주어진다.

출력
r행 c열을 몇 번째로 방문했는지 출력한다.

접근방법

 문제에서 주어진 제한 시간을 째려보자. 제한은 0.5초다. 2^N의 배열을 위 조건에 맞게 넘버링 후 result [r][c]를 출력하려고 한다면, 반드시 시간 초과가 날 것이다. 즉 문제는 너 배열 없이 문제를 구해볼 수 있니?라고 묻고 있다.  또한 문제의 Z형태가 반복되어 사용되고 있다. 이 점을 인지하고 풀이로 들어가자. 

풀이

 Sample3을 예로 보자. Sample 3의 넘버링 방식을 수기로 작성해보면 다음과 같다.

 

1. 배열을 4 분할한다. 배열의 순서는 상단 좌측, 상단 우측 , 하단 좌측, 하단 우측 순이다.
2. 나눈 배열의 크기가 1이 아니라면, 다시 1번을 반복한다.
3. 나눈 배열의 크기가 1이라면 상단 좌측, 상단 우측 , 하단 좌측, 하단 우측 순으로 번호를 매긴다. 

 이러한 재귀적인 과정을 통해 마지막 번호까지 넘버링을 하게 된다. 이 문제를 배열 없이 해결하려면, 이러한 재귀적인 과정에서 규칙성을 찾아야 한다.  본인은 다음과 같은 규칙성을 찾아내 풀었다. 

 

 Sample3을 예제로 N=3인 경우, 처음 4 분할하고, 각 분할된 면들을 문제가 넘버링하는 순서에 따라 K사분면이라고 부르겠다.

 

 

 먼저 좌표가 어디에 있는지부터 찾아보자. 좌표를 찾는 방법은 쉽다. 배열을 4 분할하여, 자신이 찾는 r행 c열이 나올 때까지, r행 c열을 포함한 구역만 재귀적으로 구하면 된다. 함수 한 번에 찾을 영역이 1/4씩 줄어든다. 

 

 그렇다면 위치는 찾았는데, 어떻게 값을 구할까? 

각 사분면들은 16개의 값을 가질 수 있으므로, 각 사분면의 시작 값은 아래와 같다.

 

• 1 사분면의 시작 값은  첫 번째 사분면이므로  0+(1-1)*(4*4) = 0이다.
• 2 사분면의 시작 값은  두 번째 사분면이므로  0+(2-1)*(4*4) = 16이다.
• 3 사분면의 시작 값은  세 번째 사분면이므로  0+(3-1) 2*(4*4) =32이다.
• 4 사분면의 시작 값은  네 번째 사분면이므로  0+(4-1)*(4*4) = 48이다.

각 사분면마다의 식의 의미는 배열 시작 값 + (사분면 번호 -1) *(영역의 크기 )이다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(stk.nextToken());
        int r = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken());

        System.out.println(solution(N,r,c,0,0,0));
    }

    private int solution(int n, int r, int c,int start_x,int start_y,int start_val) {


        int cur_n = n-1;
        //분할할 길이
        int len = (int) Math.pow(2,cur_n);
        int row=0,col=0;
        int val_wieght = 0;
        int[][] loc = {{0,0},
                {0,1},
                {1,0},
                {1,1}} ;

       //영역 분할
        for (int i = 0 ; i < 4 ; i++){
            row = start_x + loc[i][0]*len;
            col = start_y + loc[i][1]*len;
            //해당 row, col 이 가지고 있는 순번을 구하기 위한 가중치
            val_wieght = i*len*len;
            // 해당 영역에 좌표가 있다면 out
            if(r>= row && r<row+len && c>=col && c < col+len ){
                break;
            }
        }

        //row col 이 해당 좌표라면 return
        if(r==row && c == col ){
            return start_val +val_wieght;
        }

        //아니라면 다시 해당영역 분할
        return solution(cur_n,r,c,row,col,start_val+val_wieght);

    }


}

결과

 

 

 배열을 사용했다면, 무지 성으로 풀었을 것 같은데, 배열 없이 구하자니, 규칙성을 구하고 표현하는 부분에서 시간을 오래 쓴 듯하다.  1) 해당 목적지를 어떻게 하면 빠르게 찾을까? 와 2) 해당 목적지에서 요구하는 값을 어떻게 구할 것인가? 를 미리 정의하고 시작했다면 조금 더 시간 소모 없이 풀었을 것 같다.

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.