백트래킹 (5) 썸네일형 리스트형 [백준] 17825번 : 주사위 17825번: 주사위 윷놀이 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 🤔 문제분석 그래프와 점수의 판을 하드코딩으로 그려놓고 파란색 판을 이동하는 조건을 걸어 문제를 해결 할 수 있습니다. 파란색칸은 배열의 길이가 2인경우이고 해당 배열로 이동할경우 그래프에 그려놓은 위치로 이동시킵니다. 이제 위의 조건으로 백트래킹을 이용하여 문제를 해결하면 끝입니다. 💻 코드 import sys input = sys.stdin.readline graph = [[1], [2], [3], [4], [5], [6, 21],.. [백준] 19942번 : 다이어트 https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 해당문제는 모든 경우의 수를 확인하여 최저 값을 찾아내는 완전탐색 + 백트래킹 문제이다. 재귀함수를 통하여 현재 아이템을 포함하는 경우와 포함하지 않은 경우로 나누어 경우의 수를 만들어 비용의 최소값을 초기화 한 후 다음 조합을 계산할때는 이전에 계산했던 최소비용보다 높을 경우 백트래킹(탐색중단) 한다. from copy import deepcopy N = int(input()) mp, mf, .. [백준] 12100번 : 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 해당 문제는 5번의 이동으로 테이블에 있는 값중 최대값을 찾아서 리턴해야하는 문제이다. 순열 조합으로 해당 문제를 해결해야한다. R->R->R->L->R 의 결과와 R->L->R->R->R 의 결과가 다르기 때문이다. 순열의 조건으로 탐색을 시작하고 5번의 탐색의 깊이를 백트래킹 조건으로 놓는다. 즉 모든 경우의 수를 탐색하여 최대값을 리턴 하면 된다. 움직이는 조건은.. [백준] 15649번 : N과 M(1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 다음 문제는 문자열 처리와 백트래킹을 사용하여 문제를 해결 하였습니다. 자기 자신을 포함하고 있거나 문자열의 길이가 만족할 경우 탐색을 멈춘다. 수열을 사전 순서대로 출력해야함으로 깊이우선탐색으로 순차적으로 탐색한다. N , M = map(int, input().split()) def dfs(i, char): char += str(i) if len(char) == M: for i in range.. [백준] 9663번 : N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해당 문제는 브루트포스와 백트래킹으로 문제를 해결 하였습니다. 깊이우선탐색으로 탐색 합니다. 다음열에 Queen을 놓을 수 없을때 BackTracking을 합니다. N = int(input()) count = 0 def isvalied(queens,i,j): if N > i >=0 and N > j >= 0: for queen in queens: k, n = queen if i == k or j == n or a.. 이전 1 다음