백준/그래프 (24) 썸네일형 리스트형 [USACO] 백준 6002 - Job Hunt https://www.acmicpc.net/problem/6002 힌트 더보기 어떤 도시를 도착하든 D원을 벌어야 나갈 수 있다. 시작 도시도 예외는 아니다. 풀이 더보기 도시를 잇는 도로와 비행기 노선이 제공될 때 어떻게 하면 큰돈을 벌 수 있을까? 비행기를 타는데 소비되는 비용을 음수 가중치라 생각하면 이 문제는 음수 가중치가 있는 그래프에서 최장 경로를 찾는 문제가 된다. C도 220 이하이므로 벨만포드 알고리즘의 사용을 적극 고려해볼 수 있다. 다만 돈을 버는 행위는 간선이 아닌 정점에서 일어난다는 것에 유의해야 한다. 문제의 상황을 벨만포드로 모델링하기 위해 기존 알고리즘의 구현에서 두 가지 조치를 행하면 된다. 1. 시작점의 초기값을 0이 아닌 D로 둔다. D만큼 벌어야 도시를 나갈 수 있기 .. [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); .. 이전 1 2 3 4 5 다음
