87. 섬나라 아일랜드 [BFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

풀이 

- queue를 이용한 BFS 문제

- 좌표 => Struct를 사용해 저장한다.

- 상하좌우대각선 => dx, dy 활용해 좌표를 먼저 구한후 배열에 대입한다.

- 섬을 발견하면 일단 큐에 넣고 그 섬의 위치는 0으로 만든다. 

- 그 섬과 연결된 섬을 찾기 위해 상하좌우대각선의 좌표들을 탐색해 큐에 넣는다. 큐에 넣은 후에는 그 위치에 0을 항상 표시해준다.

- 큐가 비면 연결된 하나의 섬을 찾았다는 것이고  카운트가 하나 증가한다.

 

#include <stdio.h>
#include <algorithm>
#include <queue>
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, 0, 1, 1, 1, 0, -1};
//86. 섬나라 아일랜드(BFS)

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++){
                        int xx=tmp.x+dx[i];
                        int yy=tmp.y+dy[i];
                        if(map[xx][yy]==1){
                            Q.push(Loc(xx, yy));
                            map[xx][yy]=0;
                        }
                    }
                }
                cnt++;
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}