[Inflearn] 섬나라 아일랜드(BFS)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 각 섬은 1로 표시, 0은 바다

     - 상하좌우와 대각선으로 연결

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

DFS랑 BFS로 모두 해결할 수 있는 문제인데

BFS로 풀어보자!

기본적으로 (1,1) 좌표부터 (n, n) 까지 탐색한다.

섬(1)을 발견하면  그 섬을 방문했으므로 0으로 수정하고, 

상하좌우, 대각선에 연결된 섬이 있나 확인한다. 

연결된 섬이 있으면 Queue 에 push 하고 연결된 섬으로부터 또 다른 연결된 섬이 있나 확인한다.

이렇게 연결된 섬을 계속 확인하면서 다음 섬으로 이동할 때는 0으로 수정해주고

Queue 가 비워질 때까지 반복하고, Queue 가 비워지면 섬 하나가 모두 탐색된 것이다.

이건 그림으로 설명하기엔 너무 복잡하므로.. 

코드 설명으로 바로 해야겠다.

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define x first
#define y second
 
int cnt = 0;
int dx[9] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int dy[9] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int map[22][22];
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i, j, k;
    pair<int, int> popTmp;
    queue<pair<int, int> > q;
 
    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({ i, j });
                map[i][j] = 0;
            }
            else
                continue;
 
            while (!q.empty())
            {
                popTmp = q.front();
                q.pop();
 
                for (k = 0; k < 9; k++)
                {
                    int tx = popTmp.x + dx[k];
                    int ty = popTmp.y + dy[k];
 
                    if (map[tx][ty] == 1)
                    {
                        q.push({ tx, ty });
                        map[tx][ty] = 0;
                    }
                }
            }
 
            cnt++;
        }
    }
 
    printf("%d\n", cnt);
 
    return 0;
}

line 10~11) 이동해 볼 상하좌우, 대각선 좌표를 미리 저장

line 29~60) BFS의 핵심 코드이다. (1,1) 부터 (n,n) 까지 탐색.

line 33~37) 탐색한 좌표가 섬일 경우, Queue 에 push 해주고 해당 좌표는 방문했으므로 0으로 수정

line 38~39) 탐색한 좌표가 바다(0)일 경우는 더이상 동작할 필요가 없으므로 continue;

line 41~57) 연결된 섬들을 탐색하기 위해 Queue 가 빌 때까지 반복

line 43~44) 연결된 섬들을 하나씩 빼면서, 더 연결된 섬이 있나 확인

line 46~56) 상하좌우, 대각선을 탐색해보면서 더 연결된 섬이 있나 확인.

               더 연결된 섬이 있다면 Queue 에 넣어주고 0으로 수정

    (이미 방문한 좌표는 0으로 수정되었으므로 다시 방문하지 않음)

line 59) Queue 가 다 비어있다면 연결된 섬의 탐색이 끝난것이므로 cnt++

#. Other code

#include<stdio.h>
#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};
 
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;
}

DFS 문제에서는 많이 헤맸었는데 

그래도 BFS 문제는 강사님과 문제 해결 방법이 같아서 너무 감격스러웠다.. 

그래도 조금씩 늘고 있는게 보여서 너무 기쁘다 캬캬

더 열심히 해보쟈아~~!

강사님은 pair 자료형 대신 구조체를 사용하셨고,

내가 좀 참고해야 할 부분은 

line 30. 에서 섬일 경우의 동작을 하나로 묶었는데, 나는 디버깅하면서 하다 보니까

굳이 continue 를 사용하였다. 뭐 상관없긴 하지만ㅋㅋㅋ

강사님의 깔끔한 코드를 본받아야지.. 

#. Result

  - Input --------------------------------------------------------

7

1 1 0 0 0 1 0 

0 1 1 0 1 1 0 

0 1 0 0 0 0 0 

0 0 0 1 0 1 1 

1 1 0 1 1 0 0 

1 0 0 0 1 0 0 

1 0 1 0 1 0 0

------------------------------------------------------------------

  - Output --------------------------------------------------------

5

------------------------------------------------------------------