반응형

문제 출처

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


문제풀이

1
2
3
4
5
6
/*
* 모든 높이에 대해 잠기지 않는 안전영역의 갯수를 카운트 해주면 되는 문제
* dfs / bfs로 풀이할 수 있다. 특히 0은 고려하지 않았는데 아래 노트를 보니
* 비가 오지 않는 경우도 있다고 써져있었다.... 하지만 생각해보면 전부 높이가 1인
* 경우가 있을 수 있기 때문에 0도 고려를 해야합니다.
*/
cs


소스코드

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
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;
int n,result;
int map[MAX][MAX];
bool visit[MAX][MAX];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
void dfs(int x, int y, int height) {
    visit[x][y] = 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)    continue;
        if (map[nx][ny] > height && !visit[nx][ny])    dfs(nx, ny, height);
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    int maxDepth = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            maxDepth = max(maxDepth, map[i][j]);
        }
    }
    for (int height = 0; height <= maxDepth; height++) {
        int safeBlock = 0;
        memset(visit, 0, sizeof(visit));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] > height && !visit[i][j]) {
                    dfs(i, j, height);
                    safeBlock++;
                }
            }
        }
        result = max(result, safeBlock);
    }
    cout << result << endl;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1325] 효율적인 해킹  (0) 2019.01.23
[BOJ 10039] 평균점수  (0) 2019.01.22
[BOJ 2661] 좋은 수열  (0) 2019.01.21
[BOJ 1759] 암호만들기  (0) 2019.01.21
[BOJ 1012] 유기농 배추  (0) 2019.01.21
반응형

문제출처

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


dfs / bfs 두가지 모두 풀이가 가능하다. 하지만 분류가 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
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
int v, e;    //vertex, edge
int result;
bool visit[1001];
bool g[1001][1001];
void bfs(int s) {
    queue<int> q;
    q.push(s);
    visit[s] = 1;
    
    while (!q.empty()) {
        s = q.front();
        q.pop();
 
        for (int i = 1; i <= sizeof(g[s]); i++) {
            if (g[s][i] && !visit[i]) {
                q.push(i);
                visit[i] = 1;
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> v >> e;
    int start, end;
    // init graph...
    for (int i = 1; i <= e; i++) {
        cin >> start >> end;
        g[start][end] = 1;
        g[end][start] = 1;
    }
 
    for (int i = 1; i <= v; i++) {
        if (!visit[i]) {
            bfs(i);
            result++;
        }
    }
 
    cout << result;
    return 0;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2908] 상수  (0) 2019.01.07
[BOJ 10809] 알파벳 찾기  (0) 2019.01.07
[카카오 2019] 코딩테스트 - 무지의 먹방 라이브  (0) 2019.01.07
[BOJ 11004] K번째 수  (0) 2019.01.07
[BOJ 3047] ABC  (0) 2019.01.06
반응형

문제 출처

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


단순 bfs구현 문제이다.

ret배열이 0이라면 관계가 없으므로 -1을 출력하고 0이 아니면 해당 값을 출력하도록 했다.

bfs / dfs를 언제 사용하는지 감이 잘 안왔었는데 간단히 정리하면


bfs를 이용하는 경우

1. 시작 지점에서 가장 가까운 것을 구하고 싶은 경우

2. 탐색 범위 자체는 넓지만 어느정도 근처에 구하고 싶은 해가 존재하는 것을 알고 있는 경우

3. 탐색 범위가 굉장히 넒으며 dfs를 사용할 때 스택이 대량으로 사용될 경우 이다.


반면 dfs를 이용하는 경우는

1. 모든 경로를 탐색하고 결과를 확인해야 하는 경우

2. 문자열 등을 탐색할 때 '사전 순서로 앞에오는 것'처럼 앞에서 검색해서 찾는 것이 빠를 경우 이다.


즉, 탐색 범위가 넓은 경우와 전체 탐색을 하지 않아도 될 경우는 bfs를 이용하고 전체 탐색이 필요하거나 순차적으로 찾을 필요가 있는 경우는 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
//
//  main.cpp
//  BOJ_2644
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
 
#include<iostream>
#include<queue>
#define MAX 101
 
using namespace std;
int n, src, dest, m, adj[MAX][MAX], ret[MAX];
 
int main(int argc, const char * argv[]) {
    cin >> n >> src >> dest >> m;
    for (int i = 0; i < m; i++) {
        int x = 0, y = 0;
        cin >> x >> y;
        adj[x][y] = adj[y][x] = 1;
    }
    
    queue<int> q;
    q.push(src);
    
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (adj[now][i] == 0 || ret[i] != 0)
                continue;
            ret[i] = ret[now] + 1;
            q.push(i);
        }
    }
    cout << (ret[dest] == 0 ? -1 : ret[dest]) << endl;
    return 0;
}
 
cs





반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
[BOJ 2606] 바이러스  (0) 2018.12.28
[BOJ 2583] 영역구하기  (0) 2018.12.28
[TopCoder 전체탐색] 회문(Palindrome)  (0) 2018.12.20

+ Recent posts

티스토리툴바