Week 6 - BFS (숨박꼭질)

<180331>   

Week 6 - BFS

[12851] 숨박꼭질2 (http://boj.kr/12851)

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); 
}

>> 방문체크를 꺼내면서 해야한다. 

>> ans 는 트리에서 레벨수회를 할 때 그 레벨을 세는 역할을 한다고 생각하면 될 것 같다.

[13529] 숨박꼭질3 (http://boj.kr/13549)

#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);
}

>> 정답이 언제든 갱신될 수 있다고 생각했다. 그래서 다 돌리고 난 뒤에 저장되어 있는 값이 정답이라고 생각한 것을 코드로 옮겼다.

>> 다음에 방문할 위치가 현재위치보다 적은 시간에 방문할 수 있다면 다시 방문해야한다.

[13913] 숨박꼭질4 (http://boj.kr/13913)

#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);
}

>> from 배열에 주목하자.

>> from[next] = cur; 은 next 의 이전 위치는 cur 이란 뜻이다.