[SWEA] 8queen 문제 파이썬

T = int(input())

def dfs(y):
    global answer
    if y == n:  # 모든 열에 퀸을 놓았으면 카운트 증가
        answer += 1
        return

    for x in range(n):  # 현재 열(y)에 대해 모든 행(x)을 확인
        is_valid = True
        for qx, qy in visit:  # 기존에 놓인 퀸들(qx, qy)와 비교
            if x == qx or abs(x - qx) == abs(y - qy):  # 같은 행 또는 대각선
                is_valid = False
                break
        if is_valid:
            visit.append((x, y))  # 퀸을 현재 위치에 놓는다
            dfs(y + 1)           # 다음 열로 이동
            visit.pop()          # 백트래킹: 퀸 제거

for test_case in range(1, T + 1):
    n = int(input())
    visit = []  # 퀸이 놓인 좌표 저장
    answer = 0

    dfs(0)  # 첫 번째 열부터 시작
    print(f'#{test_case} {answer}')

정답

 

열에 하나씩 넣고, dfs로 다음 열 이동, 행에 대해 ... 하나씩 넣어주고, visit에 있는 행들과 대각선 여부를 비교한다. 

백트래킹은, dfs이후 pop해주는 것이 핵심. visit관리하기

 

같은행이나 대각선에 있으면 is_valid False=> 해당 좌표에 대해 이후 가지치기됨, 차단. 

상단 for문으로 가서, 행이동하여 이어나감.  

 

 

 

 

 

#https://swexpertacademy.com/main/solvingProblem/solvingProblem.do


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.



def dfs(x, y): #좌표차가 difX!=difY, difY!=0, difX!=0이면 놓을 수 잇음. 
    global answer
    global visit
    
    if(y==n):
        if(len(visit)==n):
            print(visit)
            answer+=1
            visit=[]
        return
    for x_, y_ in visit:
        difX=x-x_
        difY=y-y_
        if(difX==0 or difY==0 or abs(difX)==abs(difY)): #놓기 불가한 케이스
            return
            
    visit.append([x, y])
    
    #print(visit)
    for i in range(n):
        dfs(i, y+1) #다음 열에 대하여 
        



for test_case in range(1, T + 1):
    
    n=int(input())
    visit=[] #체스가 놓인 좌표 
    answer=0
    if(n==1):
        print(f'#{test_case} 1')
        continue

    for i in range(n):
        visit=[]
        dfs(i, 0) #열에 대하여 
    
    print(f'#{test_case} {answer}')

오답 

열에 대해 생각하는 건 좋았는데 0~4까지는 되고 이후는 안됨 왜?