[백준][C#] 1074 Z - 실버1

문제 보기

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

1074번: Z

 

 

문제

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

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

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

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

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

 

입력

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

 

 

출력

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

 

 

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2의N승

 

 

CLASS를 따라 풀다보면 처음 만나는 실버1 문제이다.

나도 오늘 처음 실버1 문제를 풀어보았는데,

실버2와 문제 풀이의 난이도는 크게 차이가 나지 않지지만

시간 초과, 메모리 초과가 걸리기 쉬운 느낌이었다.

슬슬 최적화에 더 신경을 써야겠구나 싶더라.

 

 

생각한 풀이 방법은 이렇다.

1. 가상의 2의 N승 x 2의 N승 배열이 있다고 생각하고 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 쪼개고 순서대로 0, 1, 2, 3이라고 인덱스를 부여해보자.

2. 이렇게 4개로 쪼갰을 때, 각 첫 칸의 방문 순서를 보면 (half * half) * index라는 규칙이 있다는 것을 알 수 있다.

3. 첫 칸의 방문 순서와, 첫 칸의 x, y값을 다음 재귀에 넘겨주면 된다.

4. 변의 길이가 1이 된다면 더이상 쪼갤 수 없으니 return한다.

5. x, y 값이 c, r과 동일해진다면 방문 순서의 값을 출력하고 return한다.

// n은 변의 길이. startIndex는 첫 칸의 방문 순서. x, y는 첫 칸의 좌표이다.
void Divide(int n, int startIndex, int x, int y)
{
	// x, y 값이 c, r이 되면 방문 순서를 출력하고 return.
    if (x == c && y == r)
    {
        print.WriteLine(startIndex);
        return;
    }

	// n이 1이면 더 쪼갤 수 없으니 return.
    if (n == 1)
    {
        return;
    }
    else
    {
    	// 쪼개기 위해 n을 반으로 나누어준다.
        int half = n / 2;

        // c, r 값이 있는 분면만 재귀를 돌린다.
        if (c < x + half && r < y + half)
        	// 쪼갠 사분면의 변의 길이, 첫 칸의 방문 순서, x, y 값을 넣어주는 것.
        	Divide(half, startIndex + (half * half) * 0, x, y);
        else if (c >= x + half && r < y + half)
        	Divide(half, startIndex + (half * half) * 1, x + half, y);
        else if (c < x + half && r >= y + half)
        	Divide(half, startIndex + (half * half) * 2, x, y + half);
        else if (c >= x + half && r >= y + half)
        	Divide(half, startIndex + (half * half) * 3, x + half, y + half);
    }
}

원래 코드에서는 c, r값이 있는 부분 뿐만 아니라 전부 쪼개서 재귀를 돌렸다.

그러다보니 메모리초과 시간초과가 나서 c, r값이 있는 분면만 재귀를 돌리는 코드로 수정하였다.

 

전체 코드

static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            string[] inputs = reader.ReadLine().Split();
            int N = int.Parse(inputs[0]);
            int r = int.Parse(inputs[1]);
            int c = int.Parse(inputs[2]);

            int n = (int)Math.Pow(2, N);

            Divide(n, 0, 0, 0);

            void Divide(int n, int startIndex, int x, int y)
            {
                if (x == c && y == r)
                {
                    print.WriteLine(startIndex);
                    return;
                }

                if(n == 1)
                {
                    return;
                }
                else
                {
                    int half = n / 2;

                    if (c < x + half && r < y + half)
                        Divide(half, startIndex + (half * half) * 0, x, y);
                    else if (c >= x + half && r < y + half)
                        Divide(half, startIndex + (half * half) * 1, x + half, y);
                    else if (c < x + half && r >= y + half)
                        Divide(half, startIndex + (half * half) * 2, x, y + half);
                    else if (c >= x + half && r >= y + half)
                        Divide(half, startIndex + (half * half) * 3, x + half, y + half);
                }
            }