[프로그래머스] [Level 2] N-Queen(백트래킹)

N-Queen

코딩테스트 연습 - N-Queen

 

 

• 내 풀이 - 오답
  • 테스트 케이스(1~3) 통과 / (3~10) : fail
  • 가장 앞쪽 열의 False로만 실행해보기 때문에 다른 열에서 실행할 경우를 계산하지 못함
    • → 값이 커지면 실패

def bfs(x,y,n,visited):
    for i in range(n):
        if x+i<n:
            if y+i<n:
                visited[x+i][y+i]=True
            if y-i>=0:
                visited[x+i][y-i]=True
        if x-i>=0:
            if y-i>=0:
                visited[x-i][y-i]=True
            if y+i<n:
                visited[x-i][y+i]=True
        visited[i][y]=True
        for j in range(n):
            visited[x][j]=True
            print(visited[i][j], end=' ')
        print()
    print()
    
            
def solution(n):
    answer = 0
    start=0
    
    while start<n:
        count=1
        k_list=[]
        visited=[[False]*n for _ in range(n)]
        bfs(0,start,n,visited)
        for i in range(n):
            for j in range(n):
                if visited[i][j]==False:
                    count+=1
                    bfs(i,j,n,visited)
            
        print("==========")
                    
        if count==n:
            answer+=1
            
        start+=1
            
    return answer

입력값 〉	4
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	
True True True True 
True True False False 
True False True False 
True False False True 

True True True True 
True True True True 
True True True True 
True False True True 

True True True True 
True True True True 
True True True True 
True True True True 

==========
True True True True 
True True True False 
False True False True 
False True False False 

True True True True 
True True True True 
False True True True 
False True False True 

True True True True 
True True True True 
True True True True 
True True False True 

True True True True 
True True True True 
True True True True 
True True True True 

==========
True True True True 
False True True True 
True False True False 
False False True False 

True True True True 
True True True True 
True True True False 
True False True False 

True True True True 
True True True True 
True True True True 
True False True True 

True True True True 
True True True True 
True True True True 
True True True True 

==========
True True True True 
False False True True 
False True False True 
True False False True 

True True True True 
True True True True 
True True False True 
True False True True 

True True True True 
True True True True 
True True True True 
True True True True 

==========

 

 

• 다른 사람 풀이
  • 백트래킹의 가장 기본 문제
  • queen 배열은 각 index가 row / 해당 value가 column
    • ex) [1, 3, 0, 2]라면 [0, 1], [1, 3], [2, 2], [3, 2]에 queen이 배치
    • 📍각 row에는 하나의값만 들어가기 때문에 list로 만들수있다.
  • 하나의 값을 넣고 queen[row] = col
  • 세로로도 겹치면 안되기 때문에 지금까지의 queen배열의 같은 값이 있는지 확인 → 있다면 break로 탈출
  • queen은 대각선으로도 이동이 가능
    • 해당 col의 차이가 row의 차이와 같다면 break로 탈출
  •  break로 탈출하지 않은 경우에만 for-else구문을 활용해서 else 실행
    • 즉 가로는 겹치지않게 만들었고 세로랑 대각선으로 겹치지 않는다면 dfs로 이어서 진행
  • count변수를 넣어서 row가 n 즉, 끝까지 도달했다면 값을 추가하고 종료
    • 아니라면 count=0에서 return이 되어서 0이되게된다.

해설 출처: https://bladejun.tistory.com/134

def dfs(queen, n, row):
    count = 0
    
    if n == row:
        return 1
    
    # 가로로 한번만 진행
    for col in range(n):
        queen[row] = col

        # for-else구문
        for x in range(row):
            # 세로로 겹치면 안됨
            if queen[x] == queen[row]: 
                break
                
            # 대각선으로 겹치면 안됨
            if abs(queen[x]-queen[row]) == (row-x):
                break
        else:
            count += dfs(queen, n, row+1)
            
    return count

def solution(n):
    queen = [0]*n
        
    return dfs(queen, n, 0)