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

C++ / 13023 / ABCDE ( 백트래킹 )

https://www.acmicpc.net/problem/13023문제 요약BOJ 알고리즘 캠프에는 총 N명이 참가하고 있습니다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구입니다.오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 합니다.A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성해야합니다. 문제 풀이1. n과 m을 입력받습니다.2. 2차원 배열을 만드는데 입력받는 a와 b가 서로 연결되게 만듭니다.3. dfs 탐색을 합니다. 다만 ABCDE가 되는 수열이 시작하는 숫자가 무조건 0이 아닐수도 있기 때문에 n번까지 탐색합니다.4. 기본적으로 연결..

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

C++/ 26169 / 세 번 이내에 사과를 먹자 ( 백트래킹 )

https://www.acmicpc.net/problem/26169문제 요약5 x 5 크기의 보드가 주어집니다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있습니다. 보드의 격자는 사과가 1개 있는 격자, 장애물이 있는 격자, 빈칸으로 되어 있는 격자로 구분됩니다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호를 나타냅니다. 행 번호는 맨 위 위치가 0이고 아래 방향으로 1씩 증가합니다. 열 번호는 맨 왼쪽 위치가 0이고 오른쪽으로 1씩 증가합니다. 즉, 맨 왼쪽 위 위치가 (0, 0), 맨 아래 오른쪽 위치가 (4, 4)입니다.현재 한 명의 학생이 (r, c) 위치에 있고 한 번의 이동으로 상, 하, 좌, 우 방향 중에서 한가지 방향으로 한 칸 이동할 수 있습니다. 학생이..

• format_list_bulleted BAEKJOON/Backtracking
• · 2024. 12. 31.
• textsms

C++ / 12852 / 1로 만들기 2 ( 백트래킹 )

https://www.acmicpc.net/problem/12852문제 요약정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 입니다.X가 3으로 나누어 떨어지면, 3으로 나눕니다.X가 2로 나누어 떨어지면, 2로 나눕니다.1을 뺍니다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 합니다. 연산을 사용하는 횟수의 최솟값을 출력해야 합니다.문제 풀이1. 정수를 입력받습니다. 2. dfs 탐색을 하는데, 현재  개수가 저장해둔 개수보다 커지면 탐색을 리턴합니다. ( 첫 회차엔 1e9가 저장 되어 있음 )  3. 현재 숫자를 임시 배열에 저장하고 재귀 호출합니다. ( 3으로 나누어 떨어지면 3으로 나눠서, 2로도 나누어 떨어지며 2로 나눠서, 마지막으로 -1 )4. 현재 ..

• format_list_bulleted BAEKJOON/Backtracking
• · 2024. 12. 3.
• textsms

C++ / 15651 / N 과 M ( 3 ) ( 백트래킹 )

https://www.acmicpc.net/problem/15651문제 요약자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성해야합니다. - 1부터 N까지 자연수 중에서 M개를 고른 수열- 같은 수를 여러 번 골라도 됩니다. https://lgj415415.tistory.com/91 C++ / 15649 / N과 M ( 1 ) ( 백트래킹 )https://www.acmicpc.net/problem/15649문제 요약자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이 M인 수열을 모두 구하는 프로그램을 작성해야합니다. - 1부터 N까지 자연수 중에서 중복 없이 M개를lgj415415.tistory.comhttps://lgj415415.tistory...

• format_list_bulleted BAEKJOON/Backtracking
• · 2024. 12. 1.
• textsms

C++ / 15650 / N과 M ( 2 ) ( 백트래킹 )

https://www.acmicpc.net/problem/15650문제 요약자연수 N과  M이 주어졌을 때,  아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성해야합니다. - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열- 고른 수열은 오름차순이어야 합니다. 지난 N과 M에서 이어지는 문제입니다.https://lgj415415.tistory.com/91 C++ / 15649 / N과 M ( 1 ) ( 백트래킹 )https://www.acmicpc.net/problem/15649문제 요약자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이 M인 수열을 모두 구하는 프로그램을 작성해야합니다. - 1부터 N까지 자연수 중에서 중복 없이 M개를lgj415415.tistory...

• format_list_bulleted BAEKJOON/Backtracking
• · 2024. 11. 30.
• textsms