백트래킹 2

백준 2580번 - 스도쿠

백준 2580번 - 스도쿠 문제스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다.이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.나머지 빈 칸을 채우는 방식은 다음과 같다.각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. 입력아홉 줄에 걸쳐 한 줄에 9..

아카이빙/BOJ 2017.07.19

백준 9663번 - N Queen

백준 9663번 - N Queen 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력8예제 출력92 접근1행(Row), 1열(Column) 위치에 퀸을 하나 놓는다.다음 행에서 가능한 가장 왼쪽에 퀸을 놓는다.N번째 열에 퀸을 놓지 못한다면 백트래킹마지막 행에서 퀸을 하나 놓으면 하나의 정답을 구한 것이다.모든 경우의 수를 조사하고 가능한 정답의 경우의 수를 구한다. 유망성 (Promising)백트래킹 문제에서 현재의 경우의 수가 가능한 경우의..

아카이빙/BOJ 2017.07.19