백준/그래프 (22) 썸네일형 리스트형 백준 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.. 백준 20530 - 양분 noj.am/20530 풀이 문제에 언급된 그래프는 다음과 같은 모양을 가질 수 있다. 이들의 공통점은 사이클이 하나 존재한다는 것이다. 따라서 단순 경로의 갯수는 u에서 v로 가다가 두갈래 길을 만나냐 만나지 않느냐로 갈린다. 따라서 오직 2와 1만 답이 될 수 있다. 두갈래로 나뉘는지 아닌지 어떻게 알 수 있을까? 만약 두 노드가 사이클을 경유하지 않으면 1이다. 길이 하나만 있을 수 밖에 없다. 두 노드가 사이클을 경유하는 경우를 살펴보자. 두 노드가 사이클에 속한 경우는 무조건 두 갈래로 탐색할 수 있기 때문에 2이다. 두 노드가 사이클에 속하지 않은 경우도 2다. 탐색하다 사이클을 만나 두갈래로 나눠지기 때문이다. 한 노드만 사이클에 속한 경우는 조금 복잡하다. 다음 그래프를 보자. 다음 그래프.. 이전 1 2 3 4 5 다음
