분류 전체보기151 [백준] 2644 촌수계산 c++ 문제 링크 https://www.acmicpc.net/problem/2644 KEY 두 노드 사이의 거리를 구하는 문제이므로, 하나의 노드를 기준으로 다른 노드에 도착할 때까지 거리를 증가시킨다. DFS풀이의 경우 재귀함수의 종료조건은 n번 순회를 끝낼 때로 정했다. 구하고자 하는 거리 배열을 0으로 초기화했기 때문에 방문하지 않은 노드의 경우 0이 된다. ◈ DFS풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include #include #include #include #include using namespace std; const .. 2023. 3. 12. [백준] 1389 케빈 베이컨의 6단계 법칙 c++ 문제 링크 https://www.acmicpc.net/problem/1389 KEY N번까지의 노드를 하나씩 출발노드로 지정하면서 (노드, 이동거리)의 큐를 만들어 이동거리의 합을 구하면 된다. 테스트케이스에서 예를 들어보면 다음과 같다. 1번노드에서 출발했을 때 1번(1,0) -> 3번(3,1), 4번(4,1) -> 2번(2,2), 5번(5,2) 따라서 이동거리의 총 합은 0+1+1+2+2 = 6 이 과정을 1~N노드까지 반복수행 Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53.. 2023. 3. 10. [백준] 9663 N-Queen c++ 문제 링크 https://www.acmicpc.net/problem/9663 KEY 퀸을 서로 공격하지 않게 하기 위해서는 퀸을 같은 행, 열, 대각선에 놓지 않아야 한다. (0~마지막 행) 까지 모든 행을 조사하면서 에 맞는 퀸의 위치가 나올 경우 다음 행으로 넘어간다. 만약에 에 맞지 않을 경우 현재 행의 다음 열로 가서 에 부합하는지 확인한다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include #include #include using namespace std; const int MAX = 15; int n; i.. 2023. 3. 9. [백준] 10819 차이를 최대로 c++ 문제 링크 https://www.acmicpc.net/problem/10819 KEY 다른 유형과 별 다를 거 없는 간단한 백트래킹 문제이다. 그리디로 풀 수 있는지 계속 보다가, 마땅히 떠오르지 않아서 완전탐색을 하기로 결정했다. DFS재귀함수를 이용한 방법, 헤더가 지원하는 next_permutation메서드를 사용한 방법 두가지로 풀이했다. next_permutation을 이용한 방법 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #include #include #include using namespace std; int n; vector arr; .. 2023. 3. 9. [백준] 6603 로또 c++ 문제 링크 https://www.acmicpc.net/problem/6603 KEY 일반적인 백트래킹 문제로, 어렵지 않게 풀 수 있다. DFS종료 조건 : 결과 출력 배열(result)의 크기가 6이되면 출력하도록 하면 된다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include #include #include #include using namespace std; const int MAX = 50; int k; int arr[MAX]; vector result; //결과 출력 배열 void dfs(int idx) { i.. 2023. 3. 8. [백준] 1759 암호 만들기 c++ 문제 링크 https://www.acmicpc.net/problem/1759 KEY 일반적인 백트래킹 기법에 조건을 체크하는 것이 추가된 문제이다. DFS로 완전탐색을 하다가 임시배열의 크기가 l이 되면 문제조건을 체크한 후, 출력한다. 사전 순 출력은 DFS탐색 전에 sort로 해결하였다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include #include #include #include #include using namespace std; const int .. 2023. 3. 7. 이전 1 ··· 6 7 8 9 10 11 12 ··· 26 다음
