BFS (4) 썸네일형 리스트형 [백준 1260번] DFS와 BFS - Python 백준 1260문제 문제 파악 그래프에 대한 정보가 주어진다. 해당 그래프의 노드(정점)들에는 숫자가 주어져있으며 DFS와 BFS 각각의 방법으로 탐색했을때 지나가는 순서를 구해야한다. 이 문제를 푸는 과정은 크게 다음과 같이 단계를 나누어서 접근했다. 입력 데이터들을 사용하기 쉽게 변환하여 그래프 배열을 구한다. DFS와 BFS를 수행하는 함수를 만든다. 그래프와 시작 노드 그리고 DFS, BFS 함수 등을 이용하여 방문하는 노드 순서 출력 2번의 경우 이전에 DFS, BFS 알고리즘에서 다루었다. 그래서 나머지 부분은 큰 어려움이 없었다. 무엇을 찾아야하는 조건이 없었고 전역 탐색만 수행하면 되었기에 쉬운 문제라고 생각했다. 하지만 이 문제의 관건은 1번이었다. 주어진 입력 데이터들을 2차원 배열로 정.. [알고리즘] DFS 및 BFS - Python 그래프를 탐색하는 방법으로 DFS와 BFS가 많이 언급된다. 실제로 코딩 테스트 문제로 자주 출제되며, 경험상 해당 문제들을 이러한 알고리즘 기법 도구들을 사용하지 않고 다가가면 아주 어려웠다. 그러나 DFS와 BFS라는 도구를 익힌다면 엄청 어려워 보이던 최단 거리 구하기 같은 문제들에 자신감이 생기게 된다. 알기 전과 후의 차이가 극명한 알고리즘으로 이번 기회에 정리를 해두면 도움이 될 것 같다. (엘리스 sw트랙 스터디 활동으로 [이것이 취업을 위한 코딩 테스트]다의 DFS 및 BFS 강의를 기반으로 작성한다.) 깊이 우선 탐색 (DFS : Depth First Search) 우선 DFS라고 불리는 깊이 우선 탐색을 먼저 살펴본다. 트리나 그래프 구조에서 각 노드를 검사하는 방법으로 다음 branc.. [프로그래머스] 타겟 넘버 - 자바스크립트(JavaScript) 프로그래머스의 깊이/너비 우선 탐색(DFS/BFS) 관련 문제들 중 하나인 타겟 넘버를 풀어보았다. 이 문제는 DFS(Depth First Search) 문제일 것이다. 문제 파악 다음과 같이 사용할 수 있는 숫자가 담긴 배열과 타겟 넘버가 매개변수로 주어지며, 이 숫자들을 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 구해야하는 문제이다. -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 최단 거리를 구하는 문제가 아닌, 모든 경우의 수를 따져보아야하는 문제였다. 위의 예시에서는 배열의 길이가 5이므로 총 경우의 수는 32가지이다. 즉 주어진 배열의 길이가 N개라면 2 ** N(2의 N승)의 경우의 수가 존재하는 .. [프로그래머스] 게임 맵 최단거리 - 자바스크립트(JavaScript) 문제 파악 게임 맵 최단거리 문제는 깊이/너비 우선 탐색(DFS/BFS) 카테고리에 해당되며 최단거리를 구해야 하므로 BFS(Breadth First Search) 방식으로 해결 할 수 있었다. 우선 BFS란 너비 우선 탐색으로 대표적인 그래프 탐색 방법 중 하나이다. 정점의 자식들을 먼저 탐색하는 방식인 DFS와 다르게 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식이다. 루트(root)와 가까운 노드들 부터 탐색하기 때문에 최단거리를 구할 때 유용하다. 추가적인 특징으로 두 가지의 큐(Queue)를 사용해야하며 DFS 방식보다 메모리가 많이 사용된다. 풀이 과정 1. 현 지점에서 다음 차례에 갈 수 있는 지점을 리턴하는 함수 만들기 다음의 경우를 제외한 좌표값을 반환하도록 만들었다. 이미 지나.. 이전 1 다음
