VFS
-
[프로그래머스] - 단어 변환Algorithm/프로그래머스 2022. 9. 14. 16:26
문제 [프로그래머스] - 단어 변환 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", targ..
-
[Algorithm] - 위상 정렬Algorithm/Algorithm 2022. 9. 1. 22:26
위상 정렬 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬 싸이클이 존재하는 경우는 발생할 수 없다 일반적으로 방향그래프로 설정이 되어 있기 때문에 Indegree 값이 0인 Node들에서 먼저 시작하면서 VFS 처럼 구현하면 된다. 위상 정렬의 결과가 Node들의 수와 동일해야 한다! ( 동일하지 않는 경우는 Cycle이 발생된 경우 ) 알고리즘 시간 복잡도 : O( V+E ) 1. 처음 방향 그래프들의 Edge를 읽으며, Indegree Table을 설정 2. Indegree가 0인 Node들을 Queue에 넣는다. 3. Queue에 Node들을 꺼내며, 위상 정렬 값 추가 4. 연결된 Node들의 Indgree값을 줄여주고 , 0이면 Queue에 추가 5. 3~4..