알고리즘 풀이/DFS(깊이 우선 탐색)
-
BOJ 3967 [매직 스타]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 10. 2. 03:47
BOJ 매직 스타 : https://www.acmicpc.net/problem/3967 안녕하세요. 이번 문제는 백준 온라인 저지의 [매직 스타] 입니다. 순열 조합 문제인데요, 일반적으로 작성하면, 시간 초과를 부를 수 있습니다. 저는 백트레킹을 할 때, 현재 최소로 설정된 문자열보다 사전순으로 뒤에 있는 경우엔 끝까지 가지 않고 바로 back 했습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include #include using namespace std;vector..
-
SWEA 1949 [등산로 조성]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 9. 25. 21:14
SW Expert Academy 등산로 조성 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE //SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다. 가장 긴 등산로를 만들 수 있는 경우를 찾는 문제입니다. 문제를 풀 때, 가장 간과할 수 있는점은 바로, "최대 K만큼 깎을 수 있다" 입니다. 즉, 1~K까지 깎을 수 있습니다. 따라서 다음 위치를 최대 K만큼 깎을 수 있을 때, 최소한으로 깎아준 뒤 DFS를 진행해 줬습니다. (무작정 최대만큼 깎아놓으면, 깎인 좌표에서 다..
-
SWEA 2112 [보호 필름]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 9. 25. 19:25
SW Expert Academy 보호 필름 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE //SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다. 성능검사를 하기 위해 필요한, 최소한의 약품 투입 횟수를 구하는 문제입니다. 해결방법은 다음과 같습니다. 1. 각 투입횟수마다 나올 수 있는 경우를 저장. -> A : 0, B : 1로 둔 뒤, 투입 횟수가 1회 : A : [0], B : [1] 투입 횟수가 2회 : AA : [0 , 0], AB : [0, 1] , BA : [..
-
SWEA 1767 [프로세서 연결하기]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 9. 23. 04:47
SW Expert Academy 프로세서 연결하기 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&categoryId=AV4suNtaXFEDFAUf&categoryType=CODE //SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다. 안녕하세요. 이번 문제는 SW Expert Academy의 [프로세서 연결하기] 입니다. BOJ 15683 [감시] 가 떠오르는 문제네요. 제출하면 계속 1~2개의 테스트케이스가 통과하지 않았습니다. 그 이유는 프로세서를 전원에 연결할 수 없는 경우에만 depth를 늘렸기 때문이었습니다. 프로세서를 가만히 내버려두는 경우..
-
BOJ 14500 [테트로미노]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 9. 22. 08:30
BOJ 테트로미노 : https://www.acmicpc.net/problem/14500 안녕하세요. 이번 문제는 백준 온라인 저지의 [테트로미노] 입니다. 먼저, 위 그림의 핑크색 모양 블록을 제외하면, 나머지 4개 모양의 블록은 모두 DFS를 통해 찾아낼 수 있습니다. 1. 한 점을 잡고, 중복을 어느정도 최소화하기 위해 위로 가지 않도록 DFS를 진행한다. 2. 그러면 한 점에서 갈 수 있는 모든 블록 (ㅗ 모양 블록 제외 //욕 아닙니다 :) )을 탐색할 수 있다. 3. ㅗ 모양 블록은, 해당 점에서 십자가를 그린 뒤, 최소값을 가진 블록을 뺀 값. //함수 이름이 부적절할 수 있습니다. 1234567891011121314151617181920212223242526272829303132333435..
-
BOJ 1941 [소문난 칠공주]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 9. 22. 08:19
BOJ 소문난 칠공주 : https://www.acmicpc.net/problem/1941 안녕하세요. 이번 문제는 백준 온라인 저지의 [소문난 칠공주] 입니다. 먼저 문제를 해결하기 위해선, 1. 7명의 학생을 추출한다. 2. 추출한 7명의 학생들이 서로 인접한지 확인한다. 이것이 핵심이었습니다. 먼저, 7명의 학생을 추출하는 과정은 DFS를 이용해 진행했습니다. 깊이가 7이 될 때까지, 각 인덱스를 증가시킵니다. 7명의 학생 선발이 모두 끝나면, 큐를 이용해 인접한지 체크해 나갑니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#..
-
BOJ 15686 [치킨 배달]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 9. 18. 08:21
BOJ 치킨 배달 : https://www.acmicpc.net/problem/15686 안녕하세요. 이번 문제는 백준 온라인 저지의 [치킨 배달] 입니다. 우선, 저의 문제 해결방법에서 가장 중요한 포인트는 바로, "모든 치킨집 중에서 M개를 뽑기" 입니다. 1. DFS를 통해 치킨집을 M개 고른다. (boolean 배열을 통해 선택할지 안할지 체크) 2. M만큼의 치킨집을 모두 고르면, 각 집에서의 치킨거리를 구한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import java.util.*;public class Main { public static int resu..
-
BOJ 15683 [감시]알고리즘 풀이/DFS(깊이 우선 탐색) 2018. 9. 18. 07:04
BOJ 감시 : https://www.acmicpc.net/problem/15683 안녕하세요. 이번 문제는 백준 온라인 저지의 감시입니다. 이 문제는 제가 2018년 삼성전자DS 인턴을 지원했을때 겪은 문제인데요, 당시 BFS로 접근했다가 큰 낭패를 봤고, 이번엔 DFS로 접근해봤습니다. 인턴시험때 느낀 것은, 당황하더라도 빠르게 침착함을 유지해야 했다는 것입니다. 문제 해결과정은 다음과 같습니다. 1. 카메라의 좌표를 vector에 담는다. 2. 각 depth에 해당하는 카메라를 방향마다 설정한다. 3. 모든 카메라를 세팅하면, 감시영역을 설치하고 사각지대 검사. 4. 다시 감시영역을 회수한 뒤, DFS 진행. 12345678910111213141516171819202122232425262728293..