깊이 우선 탐색2 단어 변환(프로그래머스, Java) 문제링크: https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 | 프로그래머스 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> programmers.co.kr 알고리즘 설명: 한글자씩 바꿔가면서 맞는 단어가 있다면 그 값.. 2019. 10. 24. 깊이 우선 탐색(depth-first search, DFS) 깊이 우선 탐색이란? 트리에서는 왼쪽 노드부터 확인하여 탐색하지 않은 경우에 왼쪽노드에 넘어가고를 반복하여 마지막 깊이까지 들어간 뒤 마지막 노드의 인접 노드들을 전부 탐색한 뒤 백트래킹을 하며 탐색하지 않은 노드들을 탐색한다. 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색. 얻어진 해가 최단 경로가 된다는 보장이 없다. 탐색 지점에서 일직선으로 탐색을 해나가는 느낌 설명 방문을 체크하는 배열 존재 시작 노드를 설정한 뒤 DFS메서드를 불러오고 시작노드의 방문체크를 true로 바꾼다. DFS메서드에서는 설정한 시작노.. 2019. 10. 10. 이전 1 다음
