dfs
-
BOJ) 카드 게임알고리즘/백준 2021. 3. 7. 17:30
카드 게임 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 문제 조건 1. 왼쪽 카드만 통에 버릴 수도 있고 왼쪽과 오른쪽 카드를 둘 다 통에 버릴 수도 있다. (점수 X) 2. 오른쪽 카드에 적힌 수 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다. 3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된..
-
BOJ) 빵집 (3109 번)알고리즘/백준 2021. 2. 23. 01:18
빵집 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다. 이 문제에서 필요한 제약 조건들이다. 그리고 가장 중요한 힌트는 문제의 사진 첨부에 나온다..
-
BOJ) 순열 사이클 (10451번)알고리즘/백준 2021. 2. 15. 14:58
순열 사이클 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 1 ~ N 으로 이루어진 순열을 방향 그래프로 나타냈을 때, 몇 개의 사이클이 존재하는지 구하는 문제다.각 Node에서 다음 Node의 vertex를 가지고 있고, 이 정보가 주어지기 때문에 배열을 활용했다.또한, find-union에서 착안하여 연결되는 지점을 DFS로 찾아가며 문제를 해결했다. 사이클을 형성하는지 확인하는 isCycle 메소드를 만들어 주었다.return 값은..
-
BOJ) ABCDE (13023 번)알고리즘/백준 2021. 2. 12. 15:44
ABCDE 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 설명 N 명이 0 ~ N-1의 번호가 매겨져 있고, 친구 관계가 주어진다. 이 때, 아래와 같이 A, B, C, D, E의 친구 관계가 존재하는지 알아보는 문제다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 친구 관계기 때문에, 단방향 그래프가 아닌 양방향 그래프로 생각해야한다. 또한, 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000) 으로 주어지기 때문에, 최악의 상황이 아닌 경우의 불필요한 loop를 줄이기 위해 List를 선택해서 친구 관계를 저장해주었다. 문제를 처음 봤을..
-
BOJ) 트리 (1068 번)알고리즘/백준 2021. 1. 29. 17:08
트리 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 트리의 정보가 주어지고 특정 노드를 제거할 때, 리프노드가 몇 개 인지 찾는 문제다. 먼저, 트리의 각 노드는 하나의 부모를 가지고 있기 때문에 find-union을 사용해야겠다고 생각했다. 이전 find-union과 다른 점은 이미 부모에 대한 정보가 주어졌기 때문에, find할 때 더 상위 부모로 값을 최신화하지 않았다는 것이다. (최신화를 하게되면 루트 노드로 이어지기 때문에, 특정 노드를 제거했을 때, 자식노드를 제거할 수 없음) 다음으로..
-
BOJ) 트리의 지름 (1167 번)알고리즘/백준 2021. 1. 29. 16:56
트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 이전에 포스팅했던 트리의 지름과 조금 다르게 풀었다. 먼저, 트리기 때문에 어떤 지점에서 시작해도 특정 지점까지 모두 도달할 수 있다는 특징이 있다. 이 말인 즉, 가장 멀리있는 한 특정 지점을 찾을 수 있다는 말이 된다. 위의 조건에 따라, 1에서 가장 먼 vertex를 찾아주었다. 이후, 해당 vertex에서 가장 먼 거리에 있는 지점을 찾으며 최댓값을 갱신해주었다. (만약, 1 -> 찾은 지점이 가장 먼 거리라면, 찾은 지점 -> 1..
-
BOJ) 욕심쟁이 판다(1937, JAVA)알고리즘/백준 2020. 8. 25. 17:54
욕심쟁이 판다 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 풀이 메모이제이션을 활용한 dp문제다. 생각보다 너무 어려웠다. 알고리즘을 조금 쉬었다가 메모이제이션을 적용시켜서 dp를 활용하려니까 감이 잡히지 않았다. 그래서 다른 사람들의 풀이를 보면서 이해했다. 먼저, out of index를 방지해줄 inInArea 메소드와 움직일 수 있는 조건인지 확인하는 canMove 메소드를 만들었다. 이후, dfs 메소드인 findBamboo를 통해 문제의 조건에 따라 움직이며 최대 날을 구했다. 해당 위..