"BOJ 13549 숨바꼭질 3"의 두 판 사이의 차이

2023년 12월 23일 (토) 20:33 기준 최신판

1 개요[ | ]

BOJ 13549 숨바꼭질 3

2 같이 보기[ | ]

3 C++[ | ]

#include <bits/stdc++.h>
#include <limits.h>
using namespace std;

int N, K;
int visited[100001];

int bfs() {
    queue<int> q;
    q.push(N);
    visited[N] = 1;
    int x, nx, ncost;
    while(!q.empty()) {
        x = q.front();
        q.pop();
        if(x == K) return visited[x];
        for(int i=0; i<3; i++) {
            if(i==0) {
                nx = x*2;
                ncost = 0;
            } else if(i==1) {
                nx = x+1;
                ncost = 1;
            } else {
                nx = x-1;
                ncost = 1;
            }
            if(nx<0 || nx>100000 || visited[nx]<visited[x]+ncost) continue;
            visited[nx] = visited[x]+ncost;
            q.push(nx);
        }
    }
    return -1;
}

int main() {
    cin >> N >> K;
    fill(visited, visited+100001, INT_MAX);
    cout << bfs()-1;
}

@@ 1번째 줄: / 1번째 줄: @@
 ==개요==
-[[분류: 그래프 이론]]
+{{BOJ|단계=32
-[[분류: 그래프 탐색]]
+|분류1= 그래프 이론
-[[분류: 너비 우선 탐색]]
+|분류2= 그래프 탐색
-[[분류: 데이크스트라]]
+|분류3= 너비 우선 탐색
-[[분류: 최단 경로]]
+|분류4= 데이크스트라
-[[분류: 0-1 너비 우선 탐색]]
+|분류5= 최단 경로
-{{BOJ|단계=32}}
+|분류6= 0-1 너비 우선 탐색
+}}
 ==같이 보기==
 * [[BOJ 1697 숨바꼭질]]
+* [[BOJ 12851 숨바꼭질 2]]
+* [[BOJ 13913 숨바꼭질 4]]
 ==C++==
@@ 17번째 줄: / 20번째 줄: @@
 using namespace std;
-int N, E;
+int N, K;
-int A[1001][1001];
+int visited[100001];
-int visited[1001];
-int v1, v2;
-int MAX = INT_MAX/4;
-int dijkstra(int start, int end) {
+int bfs() {
-	if (start == end) return 0;
+    queue<int> q;
-	for (int i=1; i<=N; i++) {
+    q.push(N);
-		visited[i] = MAX;
+    visited[N] = 1;
-	}
+    int x, nx, ncost;
-	priority_queue<pair<int, int>> pq;
+    while(!q.empty()) {
-	pq.push({ 0, start });
+        x = q.front();
-	visited[start] = 0;
+        q.pop();
-	int x, nx;
+        if(x == K) return visited[x];
-	while (!pq.empty()) {
+        for(int i=0; i<3; i++) {
-		x = pq.top().second;
+            if(i==0) {
-		pq.pop();
+                nx = x*2;
-		for (int nx=1; nx<=N; nx++) {
+                ncost = 0;
-			if (visited[nx] > visited[x] + A[x][nx]) {
+            } else if(i==1) {
-				visited[nx] = visited[x] + A[x][nx];
+                nx = x+1;
-				pq.push({ -visited[nx], nx });
+                ncost = 1;
-			}
+            } else {
-		}
+                nx = x-1;
-	}
+                ncost = 1;
-	return visited[end];
+            }
-}
+            if(nx<0 || nx>100000 || visited[nx]<visited[x]+ncost) continue;
+            visited[nx] = visited[x]+ncost;
-int solve() {
+            q.push(nx);
-     int sum1 = dijkstra(1,v1) + dijkstra(v1,v2) + dijkstra(v2,N);
+        }
-	int sum2 = dijkstra(1,v2) + dijkstra(v2,v1) + dijkstra(v1,N);
+    }
-	int result = min(sum1, sum2);
+     return -1;
-	if (result >= MAX) return -1;
-	return result;
 }
 int main() {
-    ios::sync_with_stdio(0);
+     cin >> N >> K;
-    cin.tie(0);
+    fill(visited, visited+100001, INT_MAX);
-     cin >> N >> E;
+     cout << bfs()-1;
-	for (int i=1; i<=N; i++) {
-		for(int j=1; j<=N; j++) {
-			A[i][j] = MAX;
-		}
-    }
-	int a, b, c;
-	for (int i=0; i<E; i++) {
-		cin >> a >> b >> c;
-		A[a][b] = c;
-		A[b][a] = c;
-	}
-	cin >> v1 >> v2;
-     cout << solve();
 }
 </syntaxhighlight>