반응형 백트래킹2 13023 ABCDE C++ 문제 설명과 풀이 안녕하세요 판타지코딩월드입니다! 오늘은 13023 ABCDE 문제 C++로 문제 설명하고 풀어보겠습니다.1. 문제 설명 0번부터 N-1번까지 친구들 중에 A와 B가 친구이고, B가 C와 친구이고, C와 D가 친구이며 D가 E와 친구인 관계가 존재하는지를 찾는 문제이다. DFS를 활용하기 때문에 간단히 이야기하면 depth가 5까지 갈 수 있는 관계인지를 묻는 것이다. 사람의 수는 N, 친구 관계 수 M을 입력 받아 M개의 줄에 입력한 관계를 배열이나 벡터에 저장하고 DFS를 활용해서 풀면 된다. 2. 문제 풀이 우선 그림으로 그려보면서 어떤 모양인지 이해해야 한다. 그런데 그림을 그렸을 때 오히려 헷갈릴 수 있는 부분이 있다. 아래의 그림을 보자. 0과 1, 1과 2, 2와 3, 3과 4 이렇게 4개.. 2024. 6. 14. 15649 C++ 백트래킹 문제 풀이 오늘은 백트래킹에 대해서 공부하기 위해 가장 위에 있는 문제를 풀어보기로 했다. 백트래킹이라는 이론 자체를 처음 접하기 때문에 가장 쉬운 문제를 풀기로 했다. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 자연수 N과 M이 주어졌을 때 N까지의 숫자 중 M개를 선택해서 만들 수 있는 모든 수열을 나열하는 것이다. 보통 이런 문제는 경우의 수가 몇 개인지를 맞추는 경우면 간단히 다이나믹 프로그래밍을 사용하면 되는데, 이 문제는 직접.. 2024. 2. 6. 이전 1 다음 반응형
