반응형

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

 

25498번: 핸들 뭘로 하지

효규가 얻을 수 있는 문자열은 사전순으로 "$\text{aa}$", "$\text{aaa}$", "$\text{aaaa}$", "$\text{aaaa}$"이므로 "$\text{aaaa}$"를 핸들로 정한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열과 그래프를 입력받고, arr[500001]과 vector<int> list[500001]에 저장합니다.

 

2. node struct를 만들어 현재 노드의 번호, 인덱스 그리고 부모의 문자를 저장합니다.

 

3. queue<node> q를 만들어 bfs를 돌면서 해당 인덱스에서 가장 큰 문자를 ans에 더해주면서 문자열을 완성합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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<vector>
#include<queue>
#include<string>
 
using namespace std;
 
struct node {
    int cur, idx;
    char parent;
};
 
int N;
char arr[500001];
vector<int> list[500001];
int visited[500001];
string ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> arr;
 
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    queue<node> q;
    q.push({ 1, 1, '0'});
    visited[1] = 1;
    ans += '0';
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int idx = q.front().idx;
        const char pa = q.front().parent;
        q.pop();
 
        if (pa != ans[idx - 1]) continue;
        if (idx >= ans.size()) ans += arr[cur - 1];
        else if (ans[idx] < arr[cur - 1]) {
            ans[idx] = arr[cur - 1];
        }
 
        for (auto& next : list[cur]) {
            if (visited[next] != 1) {
                visited[next] = 1;
                q.push({ next,idx + 1, arr[cur - 1]});
            }
        }
    }
 
    ans.erase(ans.begin());
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14
[ 백준 ] 19942번 - 다이어트 (C++)  (0) 2023.10.12
[ 백준 ] 21276번 - 계보 복원가 호석 (C++)  (0) 2023.10.11
[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
반응형

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

 

3197번: 백조의 호수

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 현재 호수의 상태를 저장할 queue<pair<int, int>> water, 다음 호수의 상태를 저장할 queue<pair<int, int>> tmpW, 현재 백조의 위치를 저장할 queue<pair<int, int>> swan, 마지막으로 다음 백조의 위치를 저장할 queue<pair<int, int>> tmpS를 선언합니다.

 

2. 호수를 입력받으면서 얼음이 아닌 좌표를 water에 push 하고, 백조 한 마리의 위치를 swan에 push 합니다.

 

3. 먼저 백조가 만날 수 있는지 bfs를 통해 움직이고, 벽에 마주칠 때마다 다음에 갈 수 있는 위치이므로 tmpS에 push 하고, 백조를 만난다면 Find 변수를 true로 갱신합니다.

 

4. 빙하가 녹으면서 현재 물에 맞닿아 있다면 tmpW에 push 해줍니다.

 

5. Find 변수가 true라면 ans를 출력해 주고, 그렇지 않다면 water = tmpW, swan = tmpS로 갱신해 주고, ans++를 해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int R, C;
int r, c;
char arr[1500][1501];
int visited[1500][1500];
int dr[] = { -1,1,0,0 };
int dc[] = { 0,0,-1,1 };
queue<pair<int, int>> swan, water, tmpW, tmpS;
bool Find = false;
 
void BFSwater()
{
    while (!water.empty()) {
        const int r = water.front().first;
        const int c = water.front().second;
        water.pop();
 
        for (int i = 0; i < 4; i++) {
            const int rr = r + dr[i];
            const int cc = c + dc[i];
 
            if (rr >= 0 && rr < R && cc >= 0 && cc < C) {
                if (arr[rr][cc] == 'X') {
                    tmpW.push({ rr,cc });
                    arr[rr][cc] = '.';
                }
            }
        }
    }
}
 
void BFSswan()
{
    while (!swan.empty() && Find == false) {
        const int r = swan.front().first;
        const int c = swan.front().second;
        swan.pop();
 
        for (int i = 0; i < 4; i++) {
            const int rr = r + dr[i];
            const int cc = c + dc[i];
 
            if (rr >= 0 && rr < R && cc >= 0 && cc < C && visited[rr][cc] == 0) {
                visited[rr][cc] = 1;
                if (arr[rr][cc] == '.') {
                    swan.push({ rr,cc });
                }
                else if (arr[rr][cc] == 'X') {
                    tmpS.push({ rr,cc });
                    arr[rr][cc] = '.';
                }
                else if (arr[rr][cc] == 'L') {
                    Find = true;
                    break;
                }
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> R >> C;
 
    
 
    for (int i = 0; i < R; i++) {
        cin >> arr[i];
        for (int j = 0; j < C; j++) {
            if (arr[i][j] != 'X') {
                water.push({ i,j });
            }
            if (arr[i][j] == 'L') {
                r = i;
                c = j;
            }
        }
    }
 
    swan.push({ r,c });
    visited[r][c] = 1;
 
    int ans = 0;
 
    while (1) {
        BFSswan();
        if (Find == true) {
            cout << ans;
            return 0;
        }
        BFSwater();
        ans++;
 
        water = tmpW;
        swan = tmpS;
 
        tmpW = queue<pair<int, int>>();
        tmpS = queue<pair<int, int>>();
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 20924번 - 트리의 기둥과 가지 (C++)  (0) 2023.09.26
[ 백준 ] 10835번 - 카드게임 (C++)  (0) 2023.09.25
[ 백준 ] 2015번 - 수들의 합 4 (C++)  (0) 2023.09.23
[ 백준 ] 13565번 - 침투 (C++)  (0) 2023.09.22
[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21
반응형

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

 

13565번: 침투

첫째 줄에는 격자의 크기를 나타내는  M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 격자를 입력받고, 격자의 y 좌표가 0인 좌표의 arr 값이 '0'이라면 queue에 넣고, visited 배열을 만들어 방문 여부를 저장합니다.

 

2. bfs를 이용하여 arr의 값이 '0'인 좌표로만 이동하면서 y 좌표의 값이 M이상인 경우가 있다면 YES를, 그렇지 않다면 NO를 출력합니다.

 

[ 소스코드 ]

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<queue>
 
using namespace std;
 
int M, N;
char arr[1000][1001];
int visited[1000][1000];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> M >> N;
 
    for (int i = 0; i < M; i++) {
        cin >> arr[i];
    }
 
    queue<pair<int, int>> q;
 
    for (int i = 0; i < N; i++) {
        if (arr[0][i] == '0') {
            q.push({ 0,i });
            visited[0][i] = 1;
        }
    }
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < M && xx >= 0 && xx < N) {
                if (visited[yy][xx] == 0 && arr[yy][xx] == '0') {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
            else if (yy == M) {
                cout << "YES";
                return 0;
            }
        }
    }
 
    cout << "NO";
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 3197번 - 백조의 호수 (C++)  (0) 2023.09.24
[ 백준 ] 2015번 - 수들의 합 4 (C++)  (0) 2023.09.23
[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21
[ 백준 ] 12016번 - 라운드 로빈 스케줄러 (C++)  (0) 2023.09.20
[ 백준 ] 17609번 - 회문 (C++)  (0) 2023.09.19
반응형

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

 

12761번: 돌다리

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 \(N\)번 돌 위에, 주미는 \(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. A, B, N, M을 입력받고, visited 배열을 만들어 방문 여부를 저장합니다.

 

2. bfs를 이용하여 8가지 경우의 수를 통해 이동하면서 cnt값을 올려주고, 현재 위치가 M이라면 cnt 값을 출력하고 종료합니다.

[ 소스코드 ]

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<iostream>
#include<queue>
 
using namespace std;
 
int A, B, N, M;
int visited[100001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> A >> B >> N >> M;
 
    queue<pair<int, int>>q;
    q.push({ N,0 });
 
    visited[N] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        if (cur == M) {
            cout << cnt;
            return 0;
        }
 
        if (cur < M) {
            if (cur + 1 <= 100000 && visited[cur + 1] == 0) {
                visited[cur + 1] = 1;
                q.push({ cur + 1,cnt + 1 });
            }
 
            if (cur + A <= 100000 && visited[cur + A] == 0) {
                visited[cur + A] = 1;
                q.push({ cur + A,cnt + 1 });
            }
 
            if (cur + B <= 100000 && visited[cur + B] == 0) {
                visited[cur + B] = 1;
                q.push({ cur + B,cnt + 1 });
            }
 
            if (cur * A <= 100000 && visited[cur * A] == 0) {
                visited[cur * A] = 1;
                q.push({ cur * A,cnt + 1 });
            }
 
            if (cur * B <= 100000 && visited[cur * B] == 0) {
                visited[cur * B] = 1;
                q.push({ cur * B,cnt + 1 });
            }
        }
 
        if (cur - 1 >= 0 && visited[cur - 1] == 0) {
            visited[cur - 1] = 1;
            q.push({ cur - 1,cnt + 1 });
        }
 
        if (cur - A >= 0 && visited[cur - A] == 0) {
            visited[cur - A] = 1;
            q.push({ cur - A,cnt + 1 });
        }
 
        if (cur - B >= 0 && visited[cur - B] == 0) {
            visited[cur - B] = 1;
            q.push({ cur - B,cnt + 1 });
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2015번 - 수들의 합 4 (C++)  (0) 2023.09.23
[ 백준 ] 13565번 - 침투 (C++)  (0) 2023.09.22
[ 백준 ] 12016번 - 라운드 로빈 스케줄러 (C++)  (0) 2023.09.20
[ 백준 ] 17609번 - 회문 (C++)  (0) 2023.09.19
[ 백준 ] 5569번 - 출근 경로 (C++)  (0) 2023.09.18
반응형

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

 

16940번: BFS 스페셜 저지

올바른 순서는 1, 2, 3, 4와  1, 3, 2, 4가 있다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받고, bfs를 돌면서 각 노드의 부모 노드와 깊이를 저장합니다.

 

2. 방문 순서를 입력 받으면서 해당 노드의 순서를 arr 배열에 저장하고, 바로 직전 노드를 temp 변수에 저장합니다.

 

3. 첫 방문 순서가 1이 아니라면 0을 출력합니다.

 

4. 직전 노드의 부모 노드와 현재 노드의 부모 노드의 순서를 비교하고, 진전 노드와 현재 노드의 깊이를 비교하여 직전 노드의 값들이 현재 노드보다 더 크다면 0을 출력하고, 그렇지 않다면 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
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N;
vector<int> list[100001];
int visited[100001];
int arr[100001];
int parent[100001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
 
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    queue<pair<int, int>> q;
 
    q.push({ 1,1 });
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        visited[cur] = cnt;
 
        for (auto next : list[cur]) {
            if (visited[next] == 0) {
                parent[next] = cur;
                visited[next] = cnt + 1;
                q.push({ next,cnt + 1 });
            }
        }
    }
 
    int temp = 0;
 
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        arr[num] = i;
 
        if ((i == 0 && num != 1) || arr[parent[num]] < arr[parent[temp]] || visited[num] < visited[temp]) {
            cout << 0;
            return 0;
        }
        
        temp = num;
    }
 
    cout << 1;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
반응형

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

 

11567번: 선진이의 겨울 왕국

첫 번째 테스트 케이스의 경우에는 (1,6) → (2,6) →  (3,6) →  (4,6) → (4,5) → (4,4) → (4,3) →  (4,2) → (4,1) → (3,1) → (2,1) → (2,2) →  (2,3) → (1,3) → (1,2) → (2,2) 의 순서로 가면 탈출이 가능하다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 빙판길을 입력받아 arr에 저장하고, visited 배열을 만들어 방문 여부를 저장합니다.

 

2. X가 있는 좌표는 미리 방문처리를 해줍니다.

 

3. bfs를 통해 이동을 하면서 r2, c2에 도착할 수 있고, 그때 해당 좌표의 visited의 값이 1이라면 YES를 출력하고, 그렇지 않다면 NO를 출력합니다.

 

[ 소스코드 ]

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>
#include<string>
 
using namespace std;
 
int n, m;
string arr[500];
int visited[500][500];
int r1, c1, r2, c2;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 'X') {
                visited[i][j] = 1;
            }
        }
    }
 
    cin >> r1 >> c1 >> r2 >> c2;
    r1--; r2--; c1--; c2--;
 
    queue<pair<int, int>> q;
 
    q.push({ r1,c1 });
    visited[r1][c1] = 1;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < n && xx >= 0 && xx < m) {
                if (visited[yy][xx] == 0) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
                else if (yy == r2 && xx == c2) {
                    cout << "YES";
                    return 0;
                }
            }
        }
    }
 
    cout << "NO";
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
반응형

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

 

3184번: 양

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, v와 o의 개수를 세어 ans에 저장해 줍니다.

 

2. 방문하지 않은 좌표들을 방문하면서, bfs를 돌려주고, 각 영역의 양과 늑대의 수를 세어주고, 늑대가 양보다 많다면 ans에서 양의 수를 빼주고, 그렇지 않다면 늑대의 수를 빼줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
int R, C;
string arr[250];
int visited[250][250];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
pair<int, int> ans;
 
void bfs(int y, int x)
{
    int v = 0, o = 0;
 
    queue<pair<int, int>> q;
 
    q.push({ y,x });
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        if (arr[y][x] == 'v') v++;
        else if (arr[y][x] == 'o') o++;
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < R && xx >= 0 && xx < C) {
                if (visited[yy][xx] == 0 && arr[yy][xx] != '#') {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    if (v >= o) {
        ans.first -= o;
    }
    else {
        ans.second -= v;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] == 'v') {
                ans.second++;
            }
            else if(arr[i][j] == 'o') {
                ans.first++;
            }
        }
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (visited[i][j] == 0 && arr[i][j] != '#') {
                visited[i][j] = 1;
                bfs(i, j);
            }
        }
    }
 
    cout << ans.first << ' ' << ans.second;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
반응형

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

 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, 아직 방문하지 않은 모든 좌표를 돌면서 bfs를 진행해줍니다.

 

2. bfs를 진행하면서 이어져 있는 땅들을 cnt로 바꿔주고, 바다와 만나는 점들을 queue에 넣어줍니다.

 

3. 한번더 bfs를 진행하면서 다른 육지와 이어졌을 때의 d 중 최솟값을 ans에 저장합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {
    int y, x, d;
};
 
int N;
int arr[100][100];
int visited[100][100];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int cnt;
int ans = 987654321;
 
void bfs(int y, int x)
{
    int v[100][100] = { 0 };
    queue<pair<int, int>> q;
    queue<node> qq;
 
    q.push({ y,x });
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        arr[y][x] = cnt;
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (arr[yy][xx] == 1 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
                else if (arr[yy][xx] == 0 && v[y][x] != 1) {
                    v[y][x] = 1;
                    qq.push({ y,x,0 });
                }
            }
        }
    }
 
    while (!qq.empty()) {
        const int y = qq.front().y;
        const int x = qq.front().x;
        const int d = qq.front().d;
        qq.pop();
 
        if (d >= ans) return;
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (arr[yy][xx] == 0 && v[yy][xx] == 0) {
                    v[yy][xx] = 1;
                    qq.push({ yy,xx,d + 1 });
                }
                else if (arr[yy][xx] != 0 && arr[yy][xx] != cnt) {
                    ans = min(ans, d);
                    return;
                }
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 1 && visited[i][j] == 0) {
                visited[i][j] = 1;
                cnt--;
                bfs(i, j);
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
반응형

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

 

7299번: Food Cubes

The spacemen in the space shuttle are waiting for the next escape window to return to the mother land Earth, where they are expected to fall somewhere in the deep blue waters of the Persian Gulf. Bored of waiting with nothing to do, they decide to play a g

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 좌표를 입력받아 해당 좌표의 값을 arr 배열에 1로 저장하고, visited 배열을 선언하여 방문여부를 체크합니다.

 

2. 모든 좌표를 돌면서 방문하지 않은 좌표에서 bfs를 이용하여 주변에 음식이 있는지 체크하고, 좌표 범위를 벗어나면 ret를 false로 갱신합니다. 

 

3. true일 때 ans++를 해주고, ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
struct node {
    int x, y, z;
};
 
int T, M;
int arr[101][101][101];
int visited[101][101][101];
int dx[] = { -1,1,0,0,0,0 };
int dy[] = { 0,0,-1,1,0,0 };
int dz[] = { 0,0,0,0,-1,1 };
 
bool bfs(int x, int y, int z)
{
    bool ret = true;
 
    queue<node> q;
    q.push({ x,y,z });
 
    while (!q.empty()) {
        const int x = q.front().x;
        const int y = q.front().y;
        const int z = q.front().z;
        q.pop();
 
        for (int i = 0; i < 6; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            int zz = z + dz[i];
 
            if (xx >= 1 && xx <= 100 && yy >= 1 && yy <= 100 && zz >= 1 && zz <= 100) {
                if (visited[xx][yy][zz] == 0 && arr[xx][yy][zz] == 0) {
                    visited[xx][yy][zz] = 1;
                    q.push({ xx,yy,zz });
                }
            }
            else {
                ret = false;
            }
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> M;
 
        for (int i = 1; i <= 100; i++) {
            for (int j = 1; j <= 100; j++) {
                for (int k = 1; k <= 100; k++) {
                    visited[i][j][k] = 0;
                    arr[i][j][k] = 0;
                }
            }
        }
 
        for (int i = 0; i < M; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            arr[x][y][z] = 1;
        }
 
        int ans = 0;
 
        for (int i = 1; i <= 100; i++) {
            for (int j = 1; j <= 100; j++) {
                for (int k = 1; k <= 100; k++) {
                    if (arr[i][j][k] == 0 && visited[i][j][k] == 0) {
                        visited[i][j][k] = 1;
                        if (bfs(i, j, k)) ans++;
                    }
                }
            }
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
반응형

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

 

6067번: Guarding the Farm

There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받아 arr 배열에 저장하고, visited 배열을 선언하여 방문여부를 체크합니다.

 

2. 모든 좌표를 돌면서 방문하지 않은 좌표에서 bfs를 이용하여 주변에 더 높은 지형이 있는지 체크하고 더 높은 지형이 없다면 true를 아니라면 false를 return 합니다.

 

3. true일 때 ans++를 해주고, ans를 출력합니다.

 

[ 소스코드 ]

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<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[700][700];
int visited[700][700];
int dy[] = { -1,-1,0,1,1,1,0,-1 };
int dx[] = { 0,1,1,1,0,-1,-1,-1 };
 
bool bfs(int y, int x)
{
    queue<pair<int, int>> q;
 
    q.push({ y,x });
 
    bool ret = true;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (visited[yy][xx] != 1 && arr[yy][xx] == arr[y][x]) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
                else if (arr[yy][xx] > arr[y][x]) {
                    ret = false;
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] != 1) {
                visited[i][j] = 1;
                if (bfs(i, j)) {
                    ans++;
                }
            }
        }
    }
 
    cout << ans;
}
cs

 

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

'백준' 카테고리의 다른 글

[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28

+ Recent posts

티스토리툴바