# back tracking
[Python/파이썬] [🥈3] 백준 알고리즘 15652 - N과 M (4)
\-가능한 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 탐색하는 알고리즘\-즉, 해가 될 만한지 사전에 판단하고 그렇지 않으면 되돌아가여(Back-Tracking) 탐색함내 포스팅 : \[Python/파이썬] 백준 알고리즘 15649 - N과 M (1)이전 포
[Python/파이썬] [🥈3] 백준 알고리즘 15649 - N과 M (1)
n,m을 입력받고 num이라는 list를 정의하자자릿수마다 n의 경우의 수만큼 순서대로 고르는 함수 bt()를 만들자for loof으로 i를 1~n만큼 증가시키면서 num에 append()하여 num 길이가 m이면 출력, m보다 작으면 bt()를 재호출하자 ※ m자릿수
(Swift) Programmers 여행경로
코딩테스트 연습 - 여행경로 문제 풀이 아이디어 전형적인 완전 탐색 문제로 보입니다. 하지만 기본에 풀었던 문제들과는 조금씩 다른 부분들이 있습니다. 모든 “공항"을 방문해야 하는 것이 아니라 모든 “티켓"을 사용해야 합니다. 따라서 방문 체크 배열이 아니라 티켓 사용 배열을 만들어서 체크해야 합니다. 알파벳 순으로 가장 앞선 경로를 찾아야 하므로 목...
(Swift) Programmers 소수 찾기
코딩테스트 연습 - 소수 찾기 문제 풀이 아이디어 완전탐색 알고리즘 (dfs)를 통해서 주어진 숫자로 만들 수 있는 모든 경우의 수를 탐색하고 해당 숫자가 소수인지 판정해서 소수이면 숫자를 세면 됩니다. 카드를 일부만 사용할 수도 있으므로 별도의 탈출 조건 없이 dfs를 통해 탐색할 때 마다 모든 숫자가 소수인지 아닌지 판정을 합니다. “011”과 ...
[ BOJ / Python ] 2661번 좋은 수열
오랜만에 백트레킹 문제를 풀어봐야곘다 생각했고, 이 문제를 선택했다. 인자로 들어오는 배열이 좋은 수열인지 확인하는 함수와 백트레킹 함수로 구현했고, 처음에는 백트레킹 함수의 재귀호출 부분에서 조건문을 달지 않고 구현했다. 그러나 이렇게 되면 재귀호출의 가짓수가 너무나
[ BOJ / Python ] 16571번 알파 틱택토
이번 문제는 백트레킹을 통해 해결하였다. 매번 대각선과 가로 세로를 확인하여 이전 차례의 상대의 글자가 일자로 배열해 있는지 확인한다. 그리고 여기서 나오는 결과를 통해 -1, 0, 1 중 하나를 반환하도록 한다. 수가 클 수록 좋은 경우로 배치하였기 때문에 -1, 0
[ BOJ / Python ] 17182번 우주 탐사선
이번 문제는 플로이드-와샬과 백트레킹을 통해 해결하였다. 처음에는 비트마스킹을 활용하여 접근하였다. n이 10까지 가능하므로 2^10인 1024를 비트마스킹 범위로 지정하고, 방문처리를 할 때 visited\[도착 행성]\[출발 행성]으로 지정하였고, 출발 행성을 비트
[ BOJ / Python ] 2026번 소풍
이번 문제는 백트래킹을 통해 해결하였다. 친구들의 관계를 인접 리스트 형태로 저장하고, 백트래킹을 통해 탐색하였다. 문제에서 선택된 모든 친구들이 서로서로 친구관계여야 하기 때문에 백트래킹에서 다음 재귀 호출을 위해 선택하려는 친구가 선택된 친구들과 모두 친구 관계인지
[ BOJ / Python ] 19942번 다이어트
이번 문제는 백트레킹을 통해 해결하였다. 백트레킹을 통해 모든 경우를 구하고, 매 경우마다 기준치를 넘겼는지 확인한다. 만약 넘겼을 경우 정답 변수와 정답 리스트를 더 작은 것으로 갱신시켜주었다. 업로드중..
[ BOJ / Python ] 17136번 색종이 붙이기
이번 문제는 백트레킹을 통해 해결하였다. 조금 복잡한 백트레킹이었는데, 우선 함수의 인자로 y, x를 받는다. 이는 좌표를 의미하고, 좌표를 오른쪽으로 이동시키면서 끝에 도달하면 아래로 한칸 내리는 식으로 진행하였다. 현재 좌표 값이 1이라면 1~5에 해당하는 색종이
[ BOJ / Python ] 16988번 Baaaaaaaaaduk2 (Easy)
이번 문제는 백트레킹과 BFS를 통해 해결하였다. 우선 백트레킹을 통해 흰돌을 놓을 수 있는 모든 경우를 만들고, 이를 이용하여 돌들의 상황을 나타내는 리스트의 임시 리스트를 만들어 모든 경우를 각각 반영하여 BFS를 통해 탐색하도록 하였다. 탐색을 할 때에는 빈칸을
[ BOJ / Python ] 3967번 매직 스타
이번 문제는 백트레킹을 통해 모든 경우를 확인하여 해결하였다. 이 문제를 해결하기 위해 다음과 같은 방식으로 접근하였다.매직스타의 위, 왼쪽부터 아래, 오른쪽으로 이동하며 인덱스를 부여했다. (0 ~ 11)일직선으로 위치하는 인덱스들에 대한 조건 판별을 하는 함수를 작
[ BOJ / Python ] 13023번 ABCDE
이번 문제는 DFS의 백트레킹을 활용하여 연결된 친구들을 모두 탐색하며, 그 연결의 길이가 5일 경우에 1을 출력하도록 하였다. 이렇게 접근하기 위해서 데이터를 인접 리스트로 저장하였고, dfs함수 내에서는 각각의 인접 리스트를 순회하며 방문처리되지 않은 친구에게 방문
[ BOJ / Python ] 17141번 연구소 2
이번 문제는 백트레킹을 통해 바이러스가 존재하는 모든 경우를 구하고, 각 경우마다 BFS를 통해 바이러스가 퍼지는 시간을 갱신하는 방식으로 구현하였다. 각 칸의 바이러스가 퍼지는 시간이 짧은 것이 우선순위가 높으므로 항상 더 작은 값으로 갱신해주었다. 다익스트라 방식과
[ BOJ / Python ] 17135번 캐슬 디펜스
이번 문제는 함수로 따로 모듈화하여 해결하였다. 궁수가 최대한 많은 적을 죽이기 위해서는 성과 같은 y축에 있어야 한다(적을 최대한 오래 봐야 하기 때문). get_arrows함수는 3명의 궁수의 x축의 모든 경우를 구해야하기 때문에 이를 백트레킹을 통해 구현하였다.