빠르게 성장하는 개발자

N-Queen 문제는 백트랙킹의 대표적인 문제이다.체스의 Queen은 같은 행, 열, 대각선에 대해서 공격할 수 있다.NxN 체스판에서 서로 공격하지 않는 Queen을 몇 개 둘 수 있나? 가 문제이다. 문제는 간단하지만, 풀이과정은 간단하지 않다.처음에는 SWEA에서도 풀이한 문제이기 때문에, 이틀 전에 교수님께서 짜신 코드를 생각하면서 다음과 같이 제출했다.# n-queen def queen(row, k): global cnt if row == k: cnt += 1 return else: for j in range(N): can_position = True # 열 검사 for l in range(0, row+1): if board[l][j] == 1: can_position = False # 대각선 ..

1. 백트래킹(Backtracking)과 DFS의 차이어떤 노드에서 부터 더이상 가능성이 없는 노드를 따라가지 않음으로 시도의 횟수를 줄인다.⇒ 이 과정을 (Prunning, 가치치기) 라고 부른다.백트래킹의 과정상태 공간 트리의 DFS 를 실시한다.각 노드가 유망한지를 점검한다.만일 노드가 유망하지 않으면, 부모 노드로 돌아가서 검색을 계속한다.백준의 N과 M문제가 대표적임 Uploaded by N2T