목록DFS (40)

1일1알

백준 2638번 치즈 C++

가장자리에는 치즈가 놓이지 않기 때문에 0,0에서 빈 공간을 bfs로 탐색하면서 바깥쪽 공기를 검사한 뒤 치즈가 바깥쪽 공기와 2개의 면 이상 닿아있다면 녹도록 했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; vector board; vector visited; vector isOut; void..
알고리즘 2022. 6. 28. 11:26
백준 1167 트리의 지름 C++

트리의 지름 구하는 법: 1. 임의의 정점x를 정한다. 2. x에서 가장 멀리있는 정점 y를 구한다. 3. y에서 가장 멀리 있는 정점까지의 거리가 트리의 지름이다. 출처 : https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 $x$를 blog.myungwoo.kr 위에서 나온 트리의 지름을 구하는 방법만 알고 있으면 dfs를 이용해서 쉽게 구현할 수 있다. #include #include #include #include #include #include #include #include #include..
알고리즘 2022. 6. 20. 12:18
백준 1967번 트리의 지름 C++

루트부터 시작해서 자식들 중 가장 긴 두 경로를 재귀적으로 탐색하는 방식으로 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int ans = 0; struct Node { vector childs; }; map mp; int GetDiameter(int root) { if (mp.find(root) == mp.end()) return 0; vector dists(mp[root].childs.size()); ..
알고리즘 2022. 6. 17. 11:58
백준 11403번 경로 찾기 C++

dfs로 그래프를 탐색해서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int n; vector graph(101, vector()); vector visited(101, false); void Print() { for (int i = 1; i
알고리즘 2022. 4. 5. 11:52
백준 4963번 섬의 개수 C++

bfs를 이용해서 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dRow[8] = { -1,-1, 0, 1, 1, 1, 0,-1 }; int dCol[8] = { 0, 1, 1, 1, 0,-1,-1,-1 }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while (true) { int w, h; cin >> w >> h; if (w == ..
알고리즘 2022. 3. 26. 12:15
백준 1405번 미친 로봇 C++

백트래킹을 이용해서 마지막 이동까지 마쳤을 때 이동 경로가 단순한 로봇들이 지나온 길의 확률들만 모두 더하는 방식으로 문제를 해결하였다. 중간에 이미 방문한 곳을 가려고 하면 그곳은 탐색을 하지 않았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dRow[4] = { 0,0,1,-1 }; int dCol[4] = { 1,-1,0,0 }; vector visited(30, vector(30, false)); vector proV(4); int ..
알고리즘 2022. 3. 17. 12:19
이전 Prev 1 2 3 4 5 6 7 Next 다음