https://www.acmicpc.net/problem/1074
1074번: Z
한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r,
www.acmicpc.net
c언어로 재귀함수를 이용하여 문제를 풀었다.
https://ggsmainstay0297.tistory.com/m/2
p1074
https://www.acmicpc.net/problem/1074 1. 재귀 알고리즘 사용 2. 3. 코드 구조화: (1) 사분면 계산 클래스 (2) 재귀 알고리즘 구현 클래스 (3) 메인 클래스 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19..
ggsmainstay0297.tistory.com
여기 블로그를 참고하여 작성하였다.
이 그림을 예시로 들자
먼저 노란색부분은 총 검토한 횟수가 2*2^2(n-1)이 될것이다. 왜냐하면 먼저 노란색 한 부분은 2^2(n-1)이 되기 때문이다. 또한 이 식에 2를 곱해줬는데 그 이유는 노란색 칸이 2개, 즉 해당하는 사분면이 2개이기 때문이다.
여기서 n=3이므로 이를 예로 하면 노란색 부분은 16=2^2(3-1)이 된다. 그리고 노란색 칸은 2개이기 때문에 2를 곱해주면 노란색 전체의 검토한 횟수가 32이가 될것이다.
초록색부분 또한 노란색 부분처럼 검토하면 된다.
보라색 부분은 n=1일 때로 유추할 수 있다. 이때가 종료조건인데 왜냐하면 다음의 그림과 같은 상황이기 때문이다.
칸안에서 보라색 칸을 하나씩 살펴보면 된다.
유의 해야 될것은 n의 값이 달라질때 마다 r과 c도 달라진다.
visit함수가 재귀함수이다.
가로 크기의 1/2을 half라고 설정해주었고 이 half의 값은 2^(n-1)이다.
n==1이면 위에서의 사진과 같다. 이것이 종료 조건이다.
이때의 코드를 if문으로 r과 c를 각각 비교해서 리턴값을 설정해 주었는데 딱히 그럴필요가 없었다. 왜냐하면 후술할 quadrant함수가 이 역할도 해주기 때문이다.
n==1이 아니면 위에서 설명했던 것 처럼 사분면의 크기를(quadrant(half, r, c)*pow(2, 2 * (n - 1))) 구한다. 그리고 n-1에서도 이와 같이 행해야 되기 때문에 visit함수를 호출하고 이 두개를 더하면 된다.
앞에서 n이 변함에 따라 r과 c의 값이 바뀐다고 하였다.
r의 값과 c의 값이 바뀌는 규칙이 있는데 half보다 작다면 값이 그대로 유지가 될것이다. 그러나 half보다 크다면 값이 r-half(c-half)로 바뀔것이다.
예를들어, n=3이고 r=7, c=7이라고 하자(빨간점)
n=2가 되면 초록색 부분을 살펴봐야 된다. 이때 r의 값은 3=7-half(2^(3-1)), c의 값도 3=7-half(2^(3-1))으로 바뀔것이다.
n=1이 되면 보라색 부분을 살펴봐야 된다. 이때 r의 값은 1=3-half(2^(2-1)), c의 값도 1=3-half(2^(2-1))이 된다.
quadrant함수는 사분면을 판단하는 함수이다.
파라미터로 전달받은 half와 r, c를 각각 비교하여 사분면을 판단한다.
r과 c가 1사분면에 있다면 사분면의 크기를 더해줄 필요가 없으므로 0을 리턴한다.
-처음에 짰던 코드-
size를 2^n이라고 놓았는데 이것이 가로의 크기(세로의 크기)이다.
만약 가로의 크기가 2이면 가장 작을때이니깐 이때 하나씩 판단을 하면서 비교한다.
그리고 사분면에 하나하나씩 접근하도록 코드를 짰다.
그러나 이렇게 풀면 재귀함수 구조가 복잡해 질것 같고 좀더 간결하게 코드를 짜고 싶어서 다시 짰다.
