C++ / 20168 / 골목 대장 호석 - 기능성 ( 백트래킹 )

https://www.acmicpc.net/problem/20168문제 요약소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다. 수금하는 요금은 골목마다 다를 수 있다. 당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다. 호석이의 횡포를 보며 짜증은 나지만, 분신술을 이겨낼 방법이 없어서 돈을 내고 가려고 한다. 하지만 이왕 지나갈 거면, 최소한의 수치심을 받고 싶다. 당신이 ..

• format_list_bulleted BAEKJOON/Backtracking
• · 2025. 6. 10.
• textsms

C++ / 9663 / N-Queen ( 백트래킹 )

https://www.acmicpc.net/problem/9663문제 요약N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제입니다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성해야합니다. 첫째 줄에 N이 주어집니다. (1 ≤ N 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력합니다. 문제 풀이1. n의 개수를 입력받습니다.2. 퀸을 배치한 위치는 1차원 배열로 저장할려 합니다. row[행] = 열 의 형태로그 이유는 2차원 배열을 만들어서 퀸을 배치하고 유효성 검사를 돌리면 시간초과가 나기 때문입니다. 3. 백트래킹을 할것인데 함수는 행 만큼 탐색합니다. 함수안에서는 열이 유효한지 보고 퀸을 배치합니다.행만큼 탐색하..

• format_list_bulleted BAEKJOON/Backtracking
• · 2025. 5. 10.
• textsms

C++ / 2580 / 스도쿠 ( 백트래킹 )

https://www.acmicpc.net/problem/2580문제요약스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있습니다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있습니다. 나머지 빈 칸을 채우는 방식은 다음과 같습니다.각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 합니다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 합니다.위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄..

• format_list_bulleted BAEKJOON/Backtracking
• · 2025. 5. 6.
• textsms

C++ / 1941 / 소문난 칠공주 ( 백트래킹 )

https://www.acmicpc.net/problem/1941문제 요약총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했습니다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했습니다.위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았습니다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 합니다.이름이 이름인 만큼, 7명의 여학생들로 구성되어야 합니다.강한 결속력을 위해, 7명의..

• format_list_bulleted BAEKJOON/Backtracking
• · 2025. 5. 6.
• textsms

C++ / 15686 / 치킨 배달 ( 백트래킹 )

https://www.acmicpc.net/problem/15686문제 요약크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있습니다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미합니다. r과 c는 1부터 시작합니다.이 도시에 사는 사람들은 치킨을 매우 좋아합니다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용합니다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리입니다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있습니다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다.임의의 두 칸 (r1, c1)과 (r2, c2) ..

• format_list_bulleted BAEKJOON/Backtracking
• · 2025. 5. 6.
• textsms

C++ / 1189 / 컴백홈 ( 백트래킹 )

https://www.acmicpc.net/problem/1189문제 요약 한수는 캠프를 마치고 집에 돌아가려 합니다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있습니다. 그리고 한수는 집에 돌아가는 방법이 다양합니다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않습니다. 위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것입니다. T로 표시된 부분은 가지 못하는 부분입니다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것입니다. 문제 풀이1. 지도의 크기 r과  c를 입력 받고 목표 깊이인 c를 입력 받습니다.2. 캐릭터 2차원 벡터로 지도를 그려주고 dfs 탐색을 r-1 * 0 부터 깊이..

• format_list_bulleted BAEKJOON/Backtracking
• · 2025. 1. 11.
• textsms