깊이우선탐색

[BOJ/16929번] Two Dots (java) : 깊이우선탐색

문제 Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다. 각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다. 다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다. 점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다. 모든 k개의 점은 서로 다르다. k는 4보다 크거나 같다. 모든 점의 색은 같다. 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다. 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자. Inpu..

[Recursion:Backtracking, 깊이우선 탐색 예제] N-Queen C#

N * N 체스판에 최대한 많은 Queen을 놓고 싶다. 다만, 서로를 공격하지 않게 올려놓고 싶다. 총 몇 가지 경우의 수가 있을까? 🎡 BackTracking 백트래킹의 대표적인 문제로 N-Queen으로 공부해보았다. N-Queen이란 N*N의 체스판에서 서로를 잡아먹지 않는 선에서 최대한 많은 수의 퀸을 두는 문제이다. 한 행에는 같은 선상에는 퀸을 1개만 배치할 수 있으므로 N* N배열에서 최대 개수는 N개가 될 것이다. 이것의 위치를 한정조건 없이 탐색할 경우 엄청나게 많은 조합의 경우가 탄생한다(O(N^N)). 첫 행에 체스말을 배치시켰을 경우 그 다음행에서 배치말이 유효한 칸이 있는지(둘 수 있는 칸인지) 검사 한뒤 없다면 이를 배제하고 그 전 행으로 되돌아간 뒤 , 다음 노드를 검사한다. ..