[BOJ] 2667. 단지번호붙이기(BFS, DFS)

#. Problem

https://www.acmicpc.net/problem/2667

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  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

우선 지도를 그려주자.

지도는 테두리를 0으로 만들어주는게 탐색하기에 편리하다.

먼저, (1,1)부터 탐색을 시작해보자.

(1,1)은 집이 없는 곳이니까 pass

다음 (1,2)는 집이 있는 곳이다 !

(1,2)에 위치한 집에 방문했으니까 우선 0으로 수정해준다.(이미 방문했으니 다시 방문하지 않기 위해)

그러고 queue에 좌표 (1,2)를 저장해준다.

Queue    (1,2) 

다음으로 queue가 빌 때까지 (1,2)와 연결된 집을 탐색해야 하는데,

먼저 queue의 가장 앞에 위치한 좌표를 빼주고(1,2)

Queue   

해당 집으로부터 북동남서에 위치한 좌표를 확인하면서 집는지 탐색해보자.

(1,3), (2,2)에 집이 있는 것을 확인할 수 있다.

집이 있는 좌표는 queue에 넣어주고

Queue    (1,3)  (2,2)

마찬가지로 0으로 수정해준다.

Queue    (1,3)  (2,2)

queue가 아직 채워져 있으니 queue 앞에 있는 좌표를 또 빼보자!

(1, 3) 이네?! (1,3)으로 이동해보자.

해당 집으로부터 북동남서에 위치한 좌표를 확인하면서 집는지 탐색해보자.

(2,3)에 집이 있는 것을 확인할 수 있다.

집이 있는 좌표는 queue에 넣어주고

Queue    (2,2)  (2,3)

마찬가지로 0으로 수정해준다.

Queue    (2,2)  (2,3)

또, (2, 2)로 가보자

Queue    (2,3)

(3,2)좌표에 집이 있다.

Queue    (2,3)  (3,2)

queue에 넣어주고 0으로 수정해주자.

이렇게 반복하다보면 연결된 단지를 구할 수 있다.

섬나라 아일랜드문제와 유사하다.

#. bfs Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; #define x first #define y second   int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 }; int map[30][30]; vector<int> complex;   int main(void) {     int n, i, j, k, cnt;     freopen("input.txt", "rt", stdin);     scanf("%d", &n);       for (i = 1; i <= n; i++)         for (j = 1; j <= n; j++)             scanf("%1d", &map[i][j]);       queue<pair<int, int> > q;     for (i = 1; i <= n; i++) {         for (j = 1; j <= n; j++) {             if (map[i][j]) {                 q.push({ i, j });                 map[i][j] = 0;                 cnt = 0;                   while (!q.empty()) {                     pair<int, int> now = q.front();                     q.pop();                     cnt++;                       for (k = 0; k < 4; k++) {                         int xx = now.x + dx[k];                         int yy = now.y + dy[k];                           if (map[xx][yy]) {                             q.push({ xx, yy });                             map[xx][yy] = 0;                         }                     }                 }                   if(cnt)                     complex.push_back(cnt);             }         }     }       sort(complex.begin(), complex.end());     printf("%ld\n", complex.size());     for (i = 0; i < complex.size(); i++)          printf("%d\n", complex[i]);          return 0; } Colored by Color Scripter

cs

line 24~51) (1,1)부터 (n,n)까지 방문해보자.   

line 25~49) 해당 좌표에 집이 있을 경우

line 27) queue에 넣어주고

line 28) 0으로 수정해준다.(이미 방문했으니 다시 방문하지 않기 위해)

line 29) 카운트를 셀 준비!

line 31~45) queue가 빌 때까지 반복

line 32~33) queue의 제일 앞 원소를 빼내고

line 34) cnt++

line 36~44) 해당 좌표로부터 동서남북에도 집이 있는지 확인해보자.

line 37~38) 탐색할 다음 좌표

line 40~43) 다음 좌표에 집이 있을 경우 queue에 넣어주고 마찬가지로 0으로 수정

line 47) 집이 한 채 이상일 경우 단지수 정보를 저장하는 vector에 넣어준다.

line 53) 최종적으로 단지수 정보를 저장한 vector를 오름차순 정렬해주고 

line 54) 총 단지수(vector 크기) 출력

line 55~56) 각 단지내 집의 수 출력

#. dfs Code

/*
reference : subinium
*/
 
#include <cstdio>
#include <algorithm>
using namespace std;
#define x first
#define y second
 
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
int map[30][30], ck[30][30], cnt[625], th = 1;
 
void dfs(int x, int y)
{
    int i;
    ck[x][y] = th;
    for (i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (map[xx][yy] && !ck[xx][yy]) 
            dfs(xx, yy);
    }
}
 
int main(void)
{
    int n, i, j;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%1d", &map[i][j]);
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (map[i][j] && !ck[i][j]) {
                dfs(i, j);
                th++;
            }
 
        }
    }
 
    for (i = 1; i <= n; i++) 
        for (j = 1; j <= n; j++) 
            cnt[ck[i][j]]++;
 
    printf("%d\n", th-1);
    sort(cnt+1, cnt+th);
    for (i = 1; i < th; i++)
        printf("%d\n", cnt[i]);
 
    return 0;
}

* 나는 이런 맵 탐색 문제에서 bfs로 푸는게 더 편한것 같다..

line 33~41) (1,1)부터 (n,n)좌표까지 탐색

line 35~38) 해당 좌표에 집이 있고 방문한 기록이 없다면

line 36) dfs()에 좌표를 넘겨주기

line 10~21) dfs()

line 13) 해당 좌표의 ck[]에 단지 번호를 저장

line 14~20) 해당 좌표로부터 북동남서에 위치한 좌표에도 집이 있는지 확인

line 18~19) 주변 좌표에도 집이 있고 방문한 적이 없는 좌표라면

line 19) dfs()에 주변 좌표 넘겨주기

line 37) 단지 탐색이 끝나면 단지 번호를 늘려주기

line 42~44) 각 단지별로 단지내에 집이 몇 채 있는지 연산