백준/그래프 (23) 썸네일형 리스트형 [ICPC] 백준 4803 - 트리 https://www.acmicpc.net/problem/4803 힌트 더보기 주어진 포레스트에 어떤 상태들이 존재할 수 있는지 생각해보자. 풀이 더보기 주어진 포레스트에서 트리의 개수를 찾는 문제이다. 포레스트에 트리와 그래프 둘 다 있을 수 있다는 사실을 유의해야 한다. 이를 간과하지 않으면 예상치 못한 오답을 받게 된다. 각 노드를 돌면서 그래프가 트리인지 확인하여 개수에 따라 올바른 문자열을 출력하면 된다. 노드의 개수가 500 이하이기 때문에 DFS로 사이클 찾기를 하던지 유니온 파인드로 사이클 감지를 하던지 상관없다. 유니온 파인드를 사용할 때는 그래프와 트리가 연결되는 경우를 조심하도록 한다. 전체 코드 - 유니온 파인드로 구현했다. #pragma GCC target("avx,avx2,fma.. 백준 2423 - 전구를 켜라 https://www.acmicpc.net/problem/2423 힌트 더보기 0-1 BFS를 이용하면 가중치가 0과 1로만 이루어진 그래프에서 $O(V + E)$의 시간복잡도로 문제를 해결할 수 있다. 이를 문제에 형태에 맞춰 구현하는 방법을 생각해본다. 만약 문제를 틀린 상태에서 이 게시글을 보고 있는 것이라면 다음 격자로 갈 수 있는 조건을 다시 확인해보도록 하자. 풀이 더보기 문제에 주어진 회로는 최대 8방향으로 탐색할 수 있음을 보여주고 있다. 그리고 회로가 가질 수 있는 위상은 두가지이므로 좌표와 위상을 나타내는 3차원 배열을 생성해서 회로를 돌렸을 때 가중치를 1로 생각해서 0-1 BFS를 수행하면 된다. 다만 회로를 돌린다고 무조건 갈 수 있는 것이 아니다. 다음 두 경우를 보자. 왼쪽의 .. 백준 16928 - 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 다른 노드로 건너뛸 수 있는 간선이 주어진다는 것과 주사위의 점만큼 움직인다는 점을 기억하며 BFS를 수행하면 된다. 전체 코드 더보기 #include using namespace std; using pii = pair; int n, m; unordered_map warp; bool visited[101]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i > go >> to; warp[go] = to; } queue q; q.push({1, 0}); visited[1] = .. [KOI] 백준 2644 - 촌수계산 https://www.acmicpc.net/problem/2644 가족 관계는 트리 형태를 가진다. 따라서 어떤 노드 A에서 B가 연결되어 있다면 그것은 단순 경로이다. 가족의 관계를 그래프로 구성하고 단순히 BFS를 통해 몇번 거쳐갔는지를 세면 된다. 원하는 노드를 찾지 못할 경우 -1을 출력하면 된다. 정답 코드 더보기 #include using namespace std; using pii = pair; int n; int mesh[101][101]; bool visited[101]; int a, b; int e; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> a >> b >> e; vector graph(n + 1); .. 백준 7562 - 나이트의 이동 www.acmicpc.net/problem/7562 각 테스트 케이스마다 bfs를 수행하여 나이트의 최소 이동 횟수를 찾으면 된다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include using namespace std; using ll = long long; int t; int n; int a, b, c, d; int cnt; bool vst[300][300]; int n.. 이전 1 2 3 4 5 다음
