https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹 문제다. 9 x 9로 배열이 크지 않아 백트래킹을 이용했다. 배열에서 0인 칸을 따로 저장해두고 해당 칸을 순차적으로 채워나가는 방식이다. 채울 때의 조건은 같은 행이나 열에 그 숫자가 없고 3 x 3 칸 안에 그 숫자가 없어야 한다. 스도쿠가 다 채워지면 해당 스도쿠 답을 출력한다. #include #include using namespace std; bool complete; int ..
백트래킹
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 브루트포스와 백트래킹 문제다. 1. m개의 치킨 집 선택 2. 각 집에서 치킨 집의 가장 가까운 거리를 구하고 모든 집에서의 거리 합 구하기 3. 모든 조합의 경우에서 2번을 수행해 최소 거리 구하기 로 방법을 생각했다. m개의 치킨 집을 선택하기 위해서는 재귀 백트래킹을 사용했다. 집과 치킨 집의 거리를 구하기 위해서는 좌표 계산을 했다. DFS와 백트래킹 공부 중인 나머지..
