[백준 - C#] 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일 때의 예이다.

조건

시간제한 : 0.5초
메모리 제한 : 512 MB

입력

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

출력

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

 

문제정리

1. 한수의 크기가 2^N * 2^N인 2차원 배열을 Z모양으로 탐색해야합니다.
2. N>1 인 경우에는 2^N-1 * 2^N-1로 4등분 후에 순서대로 방문해야합니다.
3. N이 주어졌을 때 r행 c열을 몇번째로 방문하였는지 구해야합니다.
4. 재귀, 분할정복으로 문제풀이 진행

이번 문제의 경우 Z 모양으로 2차원배열을 탐색하여 입력받은 r행 c열을 몇번 째로 방문하는지 구하는 문제입니다.

문제는 재귀와 분할정복을 이용하여 풀이를 진행하였고, 헷갈리지 않게 사분면을 가지고 설명하도록 하겠습니다.

사분면을 이용하는 이유는 분할정복을 하기 위해서입니다. 사분면으로 계속 분할 하다보면 마지막 4개만 남을 것이고 그중에 하나의 사분면이 입력받은 행과 열이 맞다면 문제의 해답을 찾을 수 있기 때문입니다.

 

예를들어 여기서 N이 3이고, 4행 7열의 값을 찾아보겠습니다.

N이 3인 경우 총 8행8열로 64개 입니다.

여기서 사분면으로 나누면 4행4열까지 1사분면 4행 8열까지 2사분면 8행 4열까지 3사분면 8행 8행까지 4사분면으로 생각할 수 있습니다.

4행7열은 1사분면에 존재하지 않기 때문에 찾아보지 않고 2사분면으로 바로 넘어간 후에 2사분면 안에 4행 7열이 존재한다는 사실을 알았습니다.

다시 2사분면은 4사분면으로 나누어줍니다. 

여기서 4행7열은 4사분면에 존재하기 때문에 4사분면을 다시 나누어줍니다.

마지막으로 4행7열은 3사분면에 있는 사실을 알고 30을 출력합니다.

 

이런식으로 계속 분할하여 입력받은 행과 열을 찾아주면 되는 문제입니다.

위의 그림을 보며 아래 코드를 보면 이해 하실 수 있습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int r = int.Parse(input[1]);
    int c = int.Parse(input[2]);
 
    int result = 0;
 
    Search(0, 0, (int)Math.Pow(2, N));
 
    void Search(int x, int y, int n)
    {
        // 해당 값을 찾았으면 몇번째로 방문했는지 출력
        if (x == c && y == r)
        {
            writer.WriteLine(result);
            return;
        }
 
        // 해당 4분면 안에 포함되어 있다면
        if (c < x + n && c >= x && r < y + n && r >= y)
        {
            Search(x, y, n / 2); // 1분면
            Search(x + n / 2, y, n / 2); // 2분면
            Search(x, y + n / 2, n / 2); // 3분면
            Search(x + n / 2, y + n / 2, n / 2); // 4분면
        }
        else
        {
            // 포함되지 않으면 다른 면으로 이동
            result += n * n;
        }
    }
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.