C++/ BFS 활용문제 - 섬나라 아일랜드, 미로의 최단거리 통로

 

Queue를 이용해 최단 거리를 사용하는 문제 => BFS

 

그것 까진 알겠는데, 내부 논리를 짜 놓고 외부 탐색 루프를 짜는 게 자꾸 헷갈린다 ,,ㅠ ㅠ

안에서 부터 짜야하는지 큰 골격을 생각하고 내부를 짜야하는지 모르겠다

아마 문제를 많이 풀어봐야 개선되겠지!?!?

 

섬나라 아일랜드

(출처 - 인프런 강의) 

1로 뭉쳐진게 섬

 

1이 연결되어 있는 뭉텅이를 찾아 총 섬의 개수를 세는 문제이다

DFS, BFS 모두 가능하지만 인프런 강의에서는 bfs를 사용했기 때문에 bfs 먼저 보려고 한다.

내가 짠 코드 

 

자료구조

- 격자 판은 vector<vector<int> > 형을 사용했음.

- 좌표는 pair<int, int> 사용

- queue<pair<int,int>> 로 저장함

 

루프

이중 while 문을 이용함. 격자를 매번 처음부터 끝까지 탐색하게 하고 싶지 않아서 좌표 (point) 변수에 제약을 크게 걸고, 내부에 1와 0을 구분해 1이면 queue에 저장, 아니면 좌표를 단순히 다음으로 옮기는 식으로 코드 작성함

 

문제점

 

point 좌표를 따로 설정을 해봤자, queue 가 들어가는 논리에서 어차피 다시 설정해서 queue에 push 해야하기 때문에 복잡해지기만함.

하여간 segmentation fault 나왔음,,ㅠ 이렇게 하려면 방문한 지점을 따로 저장해야 하는데 그럴 필요 없이 매번 새로 도는 코드 (선생님이 짠 코드)가 나은 것 같다

 

 

Not my code

 

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;
int n, map[30][30], cnt=0;
int dx[8]={0,1,1,1,0,-1,-1,-1};
int dy[8]={-1,-1,-1,1,1,0,-1};
struct Loc{
    int x;
    int y;
    Loc(int a, int b){
        x=a;
        y=b;
    }
};
queue<Loc> Q;
int main(){
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&map[i][j]);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(map[i][j]==1){
                Q.push(Loc(i,j));
                map[i][j]=0;
                while(!Q.empty()){
                    Loc tmp = Q.front();
                    Q.pop();
                    for(int i=0;i<8;i++){
                        if(map[tmp.x + dx[i]][tmp.y+dy[i]] == 1){
                            Q.push(Loc(tmp.x+dx[i], tmp.y+dy[i]));
                            map[tmp.x+dx[i]][tmp.y+dy[i]]] = 0;
                        }
                    }
                }
                cnt++;
            }
        }
        printf("%d",cnt);
        return 0;
    }
}

 

pair 대신 Loc struct를 새로 만들어서 좌표 지정, 탐색도 시계 방향으로 모두 탐색

 

미로의 최단 거리 탐색

 

너비 우선 탐색의 가장 기본적인 문제. level을 따라 노드를 탐색하기 때문에 최단경로 탐색은 bfs

0일 때는 길이 있는 것이고 1일 때는 길이 없는 것이다

 

 

진짜 내가 문제 풀면서 제일 조심해야 할 점은

문제를 제대로 이해하지 않고 뛰어드는 것인 것 같다

계속 문제를 이상하게 읽고 맘대로 짜버리니까 시간 낭비가 많이 된다 ㅠㅠ

제대로 이해하고 풀자 !!!

 

그래도 이 문제는 쉽게 풀었다

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int n;
int map[30][30], dis[30][30];
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};

struct LoC{
    int x;
    int y;
    LoC(int a, int b){
        x=a;
        y=b;
    }
};

queue<LoC> Q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&map[i][j]);
        }
    }

    Q.push(LoC(1,1));
    map[1][1]=1;

    while(!Q.empty()){
        LoC tmp = Q.front();
        Q.pop();
        for(int i=0;i<4;i++){
            int xx=tmp.x+dx[i];
            int yy=tmp.y+dy[i];
            if(map[xx][yy] == 0 && xx>=1 && xx<=7 && yy>=1 && yy<=7){
                Q.push(LoC(xx,yy));
                map[xx][yy]=1;
                dis[xx][yy] = dis[tmp.x][tmp.y] + 1;
            }
        }
    }