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


가장 쉬운 bfs문제입니다.

최소의 칸 수를 구하라? 즉 bfs를 이용해서 가장 먼저 도달하는 너비를 출력하라는 말입니다.

bfs는 항상 최적을 보장하기 때문입니다.


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
75
76
77
78
#include <stdio.h>
 
const int QUEUE_SIZE = 100 * 100 * 4;
 
typedef struct qs {
    int x, y, b;
}qs;
 
 
typedef struct queue {
    qs data[QUEUE_SIZE];
    int front, rear;
 
    queue() {
        front = rear = 0;
    }
 
    int empty() {
        return front == rear;
    }
 
    void push(qs d) {
        rear = (rear + 1) % QUEUE_SIZE;
        data[rear] = d;
    }
 
    qs pop() {
        front = (front + 1) % QUEUE_SIZE;
        return data[front];
    }
}queue;
 
 
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
char map[100][100];
int visit[100][100];
 
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
 
    getchar();
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = getchar();
        }
        getchar();
    }
 
    queue q;
    q.push(qs{0, 0, 1});
    visit[0][0] = 1;
    
    while (!q.empty()) {
        qs front = q.pop();
 
        if (front.x == m - 1 && front.y == n - 1) {
            printf("%d", front.b);
            break;
        }
 
        for (int i = 0; i < 4; i++) {
            int nx = front.x + dx[i];
            int ny = front.y + dy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
            if (map[nx][ny] == '0') continue;
 
            visit[nx][ny] = 1;
            q.push(qs{ nx, ny, front.b + 1 });
        }
 
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[2667] 단지번호붙이기  (0) 2017.09.15
[10216] Count Circle Groups  (0) 2017.08.10
[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20

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


STL을 자꾸 쓰니까 실력이 줄어드는 것 같아서..

STL없이 구현해보려고 노력하고 있습니다.


동서남북으로 연결된 지역은 같은 단지로 취급합니다.

dfs를 통해서 수를 체크하여 리턴시키고


삽입정렬로 그 개수를 정렬했습니다.


어렵지 않은 문제입니다.


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
#include <iostream>
#include <string>
 
using namespace std;
 
string map[25];
bool visit[25][25];
 
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int n;
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int dfs(int x, int y) {
    if (visit[x][y]) return 0;
    visit[x][y] = 1;
 
    int ret = 1;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || ny < 0 || nx >= n || ny >= n || map[nx][ny] == '0') continue;
        ret += dfs(nx, ny);
    }
 
    return ret;
}
 
void sort(int *arr, int size, int value) {
    int i = size - 1;
    while (i >= 0 && arr[i] > value) {
        arr[i + 1] = arr[i];
        i--;
    }
 
    arr[++i] = value;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> map[i];
    }
 
    int ret = 0;
    int cnt[25 * 25];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == '0') continue;
 
            int tmp = dfs(i, j);
            if (tmp) {
                sort(cnt, ret, tmp);
                ret++;
            }
        }
    }
 
    cout << ret<<'\n';
 
    for (int i = 0; i < ret; i++) {
        cout << cnt[i] << '\n';
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[2178] 미로 탐색  (0) 2017.09.15
[10216] Count Circle Groups  (0) 2017.08.10
[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20

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


처음에 단순히 dfs로 해결했습니다.

간단하지만 런타임 시간이 꽤 오래 걸리더군요.

일단 다 풀고나서 다른 분들이 어떻게 풀었나 봤더니


disjoint-set(union-find)로 푸셨더라구요!


그래서 저도 다시 풀어보았습니다.


간단했습니다. 우선 연결되어있다면 union을 해서 같은 그룹으로 묶습니다.

union을 한다고 모든 노드에서의 부모가 바뀌는 것은 아닙니다.

x와 y를 유니온 하면 x와 y의 부모만 바뀌는 것이므로

다시한번 find를 해줘야 완전히 갱신이 됩니다.

아무튼!! 이것은 union-find에 대해서 공부하시면 알게되실겁니다.


그리고 나서 모든 노드에 대해 그루핑이 끝났다면!


그룹이 몇개인지 세어줘야합니다!

저는 간단하게 노드 3천개에 대한 tmp 배열을 만들어서

해당 노드의 부모가 tmp배열에서 true라면 이미 센 그룹이므로 넘어가고 

false라면 안센 그룹이므로 tmp배열을 갱신시켜주고

그룹의 개수를 늘려줍니다.


uinon-find 코드입니다.

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
75
76
77
#include <iostream>
#include <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
 
int parent[3000];
int n;
 
bool isConneted(int a, int b) {
    int x = pos[a].first - pos[b].first;
    int y = pos[a].second - pos[b].second;
    int z = r[a] + r[b];
 
    return (x * x + y * y) <= z * z;
}
 
int Find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
 
    if (x != y) {
        parent[x] = y;
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        cin >> n;
 
        for (int i = 0; i < n; i++) parent[i] = i;
        
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (isConneted(i, j) && parent[i] != parent[j]) {
                    Union(i, j);
                }
            }
        }
 
        bool tmp[3000] = { 0, };
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            int p = Find(i);
            if (!tmp[p]) {
                tmp[p] = 1;
                ret++;
            }
        }
 
        cout << ret << '\n';
    }
 
    return 0;
}
cs



dfs코드입니다.

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
pii pos[3000];
int r[3000];
bool visit[3000];
int n;
 
int calcDistance(pii a, pii b) {
    int  x = (a.first - b.first);
    int y = (a.second - b.second);
    return x * x + y * y;
}
 
void dfs(int idx) {
    for (int i = 0; i < n; i++) {
        int rSum = r[idx] + r[i];
        if (idx == i || visit[i] || calcDistance(pos[idx], pos[i]) > rSum * rSum) continue;
        visit[i] = 1;
        dfs(i);
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(visit, 0, sizeof(visit));
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            cin >> pos[i].first >> pos[i].second >> r[i];
        }
 
        int ret = 0;
 
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                dfs(i);
                ret++;
            }
                
        }
        cout << ret << '\n';
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[2178] 미로 탐색  (0) 2017.09.15
[2667] 단지번호붙이기  (0) 2017.09.15
[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20

https://www.acmicpc.net/source/6343472


사이클이 몇개인지 찾는 문제입니다.!


인풋에서 1차원 배열에 다음 노드가 뭔지 저장 하고!

방문체크 하면서 들어갔던 곳으로 또가면 싸이클이 형성이되겠죠!


여기서 싸이클 종류가 두개가 생기죠!!

1. 순열 싸이클

2. 구냥 싸이클


1번은 문제에서 제시한거처럼 시작점으로 다시 돌아오는 사이클을 '순열 사이클'이라고 하는거같아요!

2번은 시작점을 제외한 노드로 다시 방문하는 경우 순열 사이클이 아니겠지요~~~


코드 보시면 이해가실거에욥!!


코드입니당.

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 <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int nextNode[1001];
bool visit[1001];
 
bool isCycle(int start, int now) {
    visit[now] = 1;
 
    if (nextNode[now] == start) return 1; //다음 노드가 시작점이면 싸이클이 맞으므로 리턴
    else if (visit[nextNode[now]]) return 0; // 시작점이 아닌데 방문했던 곳을 방문한다?? 온전한 순열 사이클이 아니죵
    else return isCycle(start, nextNode[now]); // 방문안했으면 무작정 들어가기!!!!!!!!!!!
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(visit, 0, sizeof(visit));
        int n;
        cin >> n;
 
        for (int i = 1; i <= n; i++) {
            cin >> nextNode[i];
        }
 
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            if (visit[i]) continue;
            ret += isCycle(i, i);
        }
        cout << ret << '\n';
    }
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[2667] 단지번호붙이기  (0) 2017.09.15
[10216] Count Circle Groups  (0) 2017.08.10
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20
[1941] 소문난 칠공주  (1) 2017.07.01

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


음..

next_permutation??이라는 함수가 있습니다.

알고리즘 헤더에 있는 함수인데..

이거 쓰면 엄청 쉽게 풀 수 있는데!!!!!!!!!!


기초가 튼튼해야합니다!


dfs로 해봅시다!!!!!!!!!!!!!!!!!!!!!!

그냥 배열을 n의 최대값만큼 만들어서

방문체크하면서 dfs하면 끝입니당!!!!!!!!!!!!


이해안가실 떈 디버깅이 짱짱맨!!


풀코드입니다.

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
bool visit[10];
int output[10];
 
void f(int num, int d, int n) {
    output[d] = num;
 
    if (d == n) {
        for (int i = 1; i <= n; i++) cout << output[i] << ' ';
        cout << '\n';
        return;
    }
 
 
    for (int i = 1; i <= n; i++) {
        if (visit[i]) continue;
        visit[i] = 1;
        f(i, d + 1, n);
        visit[i] = 0;
    }
}
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        visit[i] = 1;
        f(i, 1, n);
        visit[i] = 0;
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[10216] Count Circle Groups  (0) 2017.08.10
[10451] 순열 사이클  (0) 2017.07.27
[1058] 친구  (0) 2017.07.20
[1941] 소문난 칠공주  (1) 2017.07.01
[2146] 다리 만들기  (2) 2017.05.23

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


(친구)와 (친구의 친구)의 최대치를 출력하는 문제입니다.

간단하게 생각했고 bfs를 이용하여 너비 2까지 도달하면 탈출하여

방문했던 곳을 전부 체크하면 해결할 수 있는 문제입니다.


어려운 것은 없었습니다.


풀 코드입니다.

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
#include <iostream>
#include <string.h>
#include <queue>
 
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE 500000
//ios::sync_with_stdio(false); cin.tie(0);
 
char map[55][55];
bool visit[55];
int n;
 
int bfs(int vertex) {
    memset(visit, 0, sizeof(visit));
 
    queue<pair<int, int> > q;
    
    q.push(make_pair(vertex, 0));
    visit[vertex] = 1;
 
    while (!q.empty()) {
        int now = q.front().first;
        int breath = q.front().second;
        q.pop();
 
        if (breath == 2) break; //친구의 친구가 되면 탈출
 
        for (int i = 0; i < n; i++) {
            if (map[now][i] == 'Y' && !visit[i]) {
                visit[i] = 1;
                q.push(make_pair(i, breath + 1));
            }
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) ret += visit[i];
 
    return ret - 1; // 자기 자신은 제외
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    //인풋
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) ret = max(ret, bfs(i));
 
    cout << ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[10451] 순열 사이클  (0) 2017.07.27
[10974] 모든 순열  (2) 2017.07.27
[1941] 소문난 칠공주  (1) 2017.07.01
[2146] 다리 만들기  (2) 2017.05.23
[14503] 로봇 청소기  (2) 2017.04.18

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



처음에 행렬 크기도 작고 dfs로 해결하면 끝이겠다 싶었습니다.

하지만.. 예제케이스를보면 ㅜ 모양 등 dfs로는 만들 수 없는 모양이 존재했습니다..


짱돌을 아무리 굴려도 해결할 수 없는..ㅠㅠ

블로그를 참조했습니다.


해결방법은 행렬이 작다는 것을 이용한 아이디어였습니다.

어떻게 이용하냐!


하면...


결국 25칸의 학생들 중에 7명을 고르면 된다는 점입니다!(다른 분은 어떻게 푸셨는지 모르겠음.. 아이디어만 스틸해옴..)


저는 그래서 dfs를 이용하여 학생들을 선택할 수 있는 모든 방법을 만들었습니다.

1번~25번까지의 학생이 있다고 생각하면 !

1,2,3,4,5,6,7

1,2,3,4,5,6,8

..

...

19,20,21,22,23,24,25

까지의 경우가 있겠죠!


이 모든 경우의 수는 25C7 입니다.


이렇게  dfs를 이용해서 깊이가 7 즉 7명의 학생까지 선택하면!

dfs의 매개변수에 S에 다솜파가 몇명인지를 계속 넘겨줍니다!

만약에 다솜파가 4명 이상이면! dfs로 선택한 7명이 전부 연결되어있는지를 확인합니다.!!!

그래서 전부 연결되어있다면 1을 리턴하여 카운트. 아니면 0을 리턴합니다.!


아래는 코드입니다.

궁금한 점은 댓글 달아주세요~~



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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 5
 
using namespace std;
 
char map[MAX_SIZE][MAX_SIZE];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
 
int visit;
 
pair<int, int> toPos(int num) {
    return make_pair(num / 5, num % 5);
}
 
int toNum(pair<int, int> pos) {
    return pos.first * 5 + pos.second;
}
 
//내가 선택한 7명이 연결되어있는지를 확인하는 함수
bool exploration(int state, pair<int, int> pos) {
    visit |= 1 << toNum(pos); // 전역 변수 visit에 해당 학생을 쉬프트하여 체크
    if (state == visit) return 1; //isConnected에서 넘겨받은 state와 exploration으로 방문한 학생이 같으면 리턴 1
 
    bool ret = 0;
 
    for (int i = 0; i < 4; i++) {
        pair<int, int> npos = make_pair(pos.first + dx[i], pos.second + dy[i]);
 
        if (npos.first < 0 || npos.second < 0 || npos.first >= 5 || npos.second >= 5) continue;
        
        int nNum = toNum(npos);
 
        if (visit & (1 << nNum)) continue;
        if ((1 << nNum) & state) ret = max(ret, exploration(state, npos));
    }
    return ret;
}
 
//전부 연결되어있다면 1을 아니라면 0을 리턴하는 함수
bool isConnected(int state) {
    pair<int, int> now;
    
    //포문을 이용하여 내가 선택한 7명 중 한명을 찾아 탐색의 시작점으로 선택
    for (int i = 0; i < 25; i++) {
        if ((1 << i) & state) {
            now = toPos(i);
            visit = 1 << i;
            break;
        }
    }
    
    return exploration(state, now);
}
 
//dfs를 이용하여 25명의 학생 중 7명을 고르는 함수
int f(int num, int d, int state, int sCnt) {
    if (d == 7) {
        if (sCnt >= 4) return isConnected(state);
        else return 0;
    }
    int ret = 0;
 
    for (int i = num + 1; i < 25; i++) {
        pair<int, int> pos = toPos(i);
        ret += f(i, d + 1, state | (1 << i), map[pos.first][pos.second] == 'S' ? sCnt + 1 : sCnt);
    }
 
    return ret;
}
 
int main() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            map[i][j] = getchar();
        }
        getchar();
    }
 
    int ret = 0;
    for (int i = 0; i < 25 - 6; i++) {
        pair<int, int> pos = toPos(i);
        ret += f(i, 1, 1 << i, map[pos.first][pos.second] == 'S' ? 1 : 0);
    }
    printf("%d", ret);
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20
[2146] 다리 만들기  (2) 2017.05.23
[14503] 로봇 청소기  (2) 2017.04.18
[14502] 연구소  (5) 2017.04.18

삼성전자 면접 준비 하느라고 블로그 활동을 못했네요.

오랜만에 글 올립니다.

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

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


이 문제는 2가지 절차로 풀었습니다.

1. 대륙마다 번호 붙이기.

2. 대륙끼리 가장 짧은 길이로 연결하기.


input을 받을 때 1이라면 land라는 벡터에 x, y 값을 넣었습니다.

그 후에 land_mark()라는 함수를 통해서 각 대륙마다 번호를 바꿔줍니다. (map[][]에 저장됨.)

번호를 붙인 후 바다와 연결된 대륙이라면(주변에 0이 있으면) bfs를 통해서 자신과 다른 대륙 넘버를 만나면 return해주는 dist()라는 함수를 이용합니다.


아래는 코드입니다.

궁금하신 것은 댓글 달아주세요.


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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <cstdio>
#include <iostream>
#include <list>
#include <queue>
#include <string.h>
#define MAX_SIZE 100
#define INF 0x7fffffff
 
using namespace std;
 
 
//input
int n;//맵크기
int map[MAX_SIZE][MAX_SIZE];//맵
 
//process
int visit[MAX_SIZE][MAX_SIZE];//방문체크
vector<pair<int, int> > land;//땅을 저장할 벡터
int land_number;//땅마다 넘버 붙이기
int visit_number;//방문체크 넘버
 
//direct
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
//땅마다 넘버붙이기 함수
void land_mark(int x, int y)
{
    if(visit[x][y] == 1) return;
    visit[x][y] = 1;
 
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
 
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        map[x][y] = land_number;
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= n || ny >= n || visit[nx][ny]) continue;
            if(!map[nx][ny]) continue;
            visit[nx][ny] = 1;
 
            q.push(make_pair(nx, ny));
 
        }
    }
 
    land_number++;
}
 
//거리를 측정하는 bfs함수 ln은 랜드 넘버
int dist(int x, int y, int ln)
{
    bool flag = 0;
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        if(map[nx][ny] == 0)
        {
            flag = 1;
            break;
        }
    }
 
    if(!flag) return INF;//네 방향에 바다가 없으면 리턴
    visit_number++;
 
    queue<pair<pair<int, int>, int> > q;
    q.push(make_pair(make_pair(x, y), 0));
 
    while(!q.empty())
    {
        x = q.front().first.first;
        y = q.front().first.second;
        int weight = q.front().second;
        q.pop();
 
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= n || ny >= n || visit[nx][ny] == visit_number) continue;
 
            if(map[nx][ny] == ln) continue;
            else if(map[nx][ny] != ln && map[nx][ny] != 0) return weight;
 
            visit[nx][ny] = visit_number;
            q.push(make_pair(make_pair(nx, ny), weight + 1));
        }
    }
 
    return INF;
}
 
 
int main()
{
 
    scanf("%d", &n);
 
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &map[i][j]);
            if(map[i][j] == 1) land.push_back(make_pair(i, j));
        }
    }
 
    land_number = 1;
 
    for(int i = 0; i < land.size(); i++) land_mark(land[i].first, land[i].second);
 
    memset(visit, 0, sizeof(visit));
    int ret = INF;
 
    for(int i = 0; i < land.size(); i++)
    {
        int x = land[i].first;
        int y = land[i].second;
        ret = min(ret, dist(x, y, map[x][y]));
    }
 
    printf("%d\n", ret);
 
 
    return 0;
 
}
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[1058] 친구  (0) 2017.07.20
[1941] 소문난 칠공주  (1) 2017.07.01
[14503] 로봇 청소기  (2) 2017.04.18
[14502] 연구소  (5) 2017.04.18
[14501] 퇴사  (4) 2017.04.17

+ Recent posts

티스토리툴바