Backjoon Online Judge 

"10216번 : Count Circle Groups" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/2667



문제 및 코드 설명입니다.


'10216번 : Count Circle Groups' 문제의 경우 모든 좌표쌍을 기준으로 그룹 여부를 판단해야 하는 문제로 조금 까다로울 수 있는 문제였습니다.

문제 풀이는 Union Find를 이용한다면 더 쉽고 빠르게 풀 수 있겠지만 DFS로 문제 분류가 되어있어 이번에는 DFS로 해결하였습니다.

(Union Find를 이용한 풀이도 추후 시도 할 예정입니다.)


먼저 적군의 진영을 저장하기 위한 벡터를 만들고 벡터에 4개의 정보(x,y,R,visit)를 저장하기 위해 pair를 이용하였습니다.


적군의 진영의 수는 N이므로 벡터의 첫번째부터 N번째까지 dfs 탐색을 진행했습니다.

이때 방문되지 않은 진영이라면 서로 다른 진영으로 분류하였고, 진영의 수(=group_num)을 더해주었습니다.

DFS는 위의 반복문에서 방문되지 않은 진영을 발견하였을 때 호출하였고, 그 진영으로부터 통신 가능한 진영을 모두 파악합니다.

DFS를 통해 현재 진영으로 부터 방문 될 수 있는 진영을 모두 파악하여 그 진영의 visit 값을 1로 설정합니다.

위 과정을 반복하여 N개의 진영을 모두 조사한다면 서로 다른 진영의 갯수를 출력하게 됩니다.


코드는 C++로 작성하였습니다.

 - pair문을 사용하면 (구버전)C++ 컴파일러에서 오류가 발생합니다. C++ 11 이상 컴파일러로 실행시 정상적으로 동작합니다.

 - 21번째 라인에서 i의 시작을 k+1로 설정하여 결과에 오류가 발생했습니다. 코드 작성 시 참고 하시면 좋을 듯 합니다.

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
#include <iostream>
#include <vector>
#define Max 5001
 
using namespace std;
typedef pair<pair<int, int>, pair<int, int>> pair4;
 
int N, group_num;    //그룹 갯수
vector<pair4> enemy;    //순서대로 x, y, R, visit여부를 저장
 
//두 지점이 통신 가능한지를 비교 (가능하면 1)
int compare(int a, int b) {
    int r = enemy[a].second.first + enemy[b].second.first;
    int x = enemy[a].first.first - enemy[b].first.first;
    int y = enemy[a].first.second - enemy[b].first.second;
    return (((x * x) + (y * y)) <= (r * r)) ? true : false;
}
 
void dfs(int k) {
    //(mistake)양방향으로 확인하기!
    for (int i = 0; i < N; i++) {
        if (enemy[i].second.second) {
            continue;
        }
        //통신 가능 하다면
        if (compare(i, k)) {
            enemy[i].second.second = 1;
            enemy[k].second.second = 1;
            dfs(i);
        }
    }
}
 
int main() {
    int T, x, y, R;
    cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> x >> y >> R;
            enemy.push_back(make_pair(make_pair(x, y), make_pair(R, 0)));
        }
 
        group_num = 0;
        for (int i = 0; i < N; i++) {
            if (!enemy[i].second.second) {    //방문하지 않았다면
                enemy[i].second.second = 1;
                dfs(i);
                group_num++;
            }
        }
        cout << group_num << endl;
        enemy.clear();
    }
}
 


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2667번 : 단지번호붙이기  (0) 2018.05.29
2606번 : 바이러스  (0) 2018.05.28
2178번 : 미로탐색  (0) 2018.05.17
7569번 : 토마토  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16

Backjoon Online Judge 

"2667번 : 단지번호붙이기" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/2667



문제 및 코드 설명입니다.


'2667번 : 단지번호붙이기' 문제도 난이도가 높지 않은 문제였습니다.

BFS, DFS 어느 알고리즘으로 풀어도 상관없으며 이전 문제 해결시 BFS 많이 이용하였기에 이번에는 DFS를 적용하여 풀어 보았습니다.


먼저 지도를 저장할 배열과 방문 정보를 저장할 배열을 저장했습니다.

또 각 단지에 속하는 집의 수를 출력하기 위해 집의 수를 저장할 vector를 하나 만들었습니다.


이후 지도의 모든 점을 체크하되, 방문하지 않았고 지도의 값이 1인(집이 있는 곳)곳을 발견한다면 그 곳을 기준으로 DFS를 실행했습니다.

DFS 실행 시 단지를 체크하므로 danzi_num을 더하고 단지의 범위를 조사합니다.(상하좌우 접근을 통해)

각각의 집을 접근할 때 마다 방문 정보를 최신화하고 단지 내에서 집의 수를 저장하는 cnt값을 증가시켰습니다.

한 단지를 모두 조사하면 cnt 값을 vector에 집어넣고 cnt값은 다시 초기화 하는 방식으로 진행했습니다.

(코드를 보고 이해하는게 빠를 것이라 생각합니다.)


코드는 C++로 작성하였습니다.

(출력 시 범위기반 for문을 사용하면 (구버전)C++ 컴파일러에서 '출력초과'가 발생합니다.

C++ 17 컴파일러로 실행시 정상적으로 동작함을 확인하였고, 호환성을 위해 범위기반 for문은 주석 처리 하였습니다.)

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>
 
#define Max 26
 
using namespace std;
 
char map[Max][Max] = { 0, };
int visit[Max][Max] = { 0, };
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int N, cnt = 0;
 
void dfs(int i, int j) {
    visit[i][j] = 1;
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k];
        int y = j + dy[k];
        if (0 <= x && x < N && 0 <= y && y < N) {
            if (map[x][y] == '1' && !visit[x][y]) {
                cnt++;
                dfs(x, y);
            }
        }
    }
}
 
int main() {
    int danzi_num = 0;
    vector<int> house_num;
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cin >> map[i];
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == '1' && !visit[i][j]) {
                danzi_num++;
                cnt = 1;
                dfs(i, j);
                house_num.push_back(cnt);
            }                
        }
    }
    sort(house_num.begin(), house_num.end());
 
    cout << danzi_num << endl;
    
    /* (범위기반 for문 : 구버전 컴파일러에서 '출력 초과'가 나타남)
    for (int i: house_num) {
        cout << i << endl;
    } */
 
    for (int i = 0; i < house_num.size(); i++) {
        cout << house_num[i] << endl;
    }
}
 



저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

10216번 : Count Circle Groups (DFS)  (0) 2018.05.31
2606번 : 바이러스  (0) 2018.05.28
2178번 : 미로탐색  (0) 2018.05.17
7569번 : 토마토  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16

Backjoon Online Judge 

"2606번 : 바이러스" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/2606



문제 및 코드 설명입니다.


'2606번 : 미로탐색' 문제의 경우 BFS나 DFS를 적용하면 매우 쉽게 풀 수 있는 문제였습니다.

문제 설명은 BFS에 더 가깝지만 DFS로 풀어도 상관없는 문제라 DFS를 적용하여 풀어 보았습니다.


먼저 컴퓨터의 연결 상태를 저장할 2차원 배열과 방문 유뮤를 저장할 visit 배열을 만들었습니다.

2차원 배열에는 연결 정보를 저장하고 1번을 시작점으로 DFS를 적용해서 문제를 해결하였습니다.

(DFS 알고리즘을 알고 있다면 아래 DFS함수는 바로 이해가 될 것이라 생각합니다.)



코드는 C++로 작성하였습니다.

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
#include <iostream>
 
#define Max 101
 
using namespace std;
 
int num;    //컴퓨터의 수
int result;    //결과 값 저장
int computer[Max][Max] = { 0, };
int visit[Max] = { 0, };
 
void dfs(int start) {
    visit[start] = 1;
    for (int i = 1; i <= num; i++) {
        if (!visit[i] && computer[start][i]) {
            result++;
            dfs(i);
        }
    }
}
 
int main() {
    int c_pair, temp1, temp2;
    cin >> num >> c_pair;
    while (c_pair--) {
        cin >> temp1 >> temp2;
        computer[temp1][temp2] = computer[temp2][temp1] = 1;
    }
    dfs(1);
    cout << result << endl;
}


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

10216번 : Count Circle Groups (DFS)  (0) 2018.05.31
2667번 : 단지번호붙이기  (0) 2018.05.29
2178번 : 미로탐색  (0) 2018.05.17
7569번 : 토마토  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16

Backjoon Online Judge 

"2178번 : 미로탐색" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/2178


'2178번 : 미로탐색' 문제의 경우 BFS로 문제를 해결했습니다.

이전에 풀었던 '7576번 : 토마토' 문제의 코드를 살짝 변경하여 해결했습니다.

(참고링크 : http://rehu.tistory.com/20)



문제 및 코드 설명입니다.


먼저 미로의 상태를 저장하기 위해 2차원 배열로 미로를 저장했습니다.

이때 BFS를 쉽게 구현하기 위해 큐를 pair로 선언하여 x좌표, y좌표를 저장했습니다.

또 미로의 상태를 연속된 숫자로 입력받으므로 일반적인 입력으로는 미로에 숫자를 하나씩 저장할 수 없습니다.

char형 배열을 통해 문자로 입력받고 ASCII 변환을 이용하여 숫자를 배열에 하나씩 저장했습니다. 


이후 시작점에서부터 상하좌우에 길이 있는지 확인하고 길이 있다면 이동횟수를 길에 저장하도록 했습니다.

(시작점의 경우 1로 설정하면 한칸 이동했다가 다시 시작점 방향으로 탐색하기 때문에 0으로 초기화 했습니다.

 물론 시작점 방향으로 탐색하면 곧 탐색이 종료되기에 초기화 과정 없이도 정답이 나오긴 합니다.)


미로의 시작점과 끝 점은 가장 멀리 있으므로 큐의 모든 원소가 사라질때까지 반복했으며, BFS 탐색 후 도착점의 값을 출력해 주었습니다.


코드는 C++로 작성하였습니다.

(단, 큐를 pair을 이용해 구현하여 C++ 11 이상에서만 정상작동 합니다.

 C++ 11 이하에서 작동되기를 원하시면 큐를 pair로 구현하는 대신 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
#include <iostream>
#include <queue>
 
#define Max 100
 
using namespace std;
 
int main() {
    int M, N, x, y, tx, ty;
    char tmp[Max];
    int maze[Max][Max] = { 0, };
    int result = 0;
    queue<pair<int, int>> q;
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        for (int j = 0; j < M; j++) {
            maze[i][j] = tmp[j] - 48;
        }
    }
    maze[0][0] = 0;
 
    q.push(make_pair(0, 0));
    int side[4] = { 1, 0, -1, 0 };
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
 
        if (maze[x][y] == 2 + result)
            result++;
 
        for (int i = 0; i < 4; i++) {
            tx = x - side[i];
            ty = y - side[3 - i];
            if (0 <= tx && tx < N && 0 <= ty && ty < M) {
                if (maze[tx][ty] == 1) {
                    maze[tx][ty] = 2 + result;
                    q.push(make_pair(tx, ty));
                }
            }
        }
        q.pop();
    }
 
    cout << maze[N-1][M-1] << endl;
    cin >> N;
}
 



저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2667번 : 단지번호붙이기  (0) 2018.05.29
2606번 : 바이러스  (0) 2018.05.28
7569번 : 토마토  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16
2293번 : 동전 1  (0) 2018.05.15

Backjoon Online Judge 

"7569번 : 토마토" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/7569



이전에 풀었던 '7576번 : 토마토' 문제에서 상자를 층으로 쌓는 기능만 추가된 문제입니다.

'7576번 : 토마토' 문제를 먼저 해결하고 온다면 현재 문제인 '7569번 : 토마토'는 쉽게 해결가능하다고 봅니다.

(참고링크 : http://rehu.tistory.com/20)


코드 부분도 "7576번 : 토마토" 문제에서 달라진 부분이 거의 없습니다.

아래 코드를 보고 비교한다면 쉽게 이해할 수 있을 것입니다.



코드는 C++로 작성하였습니다.

(단, 큐를 pair을 이용해 구현하여 C++ 11 이상에서만 정상작동 합니다.

 C++ 11 이하에서 작동되기를 원하시면 큐를 pair로 구현하는 대신 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 <iostream>
#include <queue>
 
#define Max 100
 
using namespace std;
typedef pair<int, pair<int, int>> pair3;
 
int main() {
    int M, N, H, x, y, z, tx, ty, tz;
    int box[Max][Max][Max] = { 0, };
    int result = 0;
    queue<pair3> q;
 
    cin >> M >> N >> H;
    for (int k = 0; k < H; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> box[i][j][k];
                if (box[i][j][k] == 1) {
                    q.push({ i,{j,k} });
                }
            }
        }
    }
 
    int side[6] = { 1, 0, 0, -1, 0 ,0 };
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second.first;
        z = q.front().second.second;
 
        if (box[x][y][z] == 2 + result)
            result++;
 
        for (int i = 0; i < 6; i++) {
            tx = x - side[i];
            ty = y - side[(i + 1) % 6];
            tz = z - side[(i + 2) % 6];
            if (0 <= tx && tx < N && 0 <= ty && ty < M && 0 <= tz && tz < H) {
                if (box[tx][ty][tz] == 0) {
                    box[tx][ty][tz] = 2 + result;
                    q.push(make_pair(tx, make_pair(ty, tz)));
                }
            }
        }
        q.pop();
    }
 
    for (int k = 0; k < H; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                    if (box[i][j][k] == 0) {
                        result = -1;
                        break;
                }
            }
        }
    }
    cout << result << endl;
}
 



저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2606번 : 바이러스  (0) 2018.05.28
2178번 : 미로탐색  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16
2293번 : 동전 1  (0) 2018.05.15
10844번 : 쉬운 계단 수  (0) 2018.05.13

티스토리툴바