백트래킹5 BOJ 2239 - 스도쿠 https://www.acmicpc.net/problem/2239 접근법백트래킹 연습용으로 널리 퍼져있는 문제이다.스도쿠 빈칸에 알맞은 번호를 넣으면, 이 번호에 의해 다른 빈칸에 무엇이 들어가는지 결정된다.따라서, 만약 이전 선택이 잘못됐을 경우 돌아가야한다.이를 백트래킹을 이용해 구할 수 있다.보다 구체적으로 설계를 해보자. 1. 빈칸을 돌면서 해당 빈칸에 들어갈 적절한 번호를 선별한다.2. 선별된 번호를 빈칸에 넣고, 재귀적으로 다음 빈칸을 수행한다.3. 만약 빈칸을 모두 매꾸었으면 정답이므로 배열을 출력한다.4. 만약 이후의 빈칸에 적절한 숫자를 넣을 수 없는 경우, 재귀를 종료하여 이전으로 돌아가도록한다. #include #include #include #include #include #incl.. 2024. 8. 27. [시뮬레이션] BOJ 15686 - 치킨 배달 with c++ 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근 방법 1. 폐업하지 않을 치킨집 M개를 선택한다. 2. 해당 폐업하지 않은 치킨집들과 집 사이의 거리들의 합 중 최소값을 구한다. 위 두 가지가 이번 문제의 핵심이다. 폐업하지 않을 치킨집을 고르는 방법 브루트포스밖에 없는 거 같다. 시간을 줄이기위해 백트래킹을 이용하기로 했다. 선택된 M개의 치킨집들과 집과의 거리의 최솟값을 구하기 위해 각 집마다 치킨집들과의 거리를 재어보고 이 중 가.. 2024. 3. 24. BOJ 16987 - 계란으로 계란치기 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 접근 방법 전형적인 백트래킹 문제이다. 순서대로 계란을 집어, 나머지 계란 중 하나를 치면 되는 문제이다. 이 문제의 핵심은 조건문을 어떻게 작성하냐 이다. 내가 틀렸던 예제는 다음과 같다. 3 1 4 8 1 3 1 // 정답: 2 손에 든 계란 외에 모든 계란이 깨진 경우를 체크해주지 않아 답이 1이 나왔다. 이를 bool flag를 통해 쉽게 수정하였다. 코드 #include #.. 2024. 2. 28. [백트래킹 #1] BOJ 15649 - N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근 방법 예전에 풀어봤던 백트래킹이 가물가물해져서 다시 N과 M 시리즈를 풀어보도록 해야겠다. 브루트포스에서 처음부터 시작하는 것 대신, 이전 단계로 복귀하여 행하는 것이다. 코드를 보면 쉽게 이해가 가능하다. https://www.youtube.com/watch?v=Enz2csssTCs 코드 #include #include #include #include #include #include #d.. 2024. 2. 23. [BOJ 1941] 소문난 칠공주 https://www.acmicpc.net/problem/1941 2차원 배열에서 연속된 것을 구한다는 점에서 bfs나 dfs로 구할 수 있을 것같다. 그러나 BFS와 DFS는 뻗어나가는 형식이기 때문에 이런 규칙이 적용되지 않는 경우는 찾기 힘들다. 그래서 이번 문제는 단순히 이차원 배열에서 인접한 것만 찾는 방법 대신 S가 Y보다 큰 조합을 뽑은 다음, 서로 인접해있는지 체크하는 방법을 사용해야한다. 따라서 이중 for문을 통해 이차원 탐색을 하는 대신, 일차원 배열에서 가능성있는지 탐구한다.예를 들어, 1번째 사람이 올 수 있는지 -> 2번째 사람이 올 수 있는지 -> ... -> 25번째 사람이 올 수 있는지이 과정에서 백트래킹을 이용해 여러 조합들을 뽑을 수 있다. 그렇기 때문에 아래와 같이 일.. 2023. 3. 28. 이전 1 다음
