2차원 배열 백트래킹 문제 푸는데


알고리즘을 이렇게 짰음

1. src라는 판을 i 값에 따라서 0도(기본), 90도, 180도, 270도로 회전함

1.1 회전은 rotating() 함수에서 tmp 배열을 선언한 뒤 원본 배열의 값들을 넣어주고 tmp 배열을 반환함

2. 반환된 tmp배열을 가지고 기울이는 swiping() 함수 실행 (기울이는 동작)

3. 결과가 안 나오면 그 다음 차시 진행


근데 매 회전마다 원본 배열을 매개변수로 넣어주면서 rotating() 함수를 돌리는데, 이전 회전 결과값이 그대로 그 다음 회전으로 들어가더라고

그러니까 원본 배열 자체가 바뀜;;


내가 생각했을 때는 이게 rotating 함수에서 tmp 배열을 선언했고, 그냥 인덱스에 따라서 값만 원본 배열을 참조한거니까 깊은 복사가 된거라고 생각하는데

왜 이게 원본 배열에도 영향을 미침??

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
def swiping(arr):
    h, w = len(arr), len(arr[0])
    ind = 0
    goal = []
    for x in range(h):
        for y in range(w):
            if arr[x][y] == '#':
                ind = y+1
            elif arr[x][y] in ['R', 'B']:
                if 'O' in arr[x][ind:y+1]:
                    goal.append(arr[x][y])
                    arr[x][y] = '.'
                else:
                    arr[x][ind], arr[x][y] = arr[x][y], arr[x][ind]
                    ind += 1
            if goal:
                if 'B' in goal:
                    return 2
                elif 'R' in goal:
                    return 1
 
def rotating(arr, direction):
    global n, m
    if direction == 0:
        return arr
    elif direction == 1:
        tmp = [[0]*n for _ in range(m)]
        for x in range(m):
            for y in range(n):
                tmp[x][y] = arr[y][m-1-x]
    elif direction == 2:
        tmp = [[0]*m for _ in range(n)]
        for x in range(n):
            for y in range(m):
                tmp[x][y] = arr[n-1-x][m-1-y]
    else:
        tmp = [[0]*n for _ in range(m)]
        for x in range(m):
            for y in range(n):
                tmp[x][y] = arr[n-1-y][x]
    return tmp
 
def backtracking(k, baseArr):
    global n, m, res
    if k == 10:
        return
 
    for i in range(4):
        tmpArr = rotating(baseArr, i)
        result = swiping(tmpArr)
        q[k] = i
        if result == 1:
            if res == -1 or res > k+1:
                res = k+1
            return
        elif result == 2:
            return
        else:
            backtracking(k+1, tmpArr)
        q[k] = -1
 
n, m = map(int, input().split())
 
src = [list(input()) for _ in range(n)]
res = -1
q = [-1]*11
 
backtracking(0, src)
 
print(res)
cs