Algorithm/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로 할 것인지의 차이정도? 속도 차이도 유의미하게 크지는 않았다...
-
[백준 1012번] 유기농 배추 (Java 풀이)Algorithm/DFS 2022. 3. 26. 16:21
백준알고리즘 1012번 : 유기농 배추 (Solved.ac 난이도 Silver2) ↑클릭시 문제 link로 이동합니다.😊 DFS의 기본이 되는 문제라고 볼수있겠다. 나는 기본이 없었던 것 같다.(...) 3년전에 풀었던 문제도 이렇게 헤매다보니 역시 알고리즘은 꾸준히 해야한다는 것을 깨닫는다. 복잡한 DFS 문제와는 다르게 1, 즉 배추가 있는 곳만 잘 찾아서 근처 상하좌우로 탐색을 하면서 '추가로 인접한 배추가 있는가?' 라는 것만 check하여 0으로 바꿔주면 된다. 따라서 탐색이 몇번 이루어졌는지 알필요가 없다는 점에서 깊이 우선 탐색 문제 중 간단한 편에 속한다고 생각한다. 풀이 과정 1. 배추밭을 2차원 배열로 정의하고, 배추가 있는 곳마다 값을 1로 대입한다. 2. 2중 for문으로 배추가 있..