본문 바로가기
반응형

dfs26

백준 2573번 빙산 - C++ 풀이 1. 빙산 덩어리의 개수는 그래프의 연결 요소 개수이므로 DFS/BFS 호출 횟수와 같다. 2. 모든 빙산 칸에 대해 주변의 0의 개수만큼 높이를 줄여주고, 빙산덩어리의 개수를 센다. 3. 빙산 덩어리의 개수가 2개 이상이 될 때까지 2번 과정을 반복한다. 1. 빙산덩어리의 개수는 그래프의 연결 요소 개수이므로 DFS/BFS 호출 횟수와 같다. 서로 연결되어 있는 빙산칸은 하나의 덩어리이므로, 빙산 덩어리의 개수는 그래프의 연결 요소 개수와 같다. 따라서 빙산 덩어리 개수는 모든 빙산칸을 방문하기까지 호출한 DFS/BFS의 횟수와 같다. 2. 모든 빙산 칸에 대해 주변의 0의 개수만큼 높이를 줄여주고, 빙산 덩어리의 개수를 센다. 빙산이 녹는 과정을 시뮬레이션 해준 뒤, 빙산 덩어리의 개수를 세준다. 이.. 2022. 6. 2.
백준 2468번 안전 영역 - C++(cpp) 풀이 1. 물에 잠기지 않은 지역을 정점으로 생각하고 상하좌우로 인접한 정점을 간선으로 이었을 때, 그래프의 연결 요소가 곧 안전 영역이다. 2. 그래프의 연결 요소 개수는 모든 정점을 방문하기 위해 호출해야 하는 DFS/BFS 횟수와 같다. 3. 가능한 모든 높이에 대해 해당 높이만큼 물이 찼을 때 안전영역의 개수를 센 뒤, 최댓값을 찾는다. 1. 물에 잠기지 않은 지역을 정점으로 생각하고 상하좌우로 인접한 정점을 간선으로 이었을 때, 그래프의 연결 요소가 곧 안전 영역이다. 주어진 상황을 그래프로 바꾸어 생각할 수 있다. 물에 잠기지 않은 지역을 정점으로 생각하고, 상하좌우로 인접한 정점들을 간선으로 이었을 때, 안전 영역은 그래프의 연결 요소와 같다. 2. 그래프의 연결 요소 개수는 모든 정점을 방문하기.. 2022. 5. 8.
백준 4963번 섬의 개수 - C++(cpp) 풀이 1. 땅인 칸을 정점으로 생각하고, 가로, 세로, 대각선으로 이어져있는 땅들을 간선으로 잇는다. 2. 하나의 섬은 그래프의 연결 요소 하나와 대응된다. 3. DFS/BFS를 사용해 그래프의 연결 요소 개수를 센다. 1. 땅인 칸을 정점으로 생각하고, 가로, 세로, 대각선으로 이어져있는 땅들을 간선으로 잇는다. 주어진 상황을 그래프로 바꾸어 생각할 수 있다. 땅인 칸을 정점으로, 이어져있는 땅들을 간선으로 이으면 그래프가 된다. 2. 하나의 섬은 그래프의 연결 요소 하나와 대응된다. 이제 섬은 그래프의 연결 요소와 같다는 것을 알 수 있다. 3. DFS/BFS를 사용해 그래프의 연결 요소 개수를 센다. 따라서 섬의 개수는 곧 그래프의 연결 요소 개수와 같다. 한 번의 DFS/BFS로 하나의 연결 요소에 속.. 2022. 5. 3.
백준 2644번 촌수계산 - C++(cpp) 풀이 1. 각 사람을 정점, 부모 자식 관계를 간선으로 연결하면 결과는 트리를 이룬다. 2. 촌수는 트리에서 두 정점 간의 거리와 같다. 3. DFS나 BFS로 두 정점간의 거리를 구한다. 1. 각 사람을 정점, 부모 자식 관계를 간선으로 연결하면 결과는 트리를 이룬다. 부모 자식 관계에서 사이클이 생성되는 것은 불가능하다. 따라서 결과는 항상 트리 구조이다. 2. 촌수는 트리에서 두 정점 간의 거리와 같다. 촌수는 트리에서 두 정점 사이의 간선의 개수, 즉 두 정점간의 거리를 뜻한다. 3. DFS나 BFS로 두 정점간의 거리를 구한다. DFS나 BFS로 두 정점 간의 거리를 구하면 된다. 이때 트리에서 두 정점이 연결되어있지 않으면 촌수를 계산할 수 없는 경우이다. #include #include using.. 2022. 5. 2.
백준 1103번 게임 - C++(cpp) 풀이 1. 그래프에 사이클이 존재하면 무한번 움직일 수 있다. DFS를 이용해 사이클을 확인한다. 2. dp(r, c) = (r, c) 위치에서 시작했을 때 최대 이동 횟수라고 하면, dp(r, c) = 1 + max(dp(상), dp(하), dp(좌), dp(우)) 1. 그래프에 사이클이 존재하면 무한번 움직일 수 있다. DFS를 이용해 사이클을 확인한다. 무한번 움직일 수 있는 경우는, 그래프에 사이클이 존재하는 경우이다. DFS를 사용해서 사이클 존재여부를 체크한 후, 존재한다면 바로 -1을 출력해준다. 2. dp(r, c) = (r, c) 위치에서 시작했을 때 최대 이동 횟수라고 하면, dp(r, c) = 1 + max(dp(상), dp(하), dp(좌), dp(우)) dp(r, c) = (r,c) 위.. 2022. 3. 30.
반응형

티스토리툴바