[JAVA] BOJ(백준) - Z - 1074

문제내용

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

1074번: Z

한수는 크기가 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

---

문제 접근 방법

처음 했던생각은 그냥 NxN 행렬을 조건을 추가해 처음부터 끝까지 탐색하면서 r,c가 몇번째인지 찾는 방법이였는데 N은 2^15까지 가기때문에 이렇게 하면 대충 계산해도 최악의 경우O(2^15 * 2^15) 의 시간복잡도가 걸리게되고 문제 총 1,073,741,824번의 연산을 하게된다.

따라서 최악의 경우 약 10초 이상이 걸릴것으로 예상되기 때문에 문제조건인 0.5초안에 답을 구하기란 불가능하다고 판단됐고 더 효율적인 방법이 필요했다. 그리고 그 방법은 아래와 같다.

 

r행 c열이 NxN 행렬에서 어디에 위치해 있는지 찾는것이다.

어차피 정사각 행렬이기 때문에 1,2,3,4 사분면으로 나눠 생각해서 몇사분면에 위치해있는지 찾으면된다.

r행 c열이 속해있는 사분면을 계속 2x2 행렬로 될때까지 나누면서 카운트를해 답을 구했다.

이 과정에서  나눠진 사분면을 다시 나눠야하는 과정이 발생하기 때문에 재귀를 사용하게 됐고, 이런 알고리즘이 Divide & Conquer(분할 정복) 알고리즘 이라고 한다. 아무튼 이과정을 순서대로 써보면 아래와 같은 로직이 나온다.

 

로직

1. 행과 열의 mid값 구하기
   NxN 행렬에서 행과 열의 mid값을 "rowMid = (행끝점-행시작점)/2  , colMid = (열끝점-열시작점)/2" 로 구해준다.
   mid값을 구하는 이유는 문제에서 입력받은 r,c 의 위치를 찾기 위해서이다.
   
   예를들어 입력값 3 7 7 을 입력받았을때 r, c는 8x8행렬에서 4사분면에 위치한다.
   r,c가 4사분면에 있다는것을 알수 있는 이유는 rowMid = (8-0)/2 , colMid = (8-0)/2 를 구한뒤
   r >= rowMid && c >= colMid 라면 4사분면에 위치해 있다는 것을 알 수 있다.
   1,2,3 사분면도 마찬가지로 조건만 다르게하여 구분해낼 수 있다.
2. r,c 갱신
   사분면을 나눌때마다 나눈 사분면 기준으로 r,c의 값은 바뀌어야 한다.
   위의 예를 보면 처음엔 7,7 이 였지만 4사분면에 위치해 있는것을 알게되고 4사분면 기준으로 살펴보게되면
   r,c는 7,7 -> 3,3 으로 바뀌어야 한다.
   따라서 기준이 되는 사분면 위치에 따라 r,c를 갱신해줘야한다.
   
   
3. 위치 카운트
   만약 r,c가 4사분면에 위치해있다면 결국 1,2,3사분면을 차례대로 돌고 온것이기 때문에 "(사분면 하나의 크기 * 3) + 현재까지 카운트한값" 이 된다.
   2,3 사분면도 마찬가지 방식으로 구하면되지만 1사분면의 경우는 z가 1사분면부터 먼저 돌기 시작하기 때문에 따로 카운트를 계산해줄 필요가 없다.

위와 같은 방식으로 N이 0이될때까지 재귀로 풀어주면된다.

말로 설명이 어려운데 코드에 주석을 달아놨으니 보면서 생각해보자.

 

참고

코드를 보면 알겠지만 mid값의 역할이 r,c의 사분면을 찾는것이긴 한데.. 결국 사분면 하나에서 변의길이를 나타낼때 사용되기 때문에 굳이 저렇게 코드를 안짜도 될꺼같다. 그냥 각 사분면을 나눌때마다 변의 길이를 활용하면 될듯..

---

풀이

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

public class Main {
	static int r, c, ans;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int length = (int) Math.pow(2,N);//행렬의 처음 길이
		r = Integer.parseInt(st.nextToken());//행위치
		c = Integer.parseInt(st.nextToken());//열위치
		ans = 0;//답
		
		//ZDC(입력값, 행시작점, 행끝점, 열시작점, 열끝점);
		ZDC(N,0,length,0,length);
		System.out.println(ans);
	}
	
	public static void ZDC(int N, int rowS, int rowE, int colS, int colE) {
		if(N==0) return;//N==0이라는 말은 더이상 나눌수 없다는 말.
		
		int rowMid = (rowE-rowS)/2;//행 중간점
		int colMid = (colE-colS)/2;//열 중간점
		
		if(r<rowMid && c<colMid) { //r,c가 1사분면에 있을때
			ZDC(N-1, rowMid, rowMid*2, colMid, colMid*2);
		}else if(r<rowMid && c>=colMid) { //r,c가 2사분면에 있을때
			ans += colMid*rowMid; //1사분면 방개수 만큼 카운트
			c -= colMid; //2사분면이면 열만 갱신
			ZDC(N-1, rowMid, rowMid*2, colMid, colMid*2);
		}else if(r>=rowMid && c<colMid) { //r,c가 3사분면에 있을때
			ans += 2*(colMid*rowMid);//1,2사분면 방개수 만큼 카운트
			r -= rowMid; //3사분면이면 행만 갱신
			ZDC(N-1, rowMid, rowMid*2, colMid, colMid*2);
		}else if(r>=rowMid && c>=colMid) { //r,c,가 4사분면에 있을때
			ans += 3*(colMid*rowMid); //1,2,3사분면 방개수 만큼 카운트
			r -= rowMid; //4사분면이면 행도 갱신
			c -= colMid; //4사분면이면 열도 갱신
			ZDC(N-1, rowMid, rowMid*2, colMid, colMid*2);
		}
		
	}
}

---

마치며

분할 정복이라는 알고리즘 문제였다. 어렵지 않은 문제인데 재귀를 사용하면서 어떻게 찾아갈지 생각해야하기 때문에 좀 오래걸린 문제다.

그리고 이문제에선 위에서 말했지만 mid값대신 변의 길이를 활용하는게 더 간단할꺼 같다.