[백준] 1074 Z

---

(r, c)를 방문한 순서를 구하는 문제이다. 분할 정복 알고리즘으로 해결할 수 있다.

 

브루트 포스를 통해 모든 셀을 방문하여 (r, c)에 대한 순서를 구할 수도 있지만 시간 초과가 발생한다. 따라서 이미 주어지는 r, c의 값을 가지고 최적화를 해야한다.

 

전체 배열의 시작점(가장 왼쪽 구석 지점)을 start_row, start_col이라 가정했을 때, 전체 배열을 4등분하고 각각의 배열 시작점과 끝점을 나타내면 아래와 같다.

 

시작: start_row, start_col    끝: start_row + 세로의 길이 / 2 -1, start_col+ 가로의 길이 / 2 - 1	시작: start_row, start_col+ 가로의 길이 / 2 끝: start_row + 세로의 길이 / 2 -1, start_col+ 가로의 길이
시작: start_row + 세로의 길이 / 2, start_col 끝: start_row + 세로의 길이, start_col+ 가로의 길이 / 2 - 1	시작: start_row + 세로의 길이 / 2, start_col + 가로의 길이 / 2 끝: start_row + 세로의 길이, start_col + 가로의 길이

(r, c)가 해당 하는 지점을 선택하여 재귀 호출하면 문제를 해결할 수 있다.

 

Python