본문 바로가기

백트래킹8

[백준/C,C++] 14889번: 스타트와 링크 www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 백준 단계별로 풀어보기 백트래킹 마지막 문제입니다. void dfs(int cnt, int number) { if (cnt == N / 2) { synergy(); return; } for (int i = number; i < N; i++) { M[i] = true; dfs(cnt + 1, i + 1); M[i] = false; } } 파라미터로 cnt와 number를 받아오는데 number를 받아오는 이유는 1, 2번이 팀인 경우.. 2021. 3. 6.
[백준/C,C++] 14888번: 연산자 끼워넣기 www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 연산자의 순서를 바꿔가며 가장 큰 값과 작은 값을 출력해주면 되는 문제입니다. void dfs(int cnt) { if (cnt == n - 1) { calc(); } for (int i = 0; i 0) { operators[i]--; stack.push_back(i); dfs(cnt + 1);.. 2021. 3. 6.
[백준/C,C++] 2580번: 스도쿠 www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백준 단계별로 풀어보기 백트래킹 문제 중에서 가장 어려웠던 문제입니다. 이 문제는 노드를 선택하고 한참 노드를 선택하다 선택할 수 있는 노드가 없다면 다시 계속 선택할 수 있는 노드가 있는 부모 노드로 되돌아가야 합니다. 머리로 계속 로직을 떠올려보았지만 쉽지 않았는데 dfs 함수에 return 한 줄을 넣는 것으로 해결되었습니다. void sudoku(int cnt) { int row, col; if (cnt.. 2021. 3. 6.
[백준/C,C++] 9663번: N-Queen www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 문제로 되게 유명한 N-Queen 문제입니다. 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제인데, 이게 왜 트리 탐색 알고리즘이 필요한가 싶지만, 트리의 형태로 문제를 나타낼 수 있습니다. 입력값으로 4가 들어온 경우 4x4 체스판 위에 퀸 4개를 서로 공격할 수 없게 두어야 합니다. 예를 들어, 위의 그림을 보면 첫 번째 열에서 2번째 칸에 퀸을 놓았다고 치면 직선에 놓인 2열 2번째 칸과 대각선에 놓인 2.. 2021. 3. 6.

티스토리툴바