dfs
-
[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)Algorithm 2020. 12. 10. 18:48
깊이 우선 탐색 (DFS, Depth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 깊이 우선 탐색은 간단하게 "한쪽 방향으로 파고들어 탐색하는 방식"으로 미로에서 길을 찾는 것과 같다. 시작점으로부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다. 장점 현 경로상의 노드만 저장하면 되기 때문에 그래프 높이 만큼의 저장공간을 필요로 한다. 즉, 최대저장공간의 수요가 비교적 적다. 목표가 위한 깊이가 깊을 경우 해를 빠르게 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 수 있다. 목표에 이르는 경로가 다수인 경우, 목표에 닿으면 팀색을 끝내기 때문에 최적의 해가 아닐 수 있다. 주로 모든 경로를 탐색해야하거나, 경로 탐색에 조건이 ..
-
[백준 - JAVA] 치킨 배달Algorithm 2020. 12. 9. 17:37
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제를 풀기 시작하자마자 치킨이 먹고 싶어져서, 스터디원들과 30분만에 풀고 다같이 치맥을 먹으러 갔던 문제 ◝(⁰▿⁰)◜ M이 13이하의 수이기 때문에 기초적인 조합을 구현할 수 있다면 풀 수 있다! 풀이 방법 입력을 받으면서, 치킨집과 집의 좌표를 리스트에 각각 저장한다. 치킨집의 리스트로 dfs를 이용한 조합을 구현한다. boolean형 배열을 이용해서 중복 처리를 한다. 치킨집을 M개 골랐을 때 도시의 치킨거리를 구한다. M개의 치킨집..
-
[백준 3109 - JAVA] 빵집Algorithm 2020. 11. 26. 11:40
3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 스터디 과제로 나왔지만, 예전에 풀었던 문제라서 코드를 보면서 복기만 해봤다. dfs를 이용했고, 모든 시작점에서 출발하여 파이프를 연결할 수 있을 경우 계속 진행하는 백트래킹 방식으로 풀었다. 풀이 방법 행의 수 만큼 dfs를 시작한다. 오른쪽위, 오른쪽, 오른쪽 아래로 이동하며 범위안이며 건물이 아닐 경우에만 dfs를 진행한다. 열의 끝에 도달한 경우 ans를 증가시킨다. import java.io.*; import java.util.*; public class Main {..
-
[백준 1937 - JAVA] 욕심쟁이판다Algorithm 2020. 11. 9. 19:28
1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 현재 장소보다 대나무가 많은 지역으로만 이동할 수 있는 판다가 가장 오래 살아남는 기간을 구하는 문제! 단순하게 dfs로 풀었다가 시간초과를 받았다. DP라고해서 고민을 하다가 결국 블로그를 참조했다. 기간을 정해서 DP문제를 집중적으로 푸는 시간을 가져야 할 것 같다... ŏ̥̥̥̥םŏ̥̥̥̥ 풀이 방법 dfs를 통해 끝에 도달했을 때 그곳의 cnt(살아남은 날짜)는 1이 된다. * 더 이상 이동하지 못하기 때문에 그곳에서는 하루만 살 수 있다. 그리..
-
[SWEA 3234 - 준환이의 양팔저울]Algorithm 2020. 11. 9. 18:27
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까? 하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다. DFS를 이용하여 순열을 구현하는 문제다. 나는 올리는 과정에서도 오른쪽이 왼쪽보다 무게가 적어야 한다는 것을 생각하지 못해서 2번정도 fail했다. DP를 이용하지 않고 순열로 구현했기 때문에, StringBuilder와 매개 변수로 전달해주어야 시간 초과가 나지 않는다. 풀이 방법 dfs를 이용해서 순열을 구현한다. 아래 두가지 경..