본문 바로가기
반응형

dfs26

프로그래머스 빛의 경로 사이클 - C++ 풀이 1. 기존의 노드를 도착한 빛의 방향에 따라 4개의 노드로 쪼갠다. 2. 그리드의 문자열 값에 따라 방향 간선을 추가한다. 3. DFS로 모든 노드를 방문하면서 사이클을 모두 찾아낸다. 1. 기존의 노드를 도착한 빛의 방향에 따라 4개의 노드로 쪼갠다. 노드에 빛이 도달할 때 4가지 경우가 있다. 북쪽에서 도달한 경우, 동쪽에서 도달한 경우, 남쪽에서 도달한경우, 서쪽에서 도달한 경우. 이 4가지 경우는 모두 다른 경우이기 때문에 기존 노드들을 모두 4개로 쪼개서 도달한 빛의 방향에 따라 다른 노드로 보자. 2. 그리드의 문자열 값에 따라 방향 간선을 추가한다. 이제 그리드의 문자열 값에 따라 방향 간선을 추가하여 그래프를 완성한다. L, R인 경우 방향을 전환해주고, 해당 방향으로 1만큼 떨어진 노드로.. 2023. 9. 16.
백준 3584번 가장 가까운 공통 조상 - C++ 풀이 1. O(N)의 LCA 알고리즘을 사용하여 구한다. 1. O(N)의 LCA 알고리즘을 사용하여 구한다. 단순한 LCA(Lowest Common Ancestor) 구하기 문제이다. N = 10,000 밖에 되지 않기 때문에 희소 테이블을 사용하지 않는 O(N)의 LCA로도 충분하다. #include #include #include using namespace std; const int MAX = 10'001; int N; int depth[MAX], parent[MAX]; vector children[MAX]; void dfs(int curr) { for (auto child: children[curr]) { depth[child] = depth[curr] + 1; dfs(child); } } int NC.. 2023. 8. 21.
백준 20303번 할로윈의 양아치 - C++ 풀이 1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다. 2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치) 3. 배낭의 최대 용량이 K-1인 냅색 문제로 바꾸어 푼다. 1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다. 친구끼리는 모두 한꺼번에 사탕을 빼앗기게 되므로 개인이 아니라 친구집합 단위로만 의미가 있다. 각 아이를 노드, 친구관계를 간선으로 생각하면 친구집합은 그래프의 각 연결요소가 된다. 이제 DFS/BFS 혹은 유니온파인드를 사용하여 모든 연결요소를 구해주자. 이때 각 연결요소에 속하는 노드(아이)의 개수와 각 노드에 걸린 사탕의 총합도 구한다. 2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치) 이.. 2023. 7. 14.
백준 2583번 영역 구하기 - C++ 풀이 1. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 잇는다. 2. 완성된 그래프에서 각 연결 요소의 크기와 연결 요소의 개수를 센다. 1. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 잇는다. 유의미한 칸은 직사각형이 없는 칸이다. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 이어 그래프로 만들어준다. 2. 완성된 그래프에서 각 연결 요소의 크기와 연결 요소의 개수를 센다. 이제 각 영역은 연결 요소와 같다. DFS/BFS로 연결 요소의 개수를 세는 동시에 각 연결 요소의 크기도 구해준다. 연결 요소의 개수는 총 DFS/BFS의 호출 횟수이고, 각 연결 요소의 크기는 한 DFS/BFS에서 방문한 노드의 개수와 .. 2022. 9. 19.
백준 17779번 게리맨더링 2 - C++ 풀이 1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 가능한 모든 (x, y, d1, d2) 쌍은 N^4개, 선거구 나누기 시뮬레이션에 O(N^2)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(N^6). 이때 N=20이므로 브루트 포스로 해결할 수 있다. 선거구 나누기 시뮬레이션은 주어진 조건을 잘 구현하면 되고, 경계선으로 둘러싸인 5번 선거구는 DFS로 처리해주었다. #include #include #include using namespace std; const int INF = 987654321; int N; int A[20][20]; int board[20][20]; bool va.. 2022. 9. 18.
반응형

티스토리툴바