본문 바로가기
반응형

DFS5

프로그래머스] C++ 깊이/너비 우선 탐색(DFS/BFS) - 가장 먼 노드(level 3) 해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다. 아래 링크를 통해 풀 수 있습니다. https://programmers.co.kr/learn/courses/30/lessons/49189 1. 문제 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.제한사항노드의 개수 n은 2 이상 20,000 이하입니다.. 2020. 9. 11.
프로그래머스] C++ 깊이/너비 우선 탐색(DFS/BFS) - 단어 변환(level 3) 해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다. 아래 링크를 통해 풀 수 있습니다. https://programmers.co.kr/learn/courses/30/lessons/43163 1. 문제 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> .. 2020. 9. 9.
프로그래머스] C++ 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버(Level 2) 해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다. 아래 링크를 통해 풀 수 있습니다. https://programmers.co.kr/learn/courses/30/lessons/42839 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 soluti.. 2020. 2. 12.
C++] 위상정렬 구현 및 설명 위상정렬은 각 노드들의 간선 개수를 구한 후 간선개수가 가장 적은 요소부터 순회하는 알고리즘입니다. 여기서 간선 개수란 각 노드마다 연결된 개수를 의미합니다. 간선 개수가 적은 요소들을 순회하기 때문에 한번에 원하는 지점까지 못가게 되는 특징이 있습니다. 위상정렬을 이용한 예제들은 주로 '게임 스킬트리, 우선순위에 대한 시간 문제 등...' 다양하게 사용되고 있습니다. 아래 그림을 통해 코드를 구현해 보겠습니다. 여기서 만약 A에서 E로 간다고 가정한다면 A는 B나 C를 거치고 D를 거처서 E로 가거나 혹은 D에서 F를 거처 E로 가게 됩니다. 즉, 노드 간선을 기점으로 모든 노드를 순서대로 거처가는걸 알 수 있습니다. 이 간선을 거처가는것이 하나의 조건이 될 수 있습니다. 아래는 구현 코드 입니다. #.. 2019. 9. 26.
C++] 인접 리스트 구현 인접리스트는 그래프의 한 종류입니다. 인접리스트를 쓰는 가장 큰 이유는 바로 탐색 때문인데, 우리는 인접리스트를 통해 연결된 모든 노드들을 확인할 수 있습니다. 우선 아래의 그림의 그래프를 만들어 보겠습니다. #include #include #include #include using namespace std; enum { A, B, C, D ,E}; void AddGraph(vector * v, int x, int y) { v[x].push_back(y); v[y].push_back(x); } int main(void) { vector g[5]; AddGraph(g, A, B); //A B 연결 AddGraph(g, A, D); //A D 연결 AddGraph(g, B, C); //B C 연결 AddGr.. 2019. 9. 23.
728x90
반응형

티스토리툴바

스킨편집 -> html 편집에서