Week 4 - BFS

<180324>

Week4 - BFS

[1260] DFS와 BFS

[1012] 유기농 배추

[2178] 미로탐색 (http://boj.kr/2178)

#include <cstdio>
#include <queue>
using namespace std;
 
struct P { int r, c; };
 
int r, c;
int g[102][102];
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
 
int main()
{
    scanf("%d%d", &r, &c);
 
    for(int i=1; i<=r; i++)
        for(int j=1; j<=c; j++)
            scanf("%1d", &g[i][j]);
 
    queue<P> q;  
    q.push((P){1, 1});
 
    while(!q.empty()) {
        int curR = q.front().r;
        int curC = q.front().c; q.pop();
 
        for(int k=0; k<4; k++) {
            int nr = curR + dr[k];
            int nc = curC + dc[k];
            if(g[nr][nc] == 1) {
                q.push((P){nr, nc});
                g[nr][nc] = g[curR][curC]+1;
            }
        }
    }
 
    printf("%d\n", g[r][c]);
}

>> input data 특성상 visited[r][c] 배열을 만들 필요가 없다.

>> 32 라인이 이 문제의 핵심인 것 같다.

>> 21, 31 : 구조체 변수의 경우 저런식으로 캐스팅 해서 바로 넣을 수 있다.

[2644] 촌수계산 (http://boj.kr/2644)

#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
int main()
{
    int n, m;
    int s, e;
    scanf("%d%d%d%d", &n, &s, &e, &m);
 
    vector<int> v[101];
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    queue<int> q;
    q.push(s);
 
    int visited[101]={0};
    visited[s] = 1;
    
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        if(cur == e) break;
 
        for(int i=0; i<v[cur].size(); i++) {
            int next = v[cur][i];
            if(!visited[next]) {
                visited[next] = visited[cur]+1;
                q.push(next);
            }
        }
    }
    printf("%d\n", visited[e]-1);
}
 

>> 알고리즘은 위 문제와 다를게 없음.

- 2년전 풀이..

#include <stdio.h>
 
int n, a, b, m, g[101], ck[101], ans;
 
int getPidx(int idx)
{
    if(idx == g[idx])
        return idx;
 
    return getPidx(g[idx]);
}
 
int main()
{
    int i, x, y, p;
    scanf("%d %d %d %d", &n, &a, &b, &m);
    
    for(i=1; i<=n; i++) 
        g[i] = i;
 
    while(m--) {
        scanf("%d %d", &x, &y);
        g[y] = x;
    }
    
    x = getPidx(a);
    y = getPidx(b);
 
    if(x != y)
        puts("-1");
    else {
        p = a;
        ck[a] = 1;
        do {
            p = g[p];
            ck[p] = 1;
        } while(p != x);
        
        p = b;
        while(!ck[p]) {
            p = g[p];
        }
        
        while(p != a) {
            ans++;
            a = g[a];
        }
 
        while(p != b) {
            ans++;
            b = g[b];
        }
        printf("%d\n", ans);
    }
 
    return 0;
}

>> 2년전에는 위와 같이 풀었다. 공통 조상이 같으면 촌수를 구할 수 있고, 그렇지 않으면 불가능.

>> ...

[7562] 나이트의 이동 (http://boj.kr/7562)

#include <cstdio>
#include <queue>
using namespace std;
 
struct P { int i, j; };
 
int n;
int di[]={1, 1, 2, 2, -1, -1, -2, -2};
int dj[]={2, -2, 1, -1, 2, -2, 1, -1};
 
bool safe(int i, int j)
{
    return (0 <= i && i < n) && (0 <= j && j < n);
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int curI, curJ;
        int tI, tJ;
        int visited[305][305]={0};
 
        scanf("%d%d%d%d%d", &n, &curI, &curJ, &tI, &tJ);
 
        queue<P> q;
        q.push((P){curI, curJ});
        visited[curI][curJ] = 1;
 
        while(!q.empty()) {
            curI = q.front().i;
            curJ = q.front().j; q.pop();
 
            if(curI == tI && curJ == tJ) break;
 
            for(int k=0; k<8; k++) {
                int ni = curI+di[k];
                int nj = curJ+dj[k];
                if(safe(ni, nj) && !visited[ni][nj]) {
                    q.push((P){ni, nj});
                    visited[ni][nj] = visited[curI][curJ]+1;
                }
            }
        }
        printf("%d\n", visited[tI][tJ]-1);
    }
}
 
 

>> 알고리즘은 미로탐색과 일치한다. 탐색 방범만 조금 다를뿐.

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

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
bool safe(int k)
{
    return (0 <= k && k <= 100000);
}
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    queue<int> q;
    q.push(n);
 
    int visited[100001]={0};
    visited[n] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        if(cur == k) break;
       
        int next = cur+1;
        if(safe(next) && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } 
        
        next = cur-1;
        if(safe(next) && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } 
 
        next = cur*2;
        if(safe(next) && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } 
    }
    printf("%d\n", visited[k]-1);
}

>> 동일한 알고리즘이다.