dfs
-
(java) DFS로 순열 구하기알고리즘/알고리즘 2021. 1. 19. 14:38
DFS(Depth First Search)를 사용해서 순열 만들기 https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 문제를 해결하던 중 [+. -. *] 을 포함한 모든 경우의 수가 필요했다. 그래서 DFS를 이용한 순열을 구현해보았다. 아래 두 필드는 클래스(전역) 필드이다. ArrayList permutedOps = new ArrayList(); // 기호들을 담고 있는 리스트를 만들어야 하기 때문에 이중..
-
1260 DFS와 BFS알고리즘/백준 문제 2020. 5. 14. 18:40
입력값 : 4 5 1 1 2 1 3 1 4 2 4 3 4 - DFS (Depth First Search 깊이우선탐색) 한 방향으로 갈 수 있는 끝까지 탐색을 마치고, 그 다음 방향으로 탐색한다. 길이 여러개일 경우 숫자가 작은 정점부터 탐색하므로 1 -> 2 로 이동. 한 방향으로 탐색을 이어가야 하므로 1 -> 2 -> 4 -> 3 으로 이어진다. 마지막 3 에 도착했을 때, 1 과 4는 이미 방문 한 상태이므로 재귀로 호출된 스레드가 하나하나 모두 종료된다. 모든 정점을 방문 했으므로 프로그램은 종료된다. - BFS (Breath First Search 너비우선탐색) 한 정점에 도착했을 때, 그 정점에서 방문 가능한 정점은 모두 방문한다. 동시에 여러 정점을 방문하는 형태이다. 각 정점의 거리가 1일..