9663 - DFS

hni1124·2022년 5월 2일
0

파이썬이 느려서 대각선 체크까지 구현해야함
같은 대각선에 위치한 y,x가 같은 인덱스를 가지게 하려면 약간의 테크닉이 필요한데,
기울기가 1인 대각선은
used[y+x]로 놓으면 같은 대각선을 공유한다.

기울기가 -1인 대각선은
used2[n-1+y-x]로 놓으면 동일 대각선을 공유하게 된다.

위의 테크닉의 증명을 생각해봤는데
기울기가 1인 대각선은 (0,0)으로부터의 거리가 같다는 공통점이있고
기울기가 -1인 대각선은 (0,3)으로부터의 거리가 같다는 공통점이 있다.

즉 두점 사이의 거리가 인덱스가 되는셈인데
기울기 1의 인덱스가 [y+x]가 되는 이유는 사실 |x-0|+|y-0| 인것.
기울기 -1의 인덱스가 [n-1+y-x]가 되는 이유는 사실 |x-3|+|y-0|이고
여기서 x의 범위는 (0<=x<=3)이므로 (-3<=x-3<=0) 즉 음수이거나 0과 같은 값이므로 부호를 변경해서 3-x가 되기 때문에
위의 인덱스 값이 나온다.

n=int(input())

used1 = [0]*n
used2 = [0]*(2*n-1)
used3 = [0]*(2*n-1)

ssum = [0]
def dfs(cur_x,cnt):
    if cnt == n:
        ssum[0]+=1
        return
    for y in range(n):
        if used1[y] or used2[y+cur_x] or used3[n-1+(y-cur_x)]:
            continue
        used1[y] = 1
        used2[y+cur_x] = 1
        used3[n-1+(y-cur_x)] = 1
        dfs(cur_x+1, cnt+1)
        used1[y] = 0
        used2[y+cur_x] = 0
        used3[n-1+(y-cur_x)] = 0
    return
dfs(0,0)
print(ssum[0])
profile
42Seoul / 알고리즘 공부 중

0개의 댓글