목록9663 (1)

계단을 오르듯이

[JAVA] 9663. N-Queen

Queen은 대각선, 같은 행, 열에 존재하면 서로 공격할 수 있다. 즉, 서로 공격할 수 없는 퀸의 위치는 모두 각각의 위치에서 행과 열에서 만날 수 없고, 대각선 상으로도 위치하고 있지 않아야 한다. 처음에는 메모리 초과가 발생하였다. 각 위치를 비교해야하므로 이전 위치를 Node 클래스를 만들어서 list 비교를 진행했었다. 하지만 그럴 필요 없이 1차원 배열만으로 해결이 가능하였다. 그 이유는 N이 주어졌을 때 N개의 퀸이 위치해야하므로 모든 행에 대해서는 무조건 퀸이 존재해야 만족한다. 따라서 우리는 열의 위치만을 생각하면 된다. 1차원 배열에서 인덱스는 행을 의미하고 행에 따른 배열의 값이 바로 열의 위치를 알려준다고 생각하면 1차원 배열로 모든 퀸의 위치를 알 수 있게 된다. 퀸의 위치는 처..
알고리즘/백준_JAVA 2022. 2. 2. 14:46
이전 Prev 1 Next 다음