1. 정의
우선 DFS와 BFS의 정의부터 간략하게 다시 알고 가도록 하자.
DFS
깊이 우선 탐색이라는 이름에 맞게 탐색할 노드를 깊이를 우선으로 탐색하는 알고리즘이다.
DFS의 구현은 Stack 또는 재귀적인 특징을 이용해 구현한다.
BFS
너비 우선 탐색은 넓게 바로 아래 하위 노드를 모두 넓게 탐색한 뒤 그 아래의 노드들을 탐색하는 알고리즘이다.
큐를 이용해 탐색을 관리한다.
2. 구분 방법
그렇다면, 실제 코테나 문제를 해결할 때 무엇을 언제 사용해야하나?
우선 그 문제를 분석해봐야한다.
그래프 탐색에서 모든 정점을 방문하는가?
DFS와 BFS 둘 다 가능하다.
경로의 특징을 저장 혹은 조합, 순열을 구해야 하는 문제인가?
고로타면 DFS를 이용하는게 유리하다.
최단 경로, 최단 거리를 구해야 하는 문제인가?
그렇다면 BFS를 이용하는게 유리하다.
예시 문제
그렇다면 예시 문제를 보도록 할까?
내가 뽑은 DFS 예시 문제
[JS] 2Level / 완전탐색 / 요격 시스템
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합
58cjdcns99.tistory.com
[JS] 힌트 2Level / 완전탐색 / 피로도
문제 설명 문제 풀이 방법 나는 이 문제를 보고 dfs로 풀자는 생각을 못하고 순열을 이용해 풀려했다..... dfs로 풀어야지 완전탐색이 가능하다고 생각했지만 dfs 구현을 잘 못해서 결국 힌트를 봤
58cjdcns99.tistory.com
1Level / Summer/Winter Coding(~2018) / 소수 만들기
문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라
58cjdcns99.tistory.com
1Level / 연습문제 / 삼총사
문제 설명 한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고,
58cjdcns99.tistory.com
깊이 우선 탐색 / 3 / 여행경로 (JS) 부족...
문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배
58cjdcns99.tistory.com
깊이-너비 우선 탐색 / 2 / 타겟 넘버 (JS) dfs
문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법
58cjdcns99.tistory.com
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
위의 문제 모두 조합 또는 순열, 경로의 특징을 이용한 문제들이다.
내가 뽑은 BFS 문제들
깊이-너비 우선 탐색 / 3 / 단어 변환 (JS) bfs
문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳
58cjdcns99.tistory.com
[JS] 2Level / 깊이/너비 우선 탐색(DFS/BFS) / 게임 맵 최단거리
문제 풀이 방법 최단 거리를 구하는 문제는 BFS를 이용해 풀어야 한다. 문제는 정석적인 BFS문제이며 큐를 이용해 탐색할 노드를 저장한 뒤 해단 노드의 정보를 이용해 맵의 4방향을 검증하며 방
58cjdcns99.tistory.com
[Nodejs] 2178번 미로 탐색
문제 설명 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주
58cjdcns99.tistory.com
[JS] 2Level / 연습문제 / 무인도 여행
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁
58cjdcns99.tistory.com
위의 문제들에서 볼 수 있듯이 bfs는 최단기간 혹은 최단경로를 구할 때 유용한 알고리즘이다.
'CS' 카테고리의 다른 글
| 자료구조 / 힙 Heap (0) | 2024.03.08 |
|---|---|
| 슬라이딩 윈도우 알고리즘과 투 포인터 알고리즘 (0) | 2023.07.11 |
| 알고리즘 / 해시(Hash) (0) | 2022.06.25 |
| 알고리즘 / 이분 탐색(이진 탐색) (0) | 2022.06.24 |
| 알고리즘 / 동적 계획법 (Dynamic Programming, DP) (0) | 2022.06.23 |
