Henzee's Archive

문제 링크     문제 분석N×N 크기의 체스판 위에 N개의 퀸이 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제이다.백트래킹을 사용해서 각 행의 퀸이 놓인 열의 위치를 저장하고 다음 행으로 갈 수 있는지 판단하며 문제를 해결할 수 있다.   문제 풀이 ✔️ 한 행씩 퀸을 배치하며 유효한 위치인지 체크하고, 유효하면 다음 행으로 넘어간다. 퀸을 한 행씩 배치첫 번째 행부터 시작해서 퀸을 놓아본다.퀸을 놓을 수 있는 경우에만 다음 행으로 이동한다.N행까지 퀸을 배치했다면 경우의 수를 +1 한다.유효성 검사같은 열과 대각선 방향에 퀸이 존재하는지 확인한다.|행 차이| == |열 차이| 이면 같은 대각선에 위치한다는 것을 의미한다.    최종 제출 코드 #include using namespace std..

문제 링크     문제 분석R×C 크기의 보드에 알파벳이 하나씩 적혀있다. (1, 1)부터 시작해서 같은 알파벳을 지나지 않고, 최대로 지날 수 있는 칸 수를 구하는 문제이다.말은 상하좌우로 인접한 네 칸 중 한 칸으로 이동할 수 있고 (1, 1)도 칸 수에 포함한다.   문제 풀이 DFS를 사용해서 사방탐색을 하고, 지나온 알파벳을 저장해 중복 방문하지 않도록 체크한다.중요한 점은 한 방향으로 탐색을 마친 뒤 지나온 알파벳을 초기화해줘야 한다는 점이다. 만약, 예제 입력 2에서H → F → D 순서로 탐색을 했다면, 탐색을 마친 뒤 방문한 알파벳들의 방문 처리를 초기화해줘야 한다. 그래야 새로운 루트인 H → A → J → G 의 방문 처리를 제대로 할 수 있다.  자세한 구현 사항은 코드를 통해 알아..

백준 15686번 - 치킨 배달 (골드 5)     문제 분석최대 M개의 치킨집을 골라 도시의 치킨 거리의 최소값을 구하는 문제이다.조합을 이용해서 전체 치킨집 개수 중에 M개의 치킨집을 골라야 한다. (최대 M개라고 했으니, M개를 고르는 것이 치킨 거리의 최소값을 구할 선택지가 많아지므로)고른 치킨집을 가지고 각 집마다 치킨 거리(집과 치킨집의 최소 거리)를 구해준다.치킨 거리의 핪의 최소값을 구해준다. (= 도시의 치킨 거리의 최소값) 백트래킹 (Backtracking)M개의 치킨집을 고를 때 사용하는 조합은 백트래킹을 이용해서 구현할 수 있다.백트래킹은 현재 상태에서 가능한 모든 선택지를 탐색하는 알고리즘이다.재귀 함수로 구현할 수 있으며 탐색을 들어가서 원하는 값이 아닌 경우 이전 탐색지로 돌아..