[백준]1074 Z [Python]

문제

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

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

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

 

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

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

 

 

 

위의 문제에서 우선적으로 생각해봐야하는 부분은 전체 배열의 크기의 패턴을 파악하고 4등분을 내서 1사분면, 2사분면, 3사분면 ,4사분면 형태로 나눠서 생각한다는 점이 key point같다.

 

 

알고리즘은 분할정복과 재귀함수를 사용하며 분할정복을 간단하게 설명하면 다음과 같다.

 

 

분할정복 (divide and conquer) 알고리즘

- 분할정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다.

• Divide : 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때 까지 나눈다.
• Conquer : 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다.
• Combine :  Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다.

 

분할정복 알고리즘을 적용하고 그 사이에 재귀함수를 넣어서 구현하면 전체적인 알고리즘이 돌아갈 것으로 보인다.

 

 

예시를 들어서 설명을 하면

 

N의 값이 2일때는 전체 크기가 2² * 2² 이므로 총 16개의 칸이 만들어진다. 16개의 칸을 4등분하면 4개씩 4칸이되고 각각 1,2,3,4사분면이라고 생각을합니다. 

 

만약 입력값이 2 3 1일경우 찾고자하는 행의 값이 11이므로 이 값은 전체 4등분중에 3사분면에 위치합니다. 각각의 값들을 하나씩 비교해서 +1하면 너무 오래걸리므로 해당 사분면에 찾는 값이 없으면 +4 , +4 이런식으로 값을 넘겨 받습니다.

 

말로 하면 어려우니 코드로 보시면 좀 더 이해하기 쉬우실 거에요.

위의 코드에서 처음 입력값을 N이라고하면 visited함수에 들어가는 값을 (2ᴺ,0,0)으로 받아서 0,0부터 탐색을 시작합니다.

1,2,3,4 사분면의 구분은 r,c의 값을 통해서 (0,0) ~ (1,1) 처럼 구분을 했습니다.

 

res값에 찾고자하는 값이 나오기전까지 재귀함수를 호출해 res에 누적값을 쌓아가면서 만일 찾고자하는 값이 발견되면 print해서 몇번째에 있는지 알려줍니다.