백트래킹14 [백준 15684] 사다리 조작 www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 계속 시간초과와 원인모를 틀렸습니다를 받은 문제.. dfs를 사용해서 구현하는 문제이다. 전체 배열에서 a번째 줄 b와 b+1 사다리가 연결되어 있다면 arr[a][b] =true로 표시한다. 이렇게 표시한 사다리는 i번째 사다리가 i번째에 도달하는지 확인할 때 왼쪽 오른쪽 모두 확인해서 현재 위치를 col +-1해줘야 한다. 추가된 사다리가 4이상이면 -1을 출력하라고 했으므로 cnt>3이면 return;하.. 2020. 12. 17. [백준 15686] 치킨 배달 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 역시 백트래킹을 사용하는 구현문제이다. 백트래킹이 끝나는 기준을 폐업한 치킨 집 수로 잡아서 백트래킹을 진행한다. 처음에 틀렸던 코드는 void BackTracking(int cnt) { if (cnt == sze_c - m) { int distance = getDistance(); result = min(result, distance); return; } for (int i = cnt; .. 2020. 12. 16. [백준 1941] 소문난 칠공주 www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 백트래킹 응용문제이다. 어렵당...ㅠㅠ 7명의 사람이 모두 연결되어 있어야 하고 + 그 중에 'S'가 4개 이상인 경우의 수를 세는 문제이다. 처음에 인접 배열만 이동가능하게 했더니 중복으로 인해 값이 다르게 나왔다. 이 문제의 포인트는 7명의 사람에 대한 모든 경우의 수를 구해서 조건을 만족하는지 확인하는 것이라고 생각한다. 'S'의 경우 dfs를 진행하면서 카운트가 가능하여 따로 함수를 만들지 않아도 되지만 (.. 2020. 12. 11. [백준 16945] 매직 스퀘어로 변경하기 www.acmicpc.net/problem/16945 16945번: 매직 스퀘어로 변경하기 1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때, www.acmicpc.net 처음 봤을 땐 무슨 문젠가 싶지만 3 * 3 칸만 채우면 되므로 브루트포스 - 백트래킹을 사용하면 된다. 사각형을 모든 경우의 수로 채우는 백트래킹을 사용한다. cnt는 3 * 3칸 내에서 칸의 위치를 의미한다. 스퀘어를 1~9로 채우고 난 후 매직스퀘어 조건에 충족한다면 -> 원래 스퀘어와의 차이를 계산 -> 최솟값을 리턴 매직 스퀘어 조건은 가로 세로 대각선의 합이 모두 같은 것.. 2020. 11. 23. 이전 1 2 3 4 다음