Game Develop

[Algorithm] Baekjoon 1074번 : Z 본문

Algorithm/Baekjoon

[Algorithm] Baekjoon 1074번 : Z

MaxLevel 2022. 10. 25. 23:14

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

 

1074번: Z

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

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int targetY;
int targetX;
int answer = -1;
bool isBreak = false;
int dir[4][2= { {0,0}, {0,1}, {1,0}, {1,1} };
 
 
 
void drawZ(int leftTopY, int leftTopX, int size)
{
    if (isBreak) return;
 
    if (size == 2)
    {
        for (int i = 0; i < 4; i++)
        {
            int nextY = leftTopY + dir[i][0];
            int nextX = leftTopX + dir[i][1];
            answer++;
 
            if (nextY == targetY && nextX == targetX)
            {
                isBreak = true;
                return;
            }
        }
    }
    else // 4분할.
    {
        drawZ(leftTopY, leftTopX, size/2); // 좌상단
        drawZ(leftTopY, leftTopX + size/2size/2); // 우상단
        drawZ(leftTopY + size/2, leftTopX, size/2); // 좌하단
        drawZ(leftTopY + size/2, leftTopX + size/2size/2); // 우하단
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int r = 0;
    int c = 0;
 
    cin >> n >> targetY >> targetX;
 
    drawZ(00, pow(2,n));
    cout << answer;
    
    return 0;
}
cs

 

이건 처음 풀이하고 제출했던 코드. 결과는 시간초과다.

위 코드는 각 영역을 나누고 하나씩 값을 기록하면서, 타겟 r,c에서 count값을 리턴하는 코드이기 때문이다.

N은 최대 15이기때문에 2^15 => 32768이고, 최대 값기록횟수는 32768 * 32768이 된다. 

즉 10억회 이상을 카운팅한다. 시간제한은 0.5초이기 때문에 이렇게 풀라는 의도의 문제가 아닌것이다.

그래서 다음과같이 코드를 수정해서 해결했다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
int targetY;
int targetX;
int answer = -1;
bool isBreak = false;
int dir[4][2= { {0,0}, {0,1}, {1,0}, {1,1} };
 
void drawZ(int leftTopY, int leftTopX, int sizeint leftTopNum)
{
    if (isBreak) return;
 
    if (size == 2// 더이상 못쪼갤때
    {
        for (int i = 0; i < 4; i++)
        {
            int nextY = leftTopY + dir[i][0];
            int nextX = leftTopX + dir[i][1];
            leftTopNum += 1;
 
            if (nextY == targetY && nextX == targetX)
            {
                answer = leftTopNum - 1;
                isBreak = true;
                return;
            }
        }
    }
    else // 4분할.
    {
        int nextSize = size / 2;
 
        // 좌상단 체크.
        if (targetY >= leftTopY && targetY < leftTopY + nextSize &&
            targetX >= leftTopX && targetX < leftTopX + nextSize)
        {
            drawZ(leftTopY, leftTopX, size / 2, leftTopNum); 
        }
 
        // 우상단 체크.
        if (targetY >= leftTopY && targetY < leftTopY + nextSize &&
            targetX >= leftTopX + nextSize && targetX < leftTopX + size)
        {
            drawZ(leftTopY, leftTopX + size / 2size / 2, leftTopNum + pow(nextSize, 2)); 
        }
 
        // 좌하단 체크.
        if (targetY >= leftTopY + nextSize && targetY < leftTopY + size &&
            targetX >= leftTopX && targetX < leftTopX + nextSize)
        {
            drawZ(leftTopY + size / 2, leftTopX, size / 2, leftTopNum + pow(nextSize, 2* 2); 
        }
        
        // 우하단 체크
        if (targetY >= leftTopY + nextSize && targetY < leftTopY + size &&
            targetX >= leftTopX + nextSize && targetX < leftTopX + size)
        {
            drawZ(leftTopY + size / 2, leftTopX + size / 2size / 2, leftTopNum + pow(nextSize, 2* 3); 
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int r = 0;
    int c = 0;
 
    cin >> n >> targetY >> targetX;
 
    drawZ(00, pow(2,n),0);
 
    cout << answer;
    
    return 0;
}
cs

 

이 코드는 타겟이 되는 R과 C를 포함하는 최소범위의 영역(2 * 2)을 찾을 때까지 영역을 쪼개며 조금씩 범위를 좁혀나간다.

이게 가능한 이유는 각 영역의 leftTop(좌상단)의 카운트숫자를 알 수 있기 때문이다.

위 코드에서 drawZ의 마지막 매개변수가 좌상단의 카운트숫자이다. 

처음영역의 크기가 2^3이라면 각 4개 영역의 좌상단카운팅값은 Z방향 순서대로 아래와 같다.

leftTopNum 

leftTopNum + pow(nextSize, 2)

leftTopNum + pow(nextSize, 2* 2

leftTopNum + pow(nextSize, 2* 3

 

결국 뎁스가 증가하다보면 타겟 R과 C가 포함된 2*2의 영역까지 도달하게 되며, 해당 영역에서의 leftTop부터 Z자를 카운팅하다 타겟R,C에서 카운팅값을 출력해주면 된다.