Manta Ray's

문제 : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 : ① DFS를 이용핸 도달할 수 있는 모든 경로를 탐색. ② 탐색 한 경로의 최소값을 출력 2021.09.19 - [알고리즘/알고리즘] - 깊이 우선 탐색 Depth-first search 깊이 우선 탐색 Depth-first search 깊이 우선 탐색 시작 노드와 직접 연관된 하위 노드 끝까지 모두 ..

깊이 우선 탐색 시작 노드와 직접 연관된 하위 노드 끝까지 모두 탐색한 후 다음 하위 노드를 탐색하는 방법 일단 경로 하나의 모든 층을 탐색한 후 그 다음 경로의 모든 층을 탐색하는 방법 재귀나 스택을 이용해 구현 백트래킹 문제의 해답을 찾지 못했을 때 이전 단계로 돌아가는 것 자식노드에서 값을 찾지 못했을 때 부모노드로 돌아가는 것 슈도코드 DFS(그래프, 시작 정점) { 시작점 방문여부 = true for ( 시작점과 연결된 정점 탐색 ){ if (탐색 정점의 방문여부 == false){ 탐색 정점의 방문여부 = true DFS(그래프, 탐색 정점) //재귀 } } } 시간복잡도 초기화 시간 : Ο(노드갯수) 그래프 탐색 시간 : Ο(노드갯수 + 간선갯수) 정점은 최대 1번 탐색한다. 간선은 최대 2..