[백준_1074번] Z

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가 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_1074 {
	static int count=0;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int r=sc.nextInt();
		int c=sc.nextInt();
		
		int size=(int)Math.pow(2,n); // 2^n×2^n인 2차원 배열의 한 변의 크기 계산
		
		find(size,r,c);
		System.out.println(count);
	}
	
	// 2^n×2^n인 배열은 4등분 해가며 r행 c열은 언제 방문하는지 찾는다.
	static void find(int size, int r, int c) {
		if(size==1)
			return;
		
		/*
		 * 1사분면에 있다면 아직 아무곳도 방문하지 않은 상태이므로
		 * size만 절반으로 줄인 값을 매개변수로 하여 재귀호출 한다.
		 */
		if(r<size/2 && c<size/2) 
			find(size/2,r,c);
		
		/*
		 * 2사분면에 있다면 1사분면을 방문한 상태이므로 1사분면의 칸 개수를 누적해주고
		 * 2사분면에서의 r,c의 상태위치 r,c-size/2를 매개변수로 하여 재귀호출 한다.
		 */
		else if(r<size/2 && c>=size/2) {
			count+=size*size/4;
			find(size/2,r,c-size/2);
		}
		
		/*
		 * 3사분면에 있다면 1,2사분면을 방문한 상태이므로 1,2사분면의 칸 개수를 누적해주고
		 * 3사분면에서의 r,c의 상태위치 r-size/2,c를 매개변수로 하여 재귀호출 한다.
		 */
		else if(r>=size/2 && c<size/2) {
			count+=(size*size/4)*2;
			find(size/2,r-size/2,c);
		}
		
		/*
		 * 4사분면에 있다면 1,2,3사분면을 방문한 상태이므로 1,2,3사분면의 칸 개수를 누적해주고
		 * 4사분면에서의 r,c의 상태위치 r-size/2,c-size/2를 매개변수로 하여 재귀호출 한다.
		 */
		else {
			count+=(size*size/4)*3;
			find(size/2,r-size/2,c-size/2);
		}
	}
}

 

[고찰]

 이번 문제는 백트래킹을 사용하여 해결하는 문제였다. 이전부터 문제만 읽고 해결방법이 떠오르지 않아 미뤄뒀던 문제였지만 다른 사람의 코드를 참고해서라도 풀어보자 다짐했다. 이번 문제의 핵심은 배열을 4분면으로 쪼개가면서, r행 c열이 몇 번째 사분면에 속하는지를 구하는 것을 재귀적으로 수행하는 것이다. 즉, r행 c열이 속한 배열의 범위를 계속해서 4등분 해나가는 것이다. 해결방법을 보고도 이해하는데 시간이 좀 걸렸지만 이해하고 나니 그리 어렵게 느껴지지 않은 문제였다.