Z

0.5 초 (추가 시간 없음)

512 MB

41483

14522

10872

37.388%

문제

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

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

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

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

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

입력

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

출력

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

제한

1 ≤ N ≤ 15
0 ≤ r, c < 2N

풀이

첫번째 입력값은 N이며 배열의 크기는 2의 N 승입니다.

이후 r,c 를 입력해주는데 0부터 시작하는 인덱스 값이기 때문에 좀 더 계산은 편리합니다.

주의사항

제한 시간이 0.5초 입니다.

배열로 풀이하거나 원소 하나하나를 검사해서는 시간초과나 메모리 초과가 발생합니다.

분할 정복

전체 길이 2의 N승을 처음 길이라는 뜻으로 변수 length라고 정의했습니다.

네모의 기준은 시작하는 행(row), 시작하는 열(col), 길이로 그 네모를 정의할 수 있습니다. (왼쪽 끝점을 기준으로 정의)

처음 사각형을 기준으로 4분할합니다.

그럼 좌표는 사각형 왼쪽 위를 기준으로 하므로 4개의 좌표는 그림상 다음 위치와 같습니다.

만약 처음 사각형의 좌표가 row, col 이었다면? 4개의 사각형의 출발좌표는 다음과 같습니다.

row,col         // 1
row,col+N/2     // 2
row+N/2,col     // 3
row+N/2,col+N/2 // 4

그리고 크기는 N/2가 됩니다.

추가 조건

하지만 분할 정복만 수행하는 것이 아니라 특정 행과 열인 r, c를 찾아야 합니다.

만약 현재 사각형 안에 r, c가 없다면? 굳이 탐색할 필요가 없습니다. (왜냐하면 시간은 0.5초이기 때문입니다)

다음 조건문을 사용해 현재 사각형의 분할 정복을 포기하고 현재 사각형의 넓이만큼 카운트해버리는 방법이 있습니다.

    if(r<row || r>=row+N || c<col || c>col+N) {
        cnt += N*N; //현재 사각형의 넓이만큼 카운트를 포함합니다.
        return; //더 이상 사각형을 쪼개지 않습니다.
    }

전체 코드

import java.util.Scanner;

public class Main {
	static int r, c, cnt = 0; // 메소드에서 값을 비교하기 위한 정적할당
	static int[] dx = {0,0,1,1};  // 행 이동
	static int[] dy = {0,1,0,1}; // 열 이동
	
	static void dfs(int row, int col, int N) {
		if(N==2) { //크기가 2일 때  검사 진행

			for(int i=0; i<4; i++) {
				if(row+dx[i]==r && col+dy[i]==c) { //만약 있다면 현재까지의 카운트 출력
					System.out.println(cnt);
					break;
				}
				cnt++;
			}
			return;
		}
		if(r<row || r>=row+N || c<col || c>col+N) { //사각형 내부에 r, c가 없다면 탐색 스킵
			cnt += N*N;
			return;
		}
		dfs(row,col,N/2); // 1 사분면
		dfs(row,col+N/2,N/2); // 2 사분면
		dfs(row+N/2,col,N/2); // 3 사분면
		dfs(row+N/2,col+N/2,N/2); // 4 사분면
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		r = sc.nextInt();
		c = sc.nextInt();
		int length = (int)Math.pow(2, N); // 사각형의 한 변은 2의 N승
		
		dfs(0,0,length); // 행, 열, 크기
}
}

저작자표시