백트래킹

[BOJ/1987번] 알파벳

문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력값 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다. I..

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

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