Week 6 - BFS (숨박꼭질)
Tutoring/PS2018. 3. 30. 13:29
<180331>
Week 6 - BFS
[12851] 숨박꼭질2 (http://boj.kr/12851)
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 | c#include <cstdio> #include <queue> using namespace std; const int MAX = 100001; int main() { int n, k; scanf("%d%d", &n, &k); queue<int> q; q.push(n); int visited[MAX]={0}; int ok=0, ans=-1, cnt=0; while(!q.empty()) { int sz = q.size(); ans++; for(int i=0; i<sz; i++) { int cur = q.front(); q.pop(); visited[cur] = 1; if(cur == k) { ok = 1; cnt++; continue; } int next = cur+1; if(next < MAX && !visited[next]) { q.push(next); } next = cur-1; if(0 <= next && !visited[next]) { q.push(next); } next = cur*2; if(next < MAX && !visited[next]) { q.push(next); } } if(ok) break; } printf("%d\n%d\n", ans, cnt); } | cs |
>> 방문체크를 꺼내면서 해야한다.
>> ans 는 트리에서 레벨수회를 할 때 그 레벨을 세는 역할을 한다고 생각하면 될 것 같다.
[13529] 숨박꼭질3 (http://boj.kr/13549)
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 | #include <cstdio> #include <queue> using namespace std; const int MAX = 100001; int main() { int n, k; scanf("%d%d", &n, &k); queue<int> q; q.push(n); int visited[MAX]={0}; visited[n] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); int next = cur+1; if(next < MAX && (!visited[next] || visited[next]>visited[cur]+1)) { q.push(next); visited[next] = visited[cur]+1; } next = cur-1; if(0 <= next && (!visited[next] || visited[next]>visited[cur]+1)) { q.push(next); visited[next] = visited[cur]+1; } next = cur*2; if(next < MAX && (!visited[next] || visited[next]>visited[cur])) { q.push(next); visited[next] = visited[cur]; } } printf("%d\n", visited[k]-1); } | cs |
>> 정답이 언제든 갱신될 수 있다고 생각했다. 그래서 다 돌리고 난 뒤에 저장되어 있는 값이 정답이라고 생각한 것을 코드로 옮겼다.
>> 다음에 방문할 위치가 현재위치보다 적은 시간에 방문할 수 있다면 다시 방문해야한다.
[13913] 숨박꼭질4 (http://boj.kr/13913)
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 | #include <cstdio> #include <queue> using namespace std; const int MAX = 100001; int n, k, from[MAX]; void trace(int cur) { if(cur == n) { printf("%d", cur); return ; } trace(from[cur]); printf(" %d", cur); } int main() { scanf("%d%d", &n, &k); queue<int> q; q.push(n); int visited[MAX]={0}; visited[n] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); int next = cur+1; if(next < MAX && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; from[next] = cur; if(cur == k) break; } next = cur-1; if(0 <= next && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; from[next] = cur; if(cur == k) break; } next = cur*2; if(next < MAX && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; from[next] = cur; if(cur == k) break; } } printf("%d\n", visited[k]-1); trace(k); } | cs |
>> from 배열에 주목하자.
>> from[next] = cur; 은 next 의 이전 위치는 cur 이란 뜻이다.
'Tutoring > PS' 카테고리의 다른 글
Week 1 - DP1 (0) | 2018.06.26 |
---|---|
Week 7 - DFS+BFS (0) | 2018.04.07 |
Week 5 - BFS (0) | 2018.03.24 |
Week 4 - BFS (0) | 2018.03.11 |
Week3 - DFS (0) | 2018.03.07 |