2606. 바이러스

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





1. 접근


1번이 연결된 그래프의 노드수를 구하는 문제다.


인접리스트로 구성한 맵에 대해 1번 노드를 DFS / BFS 하면 되겟다.


DFS()로 풀어보자.



2. 풀이


DFS()는 재귀적으로 X에 연결된 노드가 몆개인지 알려다 줘야 한다.


DFS(1)이 DFS(2)를 불렀고, 최종적으로는 DFS(1)에게 DFS(2)에서 얼마나 진행되는지 알려줘야 하는 것이다.



3. 코드


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
#include <stdio.h>
#include <vector>
using namespace std;
 
int n, m, a, b;
int visit[101];
vector<vector<int>> map;
 
int dfs(int x) {
    int cnt = 1;
    visit[x] = 1;
 
    for (auto next : map[x]) {
        if (visit[next])
            continue;
 
        cnt += dfs(next);
    }
    return cnt;
}
 
int main() {
    scanf("%d %d", &n, &m);
    map.resize(n + 1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }
 
    printf("%d", dfs(1) - 1);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 3055 탈출  (3) 2018.01.14
백준) 10216 Count Circle Groups  (0) 2017.10.09
백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 7576 토마토  (0) 2017.09.28

2178. 미로 탐색

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




1. 접근


탐색은 BFS나 DFS로 조질 수 있다. 하지만 이동을 최소로 해야하기 때문에 BFS로 조져야 한다.



2. 풀이


이동의 횟수도 알아야 하기 때문에 큐질의 레벨을 기억해야 한다.


따라서 현재 레벨만큼 큐질을 하는 bfs질을 쓰자.



만약 (1, 1)에서 이동 할 수 있는 칸이 두 개 라면 다음 레벨은 두 칸이 저장될 것이다.


다음 레벨에서 큐질을 할 때면 두 칸에서 또 진행할 수 있는 칸들이 큐에 들어간다.



3. 코드


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
60
61
62
#include <stdio.h>
#include <queue>
using namespace std;
 
struct col {
    int x, y;
};
 
char buf[101];
int map[100][100];
int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
int a, b;
 
int bfs() {
    queue<col> q;
    q.push({ 0, 0 });
 
    int cnt = 2;
 
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            int x = q.front().x;
            int y = q.front().y;
            q.pop();
 
            if (map[x][y] != 1)
                continue;
            map[x][y] = cnt;
 
            if (x == a - 1 && y == b - 1)
                return cnt;
 
            for (int j = 0; j < 4; ++j) {
                int xx = x + dir[j][0];
                int yy = y + dir[j][1];
 
                if (xx < 0 || xx >= a || yy < 0 || yy >= b)
                    continue;
                if (map[xx][yy] != 1)
                    continue;
 
                q.push({ xx,yy });
            }
        }
        cnt++;
    }
    return cnt;
}
 
int main() {
    scanf("%d %d", &a, &b);
    for (int i = 0; i < a; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < b; ++j)
            map[i][j] = buf[j] - '0';
    }
 
    printf("%d", bfs() - 1);
 
    return 0;
}
cs



bfs 도중에 재방문을 막는 visit 처리는 따로 visit[][] 배열을 쓰지 않아도, 기존 맵의 정보를 고쳐가면서도 할 수 있었다.

'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 10216 Count Circle Groups  (0) 2017.10.09
백준) 2606 바이러스  (0) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 7576 토마토  (0) 2017.09.28
백준) 9466 텀 프로젝트  (0) 2017.09.03

7569. 토마토

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




1. 접근


http://js1jj2sk3.tistory.com/59 이랑 똑같다.


맵만 삼차원으로 바뀌었음.



2. 풀이


방향만 6방향으로 늘려주면 해결



3. 코드


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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <queue>
using namespace std;
 
int m, n, h, cnt;
int tomato[100][100][100];
int visit[100][100][100];
int dir[6][3] = { {-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1} };
 
struct col {
    int x, y, z;
};
queue<col> q;
 
int bfs() {
    int ans = 1;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            col c1 = q.front();
            q.pop();
            int x = c1.x, y = c1.y, z = c1.z;
 
            if (visit[x][y][z])
                continue;
            else
                visit[x][y][z] = 1;
 
            for (int j = 0; j < 6; ++j) {
                int xx = x + dir[j][0];
                int yy = y + dir[j][1];
                int zz = z + dir[j][2];
 
                if (xx < 0 || xx >= h)
                    continue;
                if (yy < 0 || yy >= n)
                    continue;
                if (zz < 0 || zz >= m)
                    continue;
                if (tomato[xx][yy][zz] == -1)
                    continue;
 
                if (tomato[xx][yy][zz] == 0) {
                    q.push({ xx,yy,zz });
                    tomato[xx][yy][zz] = 1;
                    cnt--;
                }
                
                if (cnt == 0)
                    return ans;
            }
        }
        ans++;
    }
    return -1;
}
 
int main() {
    scanf("%d %d %d", &m, &n, &h);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < m; ++k) {
                scanf("%d", &tomato[i][j][k]);
                if (tomato[i][j][k] == 0)
                    cnt++;
                else if (tomato[i][j][k] == 1)
                    q.push({ i,j,k });
            }
        }
    }
    printf("%d\n", bfs());
 
    return 0;
}
cs



'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2606 바이러스  (0) 2017.10.09
백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7576 토마토  (0) 2017.09.28
백준) 9466 텀 프로젝트  (0) 2017.09.03
백준) 1194 달이 차오른다, 가자.  (0) 2017.07.07

7576. 토마토

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




1. 접근


익은 토마토는 주변의 익지 않은 토마토를 전염시켜 익게 만든다.


주변이란 위, 아래, 왼쪽, 오른쪽의 사방향을 말하며, 익은 토마토의 전파는 하루가 걸린다.



맵의 모든 토마토를 익게 만드려면 몇 일이 걸릴까?


실제로 익어가는 과정을 시뮬레이션해보면 알 수 있다.


다만 익은 토마토를 기록해주고 전파되는 과정을 구현하고, 동시에 모든 토마토가 익었는지 확인하는 구현도 필요한데,


마침 BFS는 매우 유사한 구조를 띄고 있다.



익은 토마토를 기점으로 전파하는 방법은, 노드를 방문해나가는 과정과 비슷하며,

익은 토마토를 다시는 확인할 필요가 없는 구현은, visit을 체크하면서 다시 방문하지 않는 과정과 같기 때문이다.



2. 풀이


먼저 0일차의 익은 토마토의 좌표들을 큐에 저장한다. 1일차로 나아갈려면 어떻게 해야할까?


BFS의 특성상 진행할 수 있으면 다시 큐에 들어가야 하므로, 일자를 기록할려면 0일차의 토마토 갯수만큼 큐질을 해야한다.



따라서 큐의 사이즈만큼(X일차에 새롭게 익은 토마토 갯수)만 큐질을 하면 일자를 기억하면서도 큐질을 할 수 있다.


또한 0인 토마토를 1로 익게 만들고 나서 0인 토마토가 더이상 없으면 탈출조건으로 잡을 수 있다.



이렇게 하면 온갖 큐질 이후에도 0인 토마토가 남는 상황도 체크할 수 있다.




3. 코드


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
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <queue>
using namespace std;
 
int tomato[1000][1000], visit[1000][1000], m, n;
int dir[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
int cnt, size, x, y, xx, yy;
 
struct col {
    int x, y;
};
queue<col> que;
 
int bfs() {
    int ans = 1;
    while (!que.empty()) {
        int size = que.size();
        for (int i = 0; i < size; ++i) {
            col c1 = que.front();
            que.pop();
            x = c1.x, y = c1.y;
 
            if (visit[x][y])
                continue;
            else
                visit[x][y] = 1;
 
            for (int j = 0; j < 4; ++j) {
                xx = x + dir[j][0];
                yy = y + dir[j][1];
 
                if (xx < 0 || xx >= n || yy < 0 || yy >= m)
                    continue;
                else if (tomato[xx][yy] == -1)
                    continue;
 
                else if (tomato[xx][yy] == 0) {
                    que.push({ xx,yy });
                    tomato[xx][yy] = 1;
                    cnt--;
                }
 
                if (cnt == 0)
                    return ans;
            }
        }
        ans++;
    }
    return -1;
}
 
int main() {
    scanf("%d %d", &m, &n);
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &tomato[i][j]);
 
            if (tomato[i][j] == 1)
                que.push({ i,j });
            else if (tomato[i][j] == 0)
                cnt++;
        }
    }
    printf("%d", bfs());
 
    return 0;
}
cs



사실 visit 배열을 따로 쓰지 않아도 BFS질을 할 수 있긴 하다.

'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 9466 텀 프로젝트  (0) 2017.09.03
백준) 1194 달이 차오른다, 가자.  (0) 2017.07.07
백준) 2667 단지번호붙이기  (0) 2017.07.07

9466. 텀 프로젝트





1. 접근


결국엔 사이클을 찾음과 동시에 사이클에 원소가 몇개나 있는지 알 수 있어야 한다.


심플함이 먹히니까 학생들을 노드로, 희망사항을 간선으로 생각하여 그래프를 구성하자.


이제 사이클을 찾는 작업은 심플한 DFS로 가능할 거이다.




2. 풀이


결국엔 모든 노드에 대해 DFS를 일단 실행시켜보긴 할 것이다.


함수는 시작점과, 현재 방문지점, 지금까지 몇개나 거쳐왔는지의 정보를 알고 있어야 한다.


이유는 다음과 같다.



노드의 상태는 방문한 적이 있거나, 방문한 기록이 없거나 양자택일이다.


방문한 적이 없다면 필요한 사항을 기록하고 간선을 따라 이동하면 될것이다.



방문한 적이 있다면 이유는 두가지중 하나다.


현재의 노드가 속한 사이클이 돌고 돌아서 다시 자기 자신에게 돌아왔거나,


아니면 현재 노드가 속하지 않은 사이클이 기록되고 이미 끝나버렸는데,

구질구질하게 현재의 노드는 그 사이클에 속하고 싶어하기 때문이다.



이 두가지를 구분하기 위해 시작점을 알아야 한다.


노드에 시작점을 기록했다면(사이클의 시작인 셈) 같은 사이클인지, 아닌지 구분할 수 있다.


같은 사이클이라면 현재의 깊이와 과거 기록되었던 깊이의 차이를 구하면, 사이클의 노드 수를 알 수 있다.



3. 코드


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
#include <stdio.h>
#include <string.h>
using namespace std;
 
int t, n, ans;
int arr[100001], visit[100001], cycle[100001];
 
int dfs(int start, int cur, int dep) {
    visit[cur] = dep;
    cycle[cur] = start;
 
    int next = arr[cur];
 
    if (visit[next] == 0) {
        dfs(start, next, dep + 1);
    }
    else if (visit[next] != 0 && start == cycle[next])
        return dep - visit[next] + 1;
    else if (visit[next] != 0 && start != cycle[next])
        return 0;
}
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
 
        memset(visit, 0, sizeof(visit));
        ans = 0;
 
        for (int i = 1; i <= n; ++i)
            scanf("%d", &arr[i]);
 
        for (int i = 1; i <= n; ++i) {
            if (visit[i] != 0)
                continue;
            if (visit[arr[i]] == 0)
                ans += dfs(i, i, 1);
        }
        printf("%d\n", n - ans);
    }
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 7576 토마토  (0) 2017.09.28
백준) 1194 달이 차오른다, 가자.  (0) 2017.07.07
백준) 2667 단지번호붙이기  (0) 2017.07.07

1194 달이 차오른다, 가자.

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되 버렸다. 결국 민식이는 모두 잠든 새벽 네시 반 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되있다.

  • 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
  • 벽 : 절대 이동할 수 없다. (‘#’)
  • 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가게 되면 열쇠를 집는다. (소문자 a - f)
  • 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (대문자 a - f)
  • 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
  • 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 되도록 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (N,M <= 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

예제 입력 

1 7
f0.F..1

예제 출력 

7



1. 접근


행렬을 순회하면서 최소 이동 횟수를 찾아야 하기 때문에 BFS를 채용.


2. 세부사항


열쇠를 습득했는지 여부에 따라 이동방식이 바뀌기 때문에 매번 방문시 열쇠 보유 상태를 갱신하고 기억해야한다.

따라서 삼차원 행렬을 BFS로 순회하면서 탐색한다. X, Y 축이 미로이고, Z축이 열쇠 보유 상태인 셈.

시작점이 주어지고 지도에서 1을 찾으면 종료되므로,

최악의 경우 모든 지점을 방문하는 N*M*(가능한 열쇠보유 상태의 경우)에 비례.


3. 코드


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
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
 
char map[50][51];
int visit[50][50][1 << 7]; //6자리 2진수를 만들기 위해 7번 시프트
int d[4][2] = { {-1, 0},{1, 0},{0, -1},{0, 1} };
int n, m, stx, sty;
 
int bfs() {
    visit[stx][sty][0] = 1;
    queue<pair<pair<int, int>, int>> q;
    q.push({ {stx, sty}, 0 });
 
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int k = q.front().second;
            q.pop();
 
            if (map[x][y] == '1')
                return visit[x][y][k] - 1;
 
            for (int i = 0; i < 4; ++i) {
                int xx = x + d[i][0];
                int yy = y + d[i][1];
 
                if (xx < 0 || yy < 0 || xx >= n || yy >= m || map[xx][yy] == '#' || visit[xx][yy][k] != 0)
                    continue;
                if ('a' <= map[xx][yy] && map[xx][yy] <= 'f') {
                    int kk = k | (1 << (map[xx][yy] - 'a')); // OR연산으로 열쇠보유상태를 갱신
                    if (visit[xx][yy][kk] == 0) {
                        visit[xx][yy][k] = visit[x][y][k] + 1;
                        visit[xx][yy][kk] = visit[x][y][k] + 1;
                        q.push({ {xx, yy}, kk });
                    }
                }
                else if ('A' <= map[xx][yy] && map[xx][yy] <= 'F') {
                    int kk = k & (1 << (map[xx][yy] - 'A')); // AND연산으로 해당 열쇠를 보유 중인지 확인
                    if (kk != 0) {
                        visit[xx][yy][k] = visit[x][y][k] + 1;
                        q.push({ {xx, yy}, k });
                    }
                }
                else if (visit[xx][yy][k] == 0) {
                    visit[xx][yy][k] = visit[x][y][k] + 1;
                    q.push({ {xx, yy}, k });
                }
            }
        }
    }
    return -1;
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", map[i]);
        for (int j = 0; j < m; ++j) {
            if (map[i][j] == '0') {
                stx = i;
                sty = j;
            }
        }
    }
    printf("%d", bfs());
 
    return 0;
}
cs


4. 후기


열쇠 보유 상태를 어떤 형식으로 저장해야 하는지 한참 헤맸다.

비트마스킹 기법을 새롭게 알게 되었으니 기억하도록 하자.

처음 제출 했을 당시엔 열쇠 상태 갱신에만 신경쓰다보니 메모리 초과가 떴다.

열쇠 레벨로 올라가고 (Z축) 큐에 남겨진 기존 레벨들의 탐색을 처리해주지 않아서 였다.

'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 7576 토마토  (0) 2017.09.28
백준) 9466 텀 프로젝트  (0) 2017.09.03
백준) 2667 단지번호붙이기  (0) 2017.07.07

2667. 단지번호붙이기


문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 

3
7
8
9


1. 접근


DFS/BFS 문제.

모든 행렬을 순회해야 하므로 N^2 안에 수행.



2. 세부사항


모든 행렬을 순회하면서 1이면 DFS/BFS를 수행한다.

수행 시작시에 카운트용 변수를 선언해서 순회 중에 만난 1의 수를 저장하고, 수행이 끝나면 최종적인 카운트 값을 저장한다.

최후에 저장된 카운트들을 오름차순 정렬하고, 개수와 각 카운트들을 출력한다.



3. 코드


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
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
int map[25][25];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int que[50];
char buf[26];
 
int dfs(int x, int y) {
    int cnt = 1;
    map[x][y] = 2;
 
    for (int i = 0; i < 4;++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || xx >= n || yy < 0 || yy >= n)
            continue;
        if (map[xx][yy] != 1)
            continue;
 
        cnt += dfs(xx, yy);
    }
    return cnt;
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < n; ++j)
            map[i][j] = buf[j] - '0';
    }
 
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (map[i][j] == 1)
                que[cnt++] = dfs(i, j);
 
    printf("%d\n", cnt);
    sort(que, que + cnt);
    for (int i = 0; i < cnt; ++i)
        printf("%d\n", que[i]);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 7576 토마토  (0) 2017.09.28
백준) 9466 텀 프로젝트  (0) 2017.09.03
백준) 1194 달이 차오른다, 가자.  (0) 2017.07.07

+ Recent posts

티스토리툴바