본문 바로가기

백트래킹4

CSES PS - Grid Paths https://cses.fi/problemset/task/1625/ 백트래킹 문제. 아이디어가 안떠올라서 답확인함. 7*7 공간에서 (0,0) ~ (6,0)까지 갈 때 경로가 ?,L,R,U,D 총 48자로 주어진다. 이때 ?대신 아무 방향이나 사용할 수 있을 때 가능한 경로의 수를 모두 구하는 문제. ?가 48개 있을 때 백트래킹 없이 dfs하면 4^48만큼의 시간이 걸리므로 백트래킹이라고 생각하지 않았다. U 9개 D 15개, R 12개, L 12개의 적절한 순열인 줄 알았지만 아니었다. (빨간색은 방문할 수 없는 지점(벽너머거나, 방문했거나), 파란색은 방문할 수 있는 지점(y>0 && y 0 && cy < 6 && !visited[cy - 1][cx] && !visited[cy + 1][cx]) r.. 2019. 12. 22.
CSEC PS - chessboard and Queens https://cses.fi/problemset/list/ 코드가 깔끔한거같아서 올려봄 n-queen문제와 흡사함. 8*8 체스판에 8개의 퀸을 서로 공격할 수 없도록 두는 경우의수를 출력하는 문제. 퀸을 둘 수 없는 곳을 (*)로 표시해서 약간의 변형을 줬다. (풀이는 똑같음) column, diag1, diag2에 대해 이미 사용중인 것이 있다면 가지치기를 하며 재귀 #include #include #include using namespace std; typedef long long ll; bool unable[8][8]; int ans = 0; void go(int k, int col, ll d1, ll d2) { if (k == 8) { ans++; return; } for (int i = 0; .. 2019. 12. 21.
BOJ 9663 - N QUEEN 저번에 마구잡이로 풀어봤지만 백트래킹 연습으로 한 번 더 풀어봤다. 1번줄부터 n번 줄까지 퀸을 배치하는데, x좌표가 중복되지 않게 뽑는 것을 백트래킹 해주면서 대각선에 다른 퀸이 배치돼있는지 검사해줬다. #include #include #include #include using namespace std; int n; bool isValid(vector& picked) { //대각선 검사만 해주면 된다. |(y'-y)| == |(x'-x)| 인경우 return false if (picked.empty()) return true; for (int i = 0; i < picked.size()-1; i++) { // {i, picked[i]} : 퀸의 위치 (y,x) for (int j = i + 1; j <.. 2019. 7. 6.
BOJ 15649 - N과 M (1~12) N개 중 M개를 뽑아 나열하는 경우의 수 시리즈이다. 기본적으로 백트래킹을 이용해서 재귀로 구현함. 9~12같은 경우 중복을 제거해줘야 하는데, 이건 set로 해결하였다. #include #include #include using namespace std; void printPicked(vector& picked) { for (int n : picked) printf("%d ", n + 1); printf("\n"); } int n, m; void pick(vector& picked, vector& isUsed, int k) { if (k == m) { printPicked(picked); return; } for (int next = 0; next < n; next++) { if (!isUsed[nex.. 2019. 7. 6.

티스토리툴바