반응형

www.acmicpc.net/problem/2178

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

 

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
#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>
using namespace std;
int n, m, cnt;
int arr[100][100], visited[100][100];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
queue<pii> q;
void bfs(int i, int j) {
    q.push({ i,j });
    visited[i][j] = 1;
    while (!q.empty()) {
        cnt++;
        // 단계별로 진행
        int size = q.size();
        while (size--) {
            int x = q.front().first;
            int y = q.front().second;
            // 끝에 도착
            if (x == n - 1 && y == m - 1) {
                cout << cnt;
                return;
            }
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (!visited[nx][ny] && arr[nx][ny]) {
                        visited[nx][ny] = 1;
                        q.push({ nx, ny });
                    }
                }
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            arr[i][j] = c - '0';
        }
    }
    bfs(0,0);
}
 
 
cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 14226 [복습 필수]  (0) 2021.02.19
백준 13913  (0) 2021.02.19
백준 1707  (0) 2021.02.19
백준 13023  (0) 2021.02.19
백준 2583  (0) 2021.02.03
반응형

www.acmicpc.net/problem/1707

 

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수

www.acmicpc.net

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
// https://www.acmicpc.net/board/view/25583
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int k, v, e, a, b, arr[20001];
vector<vector<int> > vec;
void dfs(int now) {
    // 현재 정점이 속한 그룹이 없을 때 (0일 때)
    if (!arr[now])
        arr[now] = 1;
 
    // 현재 정점이 속한 그룹이 있다면
    // 연결된 정점은 무조건 현재 정점과 반대가 되어야 함
    for (int i : vec[now]) {
        if (!arr[i]) {
            arr[i] = (arr[now] == 1 ? 2 : 1);
            dfs(i);
        }
    }
}
 
bool chk() {
    for (int i = 0; i < vec.size(); i++) {
        for (int j : vec[i]) {        // 나와 연결된 모든 정점 탐색
            if (arr[i] == arr[j])    // 연결된 정점은 무조건 다른 그룹이어야 함
                return false;        // 연결된 정점이 같은 그룹이면 FALSE
        }
    }
    return true;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> k;
    while (k--) {
        cin >> v >> e;
        memset(arr, 0, sizeof(arr));
        vec.clear();
        vec.resize(v+1);
        for (int i = 0; i < e; i++) {
            cin >> a >> b;
            vec[a].push_back(b);
            vec[b].push_back(a);
        }
        // 모든 정점에 대해서 탐색
        for (int i = 0; i < v;i++) {
            // 해당 정점이 속한 그룹이 없으면 (0이면)
            if (!arr[i])
                dfs(i);
        }
        cout << (chk() ? "YES" : "NO") << '\n';
    }
}
cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 13913  (0) 2021.02.19
백준 2178  (0) 2021.02.19
백준 13023  (0) 2021.02.19
백준 2583  (0) 2021.02.03
백준 2468  (0) 2021.02.03
반응형

www.acmicpc.net/problem/13023

 

13023번: ABCDE

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

www.acmicpc.net

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
#include <iostream>
#include <vector>
using namespace std;
int n, m, a, b, visited[2001];
vector<vector<int> > v;
void dfs(int idx, int cnt) {
    if (cnt == 5) {
        cout << 1;
        exit(0);
    }
    for (int i : v[idx]) {
        if (!visited[i]) {
            visited[i] = 1;
            dfs(i, cnt+1);
            visited[i] = 0;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    v.resize(n);
    for (int i = 0; i < m;i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            dfs(i, 1);
            visited[i] = 0;
        }
    }
    cout << 0;
}
cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 2178  (0) 2021.02.19
백준 1707  (0) 2021.02.19
백준 2583  (0) 2021.02.03
백준 2468  (0) 2021.02.03
백준 1697  (0) 2021.02.03
반응형

www.acmicpc.net/problem/2583

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

 

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
#include <iostream>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int m, n, k, cnt;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
bool visited[101][101];
priority_queue<int, vector<int>, greater<int> > q;
void dfs(int x, int y) {
    cnt++;
    visited[x][y] = 1;
    rep(i, 4) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
            if (!visited[nx][ny]) 
                dfs(nx, ny);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n >> k;
    rep(i,k){
        int lx, ly, rx, ry;
        cin >> lx >> ly >> rx >> ry;
        // 입력 받은 영역 채우기
        for (int i = lx; i < rx; i++) {
            for (int j = ly; j < ry; j++) 
                visited[i][j] = 1;
            
        }
    }
 
    int ans = 0;
    rep(i, n) {
        rep(j, m) {
            if (!visited[i][j]) {
                cnt = 0;
                dfs(i, j);
                q.push(cnt);
                ans++;
            }
        }
    }
    cout << ans << '\n';
    while (!q.empty()) {
        cout << q.top() << ' ';
        q.pop();
    }
}
cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 1707  (0) 2021.02.19
백준 13023  (0) 2021.02.19
백준 2468  (0) 2021.02.03
백준 1697  (0) 2021.02.03
백준 1012  (0) 2021.02.03
반응형

www.acmicpc.net/problem/2468

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

 

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, h, arr[101][101];
bool visited[101][101];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
void dfs(int x, int y) {
    visited[x][y] = 1;
    rep(i, 4) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
            if (arr[nx][ny] > h && !visited[nx][ny])
                dfs(nx, ny);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int min_height = 101, max_height = -1;
    rep(i, n) {
        rep(j, n) {
            cin >> arr[i][j];
            if (arr[i][j] < min_height)
                min_height = arr[i][j];
            if (arr[i][j] > max_height)
                max_height = arr[i][j];
        }
    }
    int ans = 1;
    // 최소 높이 ~ 최대 높이 한 번씩 다 해봄
    for (int k = min_height; k <= max_height; k++) {
        memset(visited, 0, sizeof(visited));
        int cnt = 0;
        h = k;
        rep(i, n) {
            rep(j, n) {
                // 도시가 강수량보다 높으면
                if (arr[i][j] > k && !visited[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans;
}
 cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 1707  (0) 2021.02.19
백준 13023  (0) 2021.02.19
백준 2583  (0) 2021.02.03
백준 1697  (0) 2021.02.03
백준 1012  (0) 2021.02.03
반응형

www.acmicpc.net/problem/1697

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

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 <queue>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pii pair<int, int>
using namespace std;
int t, m, n, k, cnt;
int arr[51][51];
bool visited[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void bfs(int x, int y) {
    cnt++;
    queue<pii> q;
    q.push({ x, y });
    visited[x][y] = true;
    while (!q.empty()) {
        pii now = q.front();
        q.pop();
        int x = now.first;
        int y = now.second;
        rep(i, 4) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (arr[nx][ny]==1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({ nx,ny });
                }
            }
        }
    }
 
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while (t--) {
        cnt = 0;
        memset(arr, 0, sizeof(arr));
        memset(visited, 0, sizeof(visited));
        cin >> m >> n >> k;
        rep(i, k) {
            int a, b;
            cin >> a >> b;
            arr[b][a] = 1;
        }
 
        rep(i,n){
            rep(j, m) {
                if (arr[i][j] == 1 && !visited[i][j])
                    bfs(i, j);
            }
        }
        cout << cnt << '\n';
    }
}
 
 
 
 cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 1707  (0) 2021.02.19
백준 13023  (0) 2021.02.19
백준 2583  (0) 2021.02.03
백준 2468  (0) 2021.02.03
백준 1012  (0) 2021.02.03
반응형

www.acmicpc.net/problem/1012

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

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 <queue>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pii pair<int, int>
using namespace std;
int t, m, n, k, cnt;
int arr[51][51];
bool visited[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void bfs(int x, int y) {
// bfs 실행할 때마다 cnt++
    cnt++;
    queue<pii> q;
    q.push({ x, y });
    visited[x][y] = true;
    while (!q.empty()) {
        pii now = q.front();
        q.pop();
        int x = now.first;
        int y = now.second;
        rep(i, 4) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (arr[nx][ny]==1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({ nx,ny });
                }
            }
        }
    }
 
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while (t--) {
        cnt = 0;
        memset(arr, 0, sizeof(arr));
        memset(visited, 0, sizeof(visited));
        cin >> m >> n >> k;
        rep(i, k) {
            int a, b;
            cin >> a >> b;
            arr[b][a] = 1;
        }
 
        rep(i,n){
            rep(j, m) {
                // 현재 1이고 방문 안했으면 bfs 
                if (arr[i][j] == 1 && !visited[i][j])
                    bfs(i, j);
            }
        }
        cout << cnt << '\n';
    }
}
 
 
 
cs
반응형

'백준 > DFS, BFS' 카테고리의 다른 글

백준 1707  (0) 2021.02.19
백준 13023  (0) 2021.02.19
백준 2583  (0) 2021.02.03
백준 2468  (0) 2021.02.03
백준 1697  (0) 2021.02.03

+ Recent posts

티스토리툴바