Sean :: Dev

프로그래머스) 단어 변환 github/DFS%2CBFS 최단거리가 필요한만큼 DFS가 아닌 BFS를 이용하였음. 각 단어를 node로 보고, 한글자 차이로 변환가능하면 인접한 edge로 설정. begin노드 ~ target노드까지의 최단거리 구함. BFS의 기본구조는 일반적인 형태를 따름 (블로그 포스팅 기본코드 참고) 이때, while문에서 distance 카운트시 depth에 상관없이 노드를 방문할때마다 카운팅 되버린다. 따라서 아래와 같이 queue size를 이용한 for문 추가. 참고자료 https://www.acmicpc.net/board/view/12343 큰 차이는 아닌데, v2 코드와 같이 별도의 Node클래스 객체를 생성하거나, node.edge로 distance를 카운팅하거나, isN..

프로그래머스) 타겟 넘버 github/DFS%2CBFS https://lkhlkh23.tistory.com/74 위 링크를 참조해, 그래프를 보면 직관적으로 BFS보단 DFS를 사용해야함을 떠올릴수있다. 종료조건은 depth limit에 도달했을때(배열의 모든원소에 접근했을때)이고, 점화식은 좌측leaf는 +로, 우측leaf는 -로 가정해 계산해낸다. depth limit에선 target값과의 대조를 통해 카운팅(1)할지 / 말지(0) 결정한다.

DFS (Depth First Search) (깊이 우선 탐색) LIFO(Last-In First-Out), Stack 활용 PseudoCode recursive non-recursive 1 non-recursive 2 예제 Input Output 첫 줄에 정점의 개수 N과 간선의 개수 M이 주어집니다. 다음 M줄에 간선의 관계 시작정점 u와 도착정점 v가 주어집니다. 입력에 따른 깊이 우선 탐색 결과를 출력합니다. import java.util.*; public class Test { static boolean edge[][]; static boolean visited[]; static int n; static int m; public static void main(String args[]) { Sca..