백준 / 1074번 Z / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 1074번 Z

문제 사이트: https://www.acmicpc.net/problem/1074

1074번: Z

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

512 MB

64532

25233

18883

40.059%

문제

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

 

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

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

 

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

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

 

입력

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

출력

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

제한

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

예제 입력 1 복사

2 3 1

예제 출력 1 복사

11

예제 입력 2 복사

3 7 7

예제 출력 2 복사

63

예제 입력 3 복사

1 0 0

예제 출력 3 복사

0

예제 입력 4 복사

4 7 7

예제 출력 4 복사

63

예제 입력 5 복사

10 511 511

예제 출력 5 복사

262143

예제 입력 6 복사

10 512 512

예제 출력 6 복사

786432

출처

• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: hmw9309

알고리즘 분류

• 분할 정복
• 재귀

---

나의 풀이

첫 풀이는 무지성 재귀로 풀었었다.

그런데 시간초과가 엄청 나서.. 조금 질문게시판을 봤다.

 

초점은 분할 정복으로 풀어야했다.

내가 처음에 풀었던 풀이는 모든 곳을 분할하고 해당 위치가 찾아질때 카운트를 반환하는 것이었다.

 

첫풀이 코드

import sys
cnt = 0
def dfs(x, y, N):
    global maps
    global cnt
    if N == 2:
        maps[y][x] = cnt
        maps[y][x+1] = cnt + 1
        maps[y+1][x] = cnt + 2
        maps[y+1][x+1] = cnt + 3
        cnt += 4
        return
    for i in range(x, x + N):
        for j in range(y, y + N):
            dfs(x, y, N // 2)
            dfs(x + N // 2, y, N // 2)
            dfs(x, y + N // 2, N // 2)
            dfs(x + N // 2, y + N // 2, N // 2)
            return



if __name__ == "__main__":
    input = sys.stdin.readline
    n,row,cal = map(int,input().split())
    maps = [[0 for i in range(2**n)] for i in range(2**n)]
    dfs(0,0,2**n)
    print(maps[row][cal])

 

모든 구역을 탐색하면서 재귀호출을 하는 것은 매우 비효율적이다.

따라서 분할할 곳 위주로 (입력값의 타겟 좌표) 분할하며 재귀함수를 실행해야 정답이 나온다.

 

최종 풀이

import sys


def dfs(x, y, N):
    global cnt
    if N == 2:
        for i in range(y,y+2):
            for j in range(x,x+2):
                if i == row and j == cal:
                    print(cnt)
                    exit()
                cnt += 1

    else:
        if x <= cal < x + (N//2)  and y <= row <y + (N//2):
            dfs(x, y, (N // 2)) ## 2 분면
            
        elif x + (N//2) <= cal < x + N  and y <= row <y + (N//2):
            cnt += (N // 2)*(N//2) 
            dfs(x + (N // 2), y, (N // 2)) ## 1분면
            
        elif x <= cal < x + (N//2)  and  y + (N//2) <= row <y + N:
            cnt += (N // 2)*(N//2)*2
            dfs(x, y + (N // 2), (N // 2)) ## 3분면
            
        else:
            cnt += (N // 2)*(N//2)*3
            dfs(x + (N // 2), y + (N // 2), (N // 2)) ## 4분면



if __name__ == "__main__":
    input = sys.stdin.readline
    n,row,cal = map(int,input().split())
    start = 2**n
    cnt = 0
    dfs(0,0,start)

---

※ 알아야 할 것

- 타겟지점의 카운트만 본다는 것은 해당 지점 위주로 분할해야한다는것.