반응형

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

 

12869번: 뮤탈리스크

1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. SCV[ 61 ][ 61 ][ 61 ] 배열을 만들어 각각의 SCV의 체력에 따라 최소의 공격 횟수를 저장합니다.

 

2. bfs를 통해 각각의 공격에 따라 최소의 공격 횟수를 저장합니다.

 

3. SCV[ 0 ][ 0 ][ 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N;
int SCV[61][61][61];
int hp[3];
 
struct node {
    int scv[3];
    int cnt;
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> hp[i];
    }
 
    queue<node> q;
 
    SCV[hp[0]][hp[1]][hp[2]] = 0;
    q.push({ {hp[0],hp[1],hp[2]}, 0 });
 
    while (!q.empty()) {
        int scv1 = q.front().scv[0];
        int scv2 = q.front().scv[1];
        int scv3 = q.front().scv[2];
        const int cnt = q.front().cnt;
        q.pop();
 
        if (scv1 < 0) scv1 = 0;
        if (scv2 < 0) scv2 = 0;
        if (scv3 < 0) scv3 = 0;
        if (SCV[scv1][scv2][scv3] == 0) SCV[scv1][scv2][scv3] = 987654321;
        if (SCV[scv1][scv2][scv3] <= cnt) continue;
        SCV[scv1][scv2][scv3] = cnt;
 
        q.push({ {scv1 - 9,scv2 - 3,scv3 - 1}, cnt + 1 });
        q.push({ {scv1 - 9,scv2 - 1,scv3 - 3}, cnt + 1 });
        q.push({ {scv1 - 1,scv2 - 3,scv3 - 9}, cnt + 1 });
        q.push({ {scv1 - 3,scv2 - 1,scv3 - 9}, cnt + 1 });
        q.push({ {scv1 - 3,scv2 - 9,scv3 - 1}, cnt + 1 });
        q.push({ {scv1 - 1,scv2 - 9,scv3 - 3}, cnt + 1 });
    }
 
    cout << SCV[0][0][0];
 
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 8981번 - 입력숫자 (C++)  (0) 2023.06.30
[ 백준 ] 1863번 - 스카이라인 쉬운거 (C++)  (0) 2023.06.29
[ 백준 ] 1707번 - 이분 그래프 (C++)  (0) 2023.06.27
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
[ 백준 ] 5052번 - 전화번호 목록 (C++)  (0) 2023.06.25
반응형

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

 

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 인접한 노드끼리 같은 집합에 속해있는지 체크합니다.

 

2. dfs를 통해 모든 노드를 탐색하며 인접한 노드끼리 같은 집합에 속해있다면 false를 return 합니다.

 

3. 이분 그래프라면 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<vector>
 
using namespace std;
 
int K, V, E;
vector<int> list[20001];
int visited[20001];
 
bool dfs(int cur, int stat)
{
    for (auto& next : list[cur]) {
        if (visited[next] == 0) {
            visited[next] = -stat;
            dfs(next, -stat);
        }
        else if (visited[next] == stat) {
            return false;
        }
    }
 
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> K;
 
    while (K--) {
        cin >> V >> E;
        bool flag = true;
 
        for (int i = 1; i <= V; i++) {
            list[i].clear();
            visited[i] = 0;
        }
 
        for (int i = 0; i < E; i++) {
            int u, v;
            cin >> u >> v;
            list[u].push_back(v);
            list[v].push_back(u);
        }
 
        for (int i = 1; i <= V; i++) {
            if (visited[i] == 0) visited[i] = 1;
            if (!dfs(i, visited[i])) {
                printf("NO\n");
                flag = false;
                break;
            }
        }
 
        if (flag) {
            printf("YES\n");
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1863번 - 스카이라인 쉬운거 (C++)  (0) 2023.06.29
[ 백준 ] 12869번 - 뮤탈리스크 (C++)  (0) 2023.06.28
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
[ 백준 ] 5052번 - 전화번호 목록 (C++)  (0) 2023.06.25
[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
반응형

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

 

17071번: 숨바꼭질 5

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. pair<int,int> visited 배열을 만들어 각각 짝수번째 가장 일찍 도착하는 시간과 홀수번째 가장 일찍 도착하는 시간을 저장합니다.

 

2. K에 시간마다 i초씩 더해주면서 visited[ K + i ] % 2 == i % 2일 때 i의 최솟값을 Min에 저장합니다.

 

3. Min의 값이 987654321이 아니라면 Min을 출력하고, 그렇지 않다면 -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
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 N, K;
pair<int,int> visited[500001];
 
int main()
{
    scanf("%d %d", &N, &K);
 
    if (N == K) {
        printf("0");
        return 0;
    }
 
    queue<pair<int, int>> q;
 
    q.push({ N,0 });
    for (int i = 0; i <= 500000; i++) {
        visited[i].first = 987654321;
        visited[i].second = 987654321;
    }
    visited[N].first = 0;
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        if (cnt % 2 == 0) {
            if (visited[cur].first < cnt) continue;
            visited[cur].first = cnt;
 
            if (cur > 0) {
                if (visited[cur - 1].second > cnt + 1) {
                    visited[cur - 1].second = cnt + 1;
                    q.push({ cur - 1,cnt + 1 });
                }
            }
            if (cur < 500000) {
                if (visited[cur + 1].second > cnt + 1) {
                    visited[cur + 1].second = cnt + 1;
                    q.push({ cur + 1,cnt + 1 });
                }
            }
            if (cur <= 250000) {
                if (visited[cur * 2].second > cnt + 1) {
                    visited[cur * 2].second = cnt + 1;
                    q.push({ cur * 2,cnt + 1 });
                }
            }
        }
        else {
            if (visited[cur].second < cnt) continue;
            visited[cur].second = cnt;
 
            if (cur > 0) {
                if (visited[cur - 1].first > cnt + 1) {
                    visited[cur - 1].first = cnt + 1;
                    q.push({ cur - 1,cnt + 1 });
                }
            }
            if (cur < 500000) {
                if (visited[cur + 1].first > cnt + 1) {
                    visited[cur + 1].first = cnt + 1;
                    q.push({ cur + 1,cnt + 1 });
                }
            }
            if (cur <= 250000) {
                if (visited[cur * 2].first > cnt + 1) {
                    visited[cur * 2].first = cnt + 1;
                    q.push({ cur * 2,cnt + 1 });
                }
            }
        }
 
        
    }
 
    int cnt = 1;
    int Min = 987654321;
    K++;
 
    while (K <= 500000) {
        if (visited[K].first != 987654321) {
            if (cnt % 2 == visited[K].first % 2 && cnt >= visited[K].first) {
                Min = min(Min, cnt);
            }
        }
        if (visited[K].second != 987654321) {
            if (cnt % 2 == visited[K].second % 2 && cnt >= visited[K].second) {
                Min = min(Min, cnt);
            }
        }
 
        cnt++;
        K += cnt;
    }
 
    if (Min != 987654321) {
        printf("%d", Min);
    }
    else {
        printf("-1");
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22
[ 백준 ] 2830번 - 행성 X3 (C++)  (0) 2023.06.20
[ 백준 ] 5022번 - 연결 (C++)  (1) 2023.06.19
[ 백준 ] 2669번 - 직사각형 네개의 합집합의 면적 구하기 (C++)  (0) 2023.06.18
반응형

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

 

5022번: 연결

A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최솟값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 전선이 이어져 있는 지를 체크합니다.

 

2. bfs를 활용하여 B점 두 개를 방문처리 해준 뒤 A점끼리 전선으로 먼저 이어주고, 경로를 저장하여 방문 처리 해주고, B점끼리 이어 두 전선의 길이와 최솟값을 비교하여 Min에 저장해 줍니다.

 

3. bfs를 활용하여 A점 두 개를 방문처리 해준 뒤 ㅠ점끼리 전선으로 먼저 이어주고, 경로를 저장하여 방문 처리 해주고, A점끼리 이어 두 전선의 길이와 최솟값을 비교하여 Min에 저장해 줍니다.

 

4. Min 값이 987654321이라면 IMPOSSIBLE을 출력하고, 그렇지 않다면 Min값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
struct node {
    int y;
    int x;
    int cnt;
    vector<pair<int, int>> route;
};
 
int N, M;
int A1x, A1y, A2x, A2y, B1x, B1y, B2x, B2y;
int visited[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int Min = 987654321;
 
int bfs(int y1, int x1, int y2, int x2)
{
    queue<node> q;
    vector<pair<int, int>> temp;
    q.push({ y1,x1,0,temp });
    visited[y1][x1] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int cnt = q.front().cnt;
        vector<pair<int, int>> temp = q.front().route;
        temp.push_back({ y,x });
        q.pop();
 
        if (y == y2 && x == x2) {
            for (int i = 0; i <= M; i++) {
                for (int j = 0; j <= N; j++) {
                    visited[i][j] = 0;
                }
            }
 
            for (auto& next : temp) {
                int yyy = next.first;
                int xxx = next.second;
                visited[yyy][xxx] = 1;
            }
            return cnt;
        }
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
 
            if (yy >= 0 && yy <= M && xx >= 0 && xx <= N) {
                if (visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx,cnt + 1,temp });
                }
            }
        }
    }
 
    return -1;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    scanf("%d %d %d %d %d %d %d %d", &A1x, &A1y, &A2x, &A2y, &B1x, &B1y, &B2x, &B2y);
 
    visited[B1y][B1x] = 1;
    visited[B2y][B2x] = 1;
    int route1 = bfs(A1y, A1x, A2y, A2x);
    int route2 = bfs(B1y, B1x, B2y, B2x);
 
    if (route2 != -1) {
        Min = min(Min, route1 + route2);
    }
 
    for (int i = 0; i <= M; i++) {
        for (int j = 0; j <= N; j++) {
            visited[i][j] = 0;
        }
    }
 
    visited[A1y][A1x] = 1;
    visited[A2y][A2x] = 1;
    route1 = bfs(B1y, B1x, B2y, B2x);
    route2 = bfs(A1y, A1x, A2y, A2x);
 
    if (route2 != -1) {
        Min = min(Min, route1 + route2);
    }
 
    if (Min != 987654321) {
        printf("%d", Min);
    }
    else {
        printf("IMPOSSIBLE");
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17071번 - 숨바꼭질 5 (C++)  (0) 2023.06.21
[ 백준 ] 2830번 - 행성 X3 (C++)  (0) 2023.06.20
[ 백준 ] 2669번 - 직사각형 네개의 합집합의 면적 구하기 (C++)  (0) 2023.06.18
[ 백준 ] 2164번 - 카드2 (C++)  (0) 2023.06.17
[ 백준 ] 14497번 - 주난의 난(難) (C++)  (0) 2023.06.16
반응형

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

 

12919번: A와 B 2

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. unordered_map을 활용하여 문자열의 방문 여부를 저장합니다.

 

2. T문자열부터 시작하여 맨 뒤 문자가 'A'일 때와 맨 앞 문자가 'B'일 때 두 상황에서 각각 처리한 뒤 queue에 넣어주면서 S문자열과 같아지면 1을 출력하고 프로그램을 종료시킵니다.

 

3.  S문자열을 만들 수 없다면 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
#include<iostream>
#include<string>
#include<queue>
#include<unordered_map>
 
using namespace std;
 
string S, T;
unordered_map<string, int> visited;
 
string change(string S)
{
    string temp;
 
    for (int i = S.size()-1; i >= 0; i--) {
        temp += S[i];
    }
 
    return temp;
}
 
int main()
{
    cin >> S >> T;
 
    queue<string> q;
 
    q.push(T);
    visited[T] = 1;
 
    while (!q.empty()) {
        string A = q.front();
        q.pop();
 
        if (A == S) {
            printf("1");
            return 0;
        }
        if (A.size() == S.size()) continue;
 
        string temp = A;
        if (temp[temp.size() - 1] == 'A') {
            temp.erase(temp.end() - 1);
            if (visited[temp] != 1) {
                visited[temp] = 1;
                q.push(temp);
            }
        }
 
        temp = A;
 
        if (temp[0] == 'B') {
            temp = change(temp);
            temp.erase(temp.end() - 1);
            if (visited[temp] != 1) {
                visited[temp] = 1;
                q.push(temp);
            }
        }
    }
 
    printf("0");
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 7490번 - 0 만들기 (C++)  (0) 2023.06.14
[ 백준 ] 20437번 - 문자열 게임 2 (C++)  (0) 2023.06.13
[ 백준 ] 14463번 - 소가 길을 건너간 이유 9 (C++)  (0) 2023.06.11
[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
반응형

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

 

2310번: 어드벤처 게임

입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited[ n ][ 501 ] 배열을 만들어 얼마의 소지금을 들고 해당 노드를 방문했는지 기록합니다.

 

2. vector<int> list[1001]을 이용하여 해당 노드에서 갈 수 있는 노드들을 저장합니다.

 

3. bfs를 활용하여 queue에 넣어가면서 방을 이동하고, n번 방에 도착할 수 있으면 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
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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int n;
char room[1001];
int charge[1001];
vector<int> list[1001];
int visited[1001][501];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    list[0].push_back(1);
 
    while (1) {
        cin >> n;
        if (n == 0) return 0;
 
        for (int i = 1; i <= n; i++) {
            list[i].clear();
            fill(visited[i], visited[i] + 501, 0);
            cin >> room[i] >> charge[i];
            int next;
            while (1) {
                cin >> next;
                if (next == 0) break;
                list[i].push_back(next);
            }
        }
 
        queue<pair<int, int>> q;
 
        q.push({ 0, 0 });
 
        bool flag = false;
 
        while (!q.empty()) {
            const int cur = q.front().first;
            const int cost = q.front().second;
            q.pop();
 
            if (cur == n) {
                cout << "Yes\n";
                flag = true;
                break;
            }
 
            for (int& next : list[cur]) {
                if (room[next] == 'T') {
                    if (cost >= charge[next]) {
                        if (visited[next][cost] != 1) {
                            visited[next][cost] = 1;
                            q.push({ next,cost - charge[next] });
                        }
                    }
                }
                else if (room[next] == 'L') {
                    if (cost < charge[next]) {
                        if (visited[next][charge[next]] != 1) {
                            visited[next][charge[next]] = 1;
                            q.push({ next,charge[next] });
                        }
                    }
                    else {
                        if (visited[next][cost] != 1) {
                            visited[next][cost] = 1;
                            q.push({ next,cost });
                        }
                    }
                }
                else {
                    if (visited[next][cost] != 1) {
                        visited[next][cost] = 1;
                        q.push({ next,cost });
                    }
                }
            }
        }
 
        if (flag == false) {
            cout << "No\n";
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
[ 백준 ] 9879번 - Cross Country Skiing (C++)  (0) 2023.05.16
[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12
반응형

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 섬을 입력받습니다.

 

2. 2중 for문을 통해 그림을 탐색하면서 1이면 bfs를 통해 이어진 섬을 모두 0으로 바꿔주고, cnt에 1을 더해줍니다.

 

3. 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int arr[50][50];
int dy[8] = { 0,0,-1,1,-1,-1,1,1 };
int dx[8] = { -1,1,0,0,-1,1,1,-1 };
int w, h;
 
void bfs(int y, int x)
{
    queue<pair<int, int>> q;
    q.push({ y,x });
    arr[y][x] = 0;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
 
            if (yy >= 0 && yy < h && xx >= 0 && xx < w) {
                if (arr[yy][xx] == 1) {
                    arr[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    while (1) {
        scanf("%d %d", &w, &h);
 
        if (w == 0 && h == 0) return 0;
 
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
 
        int cnt = 0;
 
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (arr[i][j] == 1) {
                    bfs(i, j);
                    cnt++;
                }
            }
        }
 
        printf("%d\n", cnt);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
반응형

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

 

1926번: 그림

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그림을 입력받습니다.

 

2. 2중 for문을 통해 그림을 탐색하면서 1이면 bfs를 통해 그림의 크기 중 가장 큰 그림을 ans에 저장하고, cnt++를 해줍니다.

 

3. cnt와 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int bfs(int y, int x)
{
    int ret = 1;
 
    queue<pair<int, int>> q;
 
    q.push({ y,x });
    arr[y][x] = 0;
 
    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 (arr[yy][xx] == 1) {
                    arr[yy][xx] = 0;
                    q.push({ yy,xx });
                    ret++;
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    int ans = 0;
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 1) {
                ans = max(ans,bfs(i, j));
                cnt++;
            }
        }
    }
 
    printf("%d\n%d", cnt, ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
반응형

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

 

2660번: 회장뽑기

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/24

 

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk

rudalsd.tistory.com

 

1. arr[ n ][ n ] 배열을 만들어서 서로 친구관계라면 1로 초기화합니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 각 회원끼리 몇 단계를 거쳐야 친구가 되는지 저장합니다.

 

3. 1번 회원부터 N번 회원까지 각 회원들의 가장 먼 친구관계를 저장합니다.

 

4. 그 중 가장 가까운 친구관계가 몇 단계인지 min에 저장하고, 그 후보들을 ans에 push 합니다.

 

5. min과 ans.size를 출력하고, 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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
int arr[51][51];
int point[51];
vector<int> ans;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i != j) {
                arr[i][j] = 9999;
            }
        }
    }
 
    while (1) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (a == -1 && b == -1) break;
 
        arr[a][b] = 1;
        arr[b][a] = 1;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (arr[j][k] > arr[j][i] + arr[i][k]) {
                    arr[j][k] = arr[j][i] + arr[i][k];
                }
            }
        }
    }
 
    int min = 9999;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            point[i] = max(point[i], arr[i][j]);
        }
 
        if (min > point[i]) {
            min = point[i];
            ans.clear();
            ans.push_back(i);
        }
        else if (min == point[i]) {
            ans.push_back(i);
        }
    }
 
    printf("%d %d\n", min, (int)ans.size());
 
    for (int next : ans) {
        printf("%d ", next);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17396번 - 백도어 (C++)  (0) 2023.03.02
[ 백준 ] 3066번 - 브리징 시그널 (C++)  (0) 2023.03.01
[ 백준 ] 2617번 - 구슬 찾기 (C++)  (0) 2023.02.27
[ 백준 ] 18235번 - 지금 만나러 갑니다 (C++)  (0) 2023.02.26
[ 백준 ] 18405번 - 경쟁적 전염 (C++)  (0) 2023.02.25
반응형

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

 

18235번: 지금 만나러 갑니다

첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. A와 B를 입력받고, queue에 넣습니다.

 

2. arr 배열을 만들어서 오리와 육리가 몇 번째 해당 좌표로 갔는지 기록해 줍니다.

 

3. 오리가 먼저 움직이고 육리가 움직였을 때, 같은 좌표에 있다면 이동 횟수를 출력하고, 같은 좌표에서 만날 수 없다면 -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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, A, B;
int arr[500001];
 
int main()
{
    scanf("%d %d %d", &N, &A, &B);
    fill(arr, arr + N + 1, -1);
 
    queue<pair<int, int>> q;
 
    q.push({ A,0 });
    q.push({ B,0 });
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        if (arr[cur] == cnt) {
            printf("%d", cnt);
            return 0;
        }
 
        arr[cur] = cnt;
 
        const int next = 1 << cnt;
 
        if (cur - next > 0) {
            q.push({ cur - next, cnt + 1 });
        }
        if (cur + next <= N) {
            q.push({ cur + next, cnt + 1 });
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2660번 - 회장뽑기 (C++)  (0) 2023.02.28
[ 백준 ] 2617번 - 구슬 찾기 (C++)  (0) 2023.02.27
[ 백준 ] 18405번 - 경쟁적 전염 (C++)  (0) 2023.02.25
[ 백준 ] 1613번 - 역사 (C++)  (0) 2023.02.24
[ 백준 ] 1162번 - 도로포장 (C++)  (0) 2023.02.23

+ Recent posts

티스토리툴바