목록백준 9663 (1)

시작이 반

[백준] 9663번(python 파이썬)

NxN크기의 체스판이 주어졌을때 퀸을 서로 공격할 수 없게 N개 놓을 수 있다. N개를 놓을 수 있는 경우의 수를 구하는 문제인다. N개를 놓을 수 있다는 것은 한 행에 한개씩 놓을 수 있으면 된다는 소리이다. 퀸은 대각선, 열, 행 이렇게 움직일 수 있다. 즉, 어떤 위치에 퀸이 놓여지면 해당 대각선, 행, 열은 더이상 다른 퀸을 놓을 수 없게 된다. 해당 행에서 열을 순회하면서 놓을수 없는지 판단하며 상태 트리를 만들게 된다. ex) 퀸이 0,0에 있다면 0,0에 퀸을 놓았다면 1,2에 놓을 수 있다. 1,2에 퀸을 놓았는데 행이 2인 곳에 퀸을 놓을 수 있는 자리가 없기 때문에 이전 상태로 올라간다. 1,3에 퀸을 놓으면 2,1에 퀸을 놓을 수 있다. 2,1에 퀸을 놓았는데 행이 3인 곳에 퀸을 놓..
알고리즘/백준 2021. 1. 28. 17:30
이전 Prev 1 Next 다음