DFS
-
[백준 15651번] N과 M(3) (자바)Algorithm/DFS 2022. 6. 22. 13:06
백준알고리즘 15651번 : N과 M(3) (Solved.ac 난이도 Silver3) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 배열에 값을 담은뒤에 DFS를 이용하여 출력하는 문제이다. 처음에는 출력해야하는 길이값에 따른 배열에 담지않고 바로 출력할수는 없을까.. 라고 생각해서 풀어보았다. 당연하게도 앞에서 여러번 출력되어야하는 숫자들이 한번씩만 출력된다. 요지는 배열의 길이만큼 숫자를 채울때까지 DFS를 돌리고, 다 찬 시점에 바로바..
-
[백준 2644번] 촌수 계산 (Java 풀이)Algorithm/DFS 2022. 5. 23. 21:13
백준알고리즘 2644번 : 촌수 계산 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 촌수를 이동함에 따라 count를 해주어야하는 부분에서 약간 헤멨다. 특이사항이 있다면, 일반적인 dfs와는 달리 한번 check한 LinkedList에 대해서는 다시 확인을 할 필요가 없다는 점이다. 그렇게 해도 되는 이유는 문제에서 '각 사람의 부모는 최대 한 명만 주어진다.'라고 명시되어 있기 때..
-
[백준 11725번] 트리의 부모 찾기 (Java 풀이)Algorithm/DFS 2022. 5. 17. 18:34
백준알고리즘 11725번 : 트리의 부모 찾기 (Solved.ac 난이도 Silver2) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net DFS와 BFS 모두를 이용해서 풀 수 있는 문제였다. LinkedList 타입의 배열을 정의하는 것이 문제 해결에 도움이 많이 되었다. 아직 DFS 및 BFS에 익숙치않아 2가지버전 모두 사용해서 풀어보았다. 실제 소스의 차이는 그리 크지 않다. method를 재귀로 할 것인지, while문을 낀 queue로 할 것인지의 차이정도? 속도 차이도 유의미하게 크지는 않았다...