반응형

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

 

20010번: 악덕 영주 혜유

FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. node struct를 만들어서 arr 배열에 a, b, c를 각각 저장합니다.

 

2. c를 기준으로 arr배열을 오름차순으로 정렬합니다.

 

3. Union-Find를 이용하여 마을들을 연결하고, 열결이 될 때마다 ans에 c를 더해줍니다.

 

4. 또한, 연결이 될 때마다 연결이 된 교역로만으로 그래프를 다시 만듭니다.

 

5. 새로 만든 그래프를 이용하여 한 마을에서 가장 먼 마을을 구하고, 다시 그 마을로부터 가장 먼 마을까지의 거리를 따로 저장합니다.

 

6. 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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int a;
    int b;
    int c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int N, K;
node arr[1000000];
int vect[1000];
vector<pair<int,int>> list[1000];
int visited[1000];
int Max;
int start;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
void dfs(int n, int cost)
{
    if (cost > Max) {
        Max = cost;
        start = n;
    }
 
    for (auto& next : list[n]) {
        if (visited[next.first] != 1) {
            visited[next.first] = 1;
            dfs(next.first, cost + next.second);
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 1; i < N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < K; i++) {
        scanf("%d %d %d", &arr[i].a, &arr[i].b, &arr[i].c);
    }
 
    sort(arr, arr + K, cmp);
 
    int ans = 0;
 
    for (int i = 0; i < K; i++) {
        const int a = arr[i].a;
        const int b = arr[i].b;
        const int c = arr[i].c;
 
        if (Find(a) != Find(b)) {
            list[a].push_back({ b,c });
            list[b].push_back({ a,c });
            Union(a, b);
            ans += c;
        }
    }
 
    visited[0] = 1;
    dfs(0, 0);
 
    Max = 0;
    fill(visited, visited + N, 0);
 
    visited[start] = 1;
    dfs(start, 0);
 
    printf("%d\n%d", ans, Max);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2056번 - 작업 (C++)  (0) 2023.02.20
[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19
[ 백준 ] 1944번 - 복제 로봇 (C++)  (0) 2023.02.17
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 1937번 - 욕심쟁이 판다 (C++)  (0) 2023.02.15
반응형

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

 

1937번: 욕심쟁이 판다

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 대나무 숲을 저장할  arr 배열과, 메모이제이션을 위한 dp 배열을 만듭니다.

 

2. dp[ i ][ j ]에는 i, j 좌표에서 시작했을 때 가장 많이 이동할 수 있는 칸의 수를 저장합니다.

 

3. 따라서, 한번 저장한 좌표에는 다시 갈 필요가 없으므로 dp[ i ][ j ] != 0일 때 dp[ i ][ j ]를 return 합니다.

 

4. 그렇지 않다면 arr[ yy ][ xx ] > arr[ y ][ x ] 일 때, dp[ y ][ x ] = max(dp[ y ][ x ], dfs(yy, xx) + 1)의 점화식을 이용하여 각 좌표의 최댓값을 저장해 줍니다.

 

5. 모든 좌표를 2중 for문을 이용해 돌며 dfs를 실행하고, 그중 최댓값을 ans에 저장합니다.

 

6. 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
#include<iostream>
 
using namespace std;
 
int n;
int arr[500][500];
int dp[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int ans;
 
int dfs(int y, int x)
{
    int& ret = dp[y][x];
    if (ret != 0) return ret;
    ret = 1;
    
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
 
        if (yy >= 0 && yy < n && xx >= 0 && xx < n) {
            if (arr[yy][xx] > arr[y][x]) {
                ret = max(ret, dfs(yy, xx) + 1);
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans,dfs(i, j));
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1944번 - 복제 로봇 (C++)  (0) 2023.02.17
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 7570번 - 줄 세우기 (C++)  (0) 2023.02.14
[ 백준 ] 11085번 - 군사 이동 (C++)  (0) 2023.02.13
[ 백준 ] 2565번 - 전깃줄 (C++)  (0) 2023.02.12
반응형

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

 

15971번: 두 로봇

입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 방문을 기록해 줍니다.

 

2. 그래프를 입력받고, bfs를 이용하여 시작점부터 끝점까지 이동 거리를 구해줍니다.

 

3. 위의 과정에서 지나갔던 통로 중 가장 긴 통로를 이동 거리에서 빼줍니다.

 

4. 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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {
    int cur;
    int cost;
    int max;
};
 
int N, s, e;
vector<pair<int, int>> list[100001];
int visited[100001];
 
int main()
{
    scanf("%d %d %d", &N, &s, &e);
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    queue<node> q;
    q.push({ s,0,0 });
    visited[s] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int cost = q.front().cost;
        const int Max = q.front().max;
        q.pop();
 
        if (cur == e) {
            printf("%d", cost - Max);
            return 0;
        }
 
        for (auto& next : list[cur]) {
            if (visited[next.first] != 1) {
                visited[next.first] = 1;
                q.push({ next.first, cost + next.second, max(Max, next.second) });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2565번 - 전깃줄 (C++)  (0) 2023.02.12
[ 백준 ] 17836번 - 공주님을 구해라! (C++)  (0) 2023.02.11
[ 백준 ] 2637번 - 장난감 조립 (C++)  (0) 2023.02.09
[ 백준 ] 11658번 - 구간 합 구하기 3 (C++)  (0) 2023.02.08
[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
반응형

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

 

17090번: 미로 탈출하기

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ 501 ][ 501 ] 배열을 만들어서 -1로 초기화합니다.

 

2. dfs를 통해 해당 좌표에 방문 시 visited배열이 -1이 아니라면 그 값을  return 합니다.

 

3. visited 배열을 0으로 초기화시키고, 지도에 적힌 문자대로 이동합니다.

 

4. 이동했을 때 지도 밖으로 나간다면 1을 return 하고, 그렇지 않다면 다시 재귀해 줍니다.

 

5. visited 배열에서 값이 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
#include<iostream>
#include<cstring>
 
using namespace std;
 
int N, M;
char arr[501][501];
int visited[505][505];
 
int dfs(int r, int c)
{
    if (visited[r][c] != -1) return visited[r][c];
    visited[r][c] = 0;
 
    if (arr[r][c] == 'U') {
        if (r == 0) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r - 1, c);
    }
    else if (arr[r][c] == 'R') {
        if (c == M-1) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r, c + 1);
    }
    else if (arr[r][c] == 'D') {
        if (r == N - 1) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r + 1, c);
    }
    else {
        if (c == 0) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r, c - 1);
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
    memset(visited, -1, sizeof(visited));
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] == -1) {
                if (dfs(i, j)) ans++;
            }
            else if (visited[i][j] == 1) ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13418번 - 학교 탐방하기 (C++)  (0) 2023.01.29
[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
[ 백준 ] 14923번 - 미로 탈출 (C++)  (0) 2023.01.26
[ 백준 ] 5558번 - チーズ (Cheese) (C++)  (0) 2023.01.25
[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
반응형

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

 

14466번: 소가 길을 건너간 이유 6

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. road[ r + r` ][ c + c` ] 배열을 만들어 길의 위치를 저장합니다.

 

2. cow 배열을 만들어 소들의 위치를 저장합니다.

 

3. for문을 통해 cow 배열을 돌면서 bfs를 이용하여 몇마리의 소를 만날 수 있는지 ans에 저장합니다.

 

4. ans는 만날 수 있는 모든 경우이므로 겹치는 경우를 빼기 위해 2로 나눈 후, 나올 수 있는 모든 쌍에서 ans/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
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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, K, R;
int road[205][205];
int arr[101][101];
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
vector<pair<int, int>> cow;
 
int bfs(int num)
{
    int ret = 0;
    int visited[101][101] = { 0 };
    queue<pair<int, int>> q;
    q.push({ cow[num].first, cow[num].second });
 
    while (!q.empty()) {
        const int r = q.front().first;
        const int c = q.front().second;
        q.pop();
 
        if (visited[r][c] == 1) continue;
        visited[r][c] = 1;
 
        if (arr[r][c] == 1) {
            ret++;
        }
 
        for (int i = 0; i < 4; i++) {
            const int rr = r + dr[i];
            const int cc = c + dc[i];
 
            if (rr > 0 && rr <= N && cc > 0 && cc <= N) {
                if (road[r + rr][c + cc] != 1) {
                    q.push({ rr,cc });
                }
            }
        }
    }
 
    return ret - 1;
}
 
int main()
{
    scanf("%d %d %d", &N, &K, &R);
 
    for (int i = 0; i < R; i++) {
        int r, c, rr, cc;
        scanf("%d %d %d %d", &r, &c, &rr, &cc);
 
        road[r + rr][c + cc] = 1;    //길의 위치
    }
 
    for (int i = 0; i < K; i++) {
        int r, c;
        scanf("%d %d", &r, &c);
 
        arr[r][c] = 1;
        cow.emplace_back(r, c);
    }
 
    int pair = (K) * (K - 1) / 2;    //나올 수 있는 모든 쌍
 
    int ans = 0;    //길 없이 만날 수 있는 모든 쌍의 수
 
    for (int i = 0; i < cow.size(); i++) {
        ans += bfs(i);
    }
 
    printf("%d", pair - ans / 2);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 4179번 - 불! (C++)  (0) 2022.12.04
[ 백준 ] 10159번 - 저울 (C++)  (0) 2022.12.03
[ 백준 ] 1039번 - 교환 (C++)  (0) 2022.12.01
[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++)  (0) 2022.11.30
[ 백준 ] 11967번 - 불켜기 (C++)  (0) 2022.11.29
반응형

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

 

15681번: 트리와 쿼리

트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 루트를 기준으로 재귀 함수를 통해 자식 노드들의 개수를 dp 배열에 저장합니다.

 

2. 점화식은 dp[ cur ] += dp[ next ] 입니다.

 

3. return을 할 때 자기 자신도 포함시켜야 하기 때문에 return dp[ cur ] += 1 을 해줍니다.

 

3. 마지막에 dp[num]을 하나씩 출력해주면 됩니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, R, Q;
vector<int> list[100001];
int dp[100001];
int visited[100001];
 
int dfs(int cur)
{
    if (dp[cur] != 0) return dp[cur];
    if (visited[cur] == 1) return 0;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next] != 1) {
            dp[cur] += dfs(next);
        }
    }
 
    return dp[cur] += 1;
}
 
int main()
{
    scanf("%d %d %d", &N, &R, &Q);
 
    for (int i = 1; i < N; i++) {
        int U, V;
        scanf("%d %d", &U, &V);
        list[U].push_back(V);
        list[V].push_back(U);
    }
 
    dfs(R);
 
    for (int i = 0; i < Q; i++) {
        int num;
        scanf("%d", &num);
        printf("%d\n", dp[num]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16933번 - 벽 부수고 이동하기 3 (C++)  (0) 2022.11.16
[ 백준 ] 11758번 - CCW (C++)  (0) 2022.11.15
[ 백준 ] 7682번 - 틱택토 (C++)  (0) 2022.11.13
[ 백준 ] 13913번 - 숨바꼭질 4 (C++)  (0) 2022.11.12
[ 백준 ] 1976번 - 여행 가자 (C++)  (0) 2022.11.11
반응형

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

 

7682번: 틱택토

틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 백트래킹을 이용하여 가능한 모든 경우의 수를 map에 저장합니다.

 

2. 결과를 입력받고 map에 있는지 체크한 후 있다면 valid, 없다면 invalid를 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
#include<cstring>
#include<unordered_map>
 
using namespace std;
 
char tik[10];
char temp[10] = ".........";
unordered_map<string, bool> m;
 
void dfs(int level) 
{
    if (level == 9) {
        m[temp] = true;    //승부가 나지 않았을 때
        return;
    }
 
    for (int i = 0; i < 3; i++) {
        if (temp[i * 3] == temp[i * 3 + 1] && temp[i * 3 + 1] == temp[i * 3 + 2]&&temp[i*3] != '.') {    //가로
            m[temp] = true;
            return;
        }
        if (temp[i] == temp[i + 3] && temp[i + 3] == temp[i + 6]&&temp[i] != '.') {    //세로
            m[temp] = true;
            return;
        }
    }
    if (((temp[0] == temp[4] && temp[4] == temp[8]) || (temp[2] == temp[4] && temp[4] == temp[6])) && temp[4] != '.') {    //대각
        m[temp] = true;
        return;
    }
 
    for (int i = 0; i < 9; i++) {
        if (temp[i] == '.') {
            if (level % 2 == 0) {
                temp[i] = 'X';
                dfs(level + 1);
                temp[i] = '.';
            }
            else {
                temp[i] = 'O';
                dfs(level + 1);
                temp[i] = '.';
            }
        }
    }
}
 
int main()
{
    dfs(0);    //가능한 경우의수 map에 저장
 
    while (1) {
        scanf("%s", &tik);
        if (!strcmp(tik, "end")) {
            return 0;
        }
 
        if (m[tik] == true) {
            printf("valid\n");
        }
        else {
            printf("invalid\n");
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11758번 - CCW (C++)  (0) 2022.11.15
[ 백준 ] 15681번 - 트리와 쿼리 (C++)  (0) 2022.11.14
[ 백준 ] 13913번 - 숨바꼭질 4 (C++)  (0) 2022.11.12
[ 백준 ] 1976번 - 여행 가자 (C++)  (0) 2022.11.11
[ 백준 ] 12286번 - 돌 그룹 (C++)  (0) 2022.11.10
반응형

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

 

23290번: 마법사 상어와 복제

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. fish struct를 만들어 vector <fish> vect에 물고기의 좌표와 방향을 저장하고, cnt 배열에 물고기의 개수를 저장합니다.

 

2. temp 배열에 물고기의 현재 위치를 저장하고, 물고기를 이동시키고, cnt 배열을 갱신해줍니다.

 

3. dfs를 이용하여 상어를 이동시키고, 이동한 좌표들을 box 배열에 저장합니다.

 

3. for문을 이용하여 vect 배열을 탐색하면서 상어가 지나간 자리에 있었던 물고기들의 좌표를 0으로 바꿔주고, 냄새를 남기고, 해당 좌표의 cnt 배열의 값을 0으로 경신합니다.

 

5. 냄새를 1 깎아줍니다.

 

6. temp 배열에 있는 물고기들의 좌표를 이용하여 cnt 배열을 갱신해주고, temp 배열에 남아있는 물고기들을 push 해줍니다.

 

7. vect 배열을 temp 배열로 초기화해줍니다.

 

8. 위 과정을 반복합니다.

 

[ 소스코드 ]

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<iostream>
#include<vector>
 
using namespace std;
 
struct fish{
    int y;
    int x;
    int d;
};
 
int M, S;
int arr[5][5];    //상어 위치
int smell[5][5];    //냄새 위치
vector<fish> vect;
int fy[9] = { 0,0,-1,-1,-1,0,1,1,1 };    //물고기 방향 배열
int fx[9] = { 0,-1,-1,0,1,1,1,0,-1 };
int dy[4] = { -1,0,1,0 };        //상어 방향 배열
int dx[4] = { 0,-1,0,1 };
int cnt[5][5];    //물고기 수
int sy, sx;        //상어 좌표
pair<int,int> temp[3];
pair<int,int> box[3];
int Max;
 
void dfs(int y, int x, int level, int ans)    //상어 이동
{
    if (level == 3) {
        if (Max < ans) {
            Max = ans;
            for (int i = 0; i < 3; i++) {
                box[i] = temp[i];
            }
        }
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy > 0 && yy <= 4 && xx > 0 && xx <= 4) {
            temp[level] = { yy,xx };
            int temp = cnt[yy][xx];
            cnt[yy][xx] = 0;
            dfs(yy, xx, level + 1, ans + temp);
            cnt[yy][xx] = temp;
        }
    }
}
 
void move()        //물고기 이동
{
    for (auto &next : vect) {
        int y = next.y;
        int x = next.x;
        int d = next.d;
        for (int i = 0; i < 8; i++) {
            int yy = y + fy[d];
            int xx = x + fx[d];
            if (yy > 0 && yy <= 4 && xx > 0 && xx <= 4) {
                if (arr[yy][xx] == 0 && smell[yy][xx] == 0) {
                    next.y = yy;
                    next.x = xx;
                    next.d = d;
                    cnt[y][x]--;
                    cnt[yy][xx]++;
                    break;
                }
            }
            d--;
            if (d <= 0) {
                d += 8;
            }
        }
    }
}
 
int main()
{
    scanf("%d %d", &M, &S);
 
    for (int i = 0; i < M; i++) {
        int y, x, d;
        scanf("%d %d %d", &y, &x, &d);
        vect.push_back({ y,x,d });
        cnt[y][x]++;
    }
 
    scanf("%d %d", &sy, &sx);
 
    arr[sy][sx] = 5;
 
    for(int s=0;s<S;s++){
        vector<fish> temp = vect;
 
        move();
 
        Max = -1;
 
        dfs(sy, sx, 0, 0);
        arr[sy][sx] = 0;
        sy = box[2].first;
        sx = box[2].second;
        arr[sy][sx] = 5;
 
        for (int i = 0; i < 3; i++) {
            cnt[box[i].first][box[i].second] = 0;
        }
 
        for (int i = 0; i < vect.size(); i++) {
            for (int j = 0; j < 3; j++) {
                if (vect[i].y == box[j].first && vect[i].x == box[j].second) {
                    smell[vect[i].y][vect[i].x] = 3;
                    cnt[vect[i].y][vect[i].x] = 0;
                    vect[i].y = 0;
                    break;
                }
            }
        }
 
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                if (smell[i][j] > 0) {
                    smell[i][j]--;
                }
            }
        }
 
        for (int i = 0; i < temp.size(); i++) {
            cnt[temp[i].y][temp[i].x]++;
        }
 
        for (int i = 0; i < vect.size(); i++) {
            if (vect[i].y != 0) {
                temp.push_back({ vect[i].y, vect[i].x, vect[i].d });
            }
        }
 
        vect = temp;
    }
 
    printf("%d", vect.size());
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17281번 - ⚾ (C++)  (0) 2022.10.07
[ 백준 ] 17136번 - 색종이 붙이기 (C++)  (0) 2022.10.06
[ 백준 ] 23289번 - 온풍기 안녕! (C++)  (0) 2022.10.04
[ 백준 ] 23288번 - 주사위 굴리기 2 (C++)  (0) 2022.10.03
[ 백준 ] 21609번 - 상어 중학교 (C++)  (0) 2022.10.02
반응형

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

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

각각의 문자에 따라 구역을 0으로 바꿔주는 함수를 만들어서 적록색약이 아닌 사람이 볼 수 있는 구역의 수를 구해줍니다. 그리고 R과 G를 한 구역으로 찾는 함수를 하나 더 만들어주어서 적록색약인 사람이 볼 수 있는 구역의 수를 출력해줍니다.

 

[ 소스 코드 ]

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
109
110
111
112
113
114
115
116
117
118
119
120
#include<iostream>
#include<queue>
 
using namespace std;
 
int N;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
 
struct node {
    int y;
    int x;
};
 
void bfs(int y, int x, char ch, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (temp[yy][xx] == ch) {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
void bfsRG(int y, int x, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (temp[yy][xx] == 'R' || temp[yy][xx] == 'G') {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    char arr[101][101];
    char temp[101][101];
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (temp[i][j] == 'R') {
                cnt++;
                bfs(i, j, 'R', temp);
            }
            else if (temp[i][j] == 'G') {
                cnt++;
                bfs(i, j, 'G', temp);
            }
            else if (temp[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', temp);
            }
        }
    }
 
    printf("%d ", cnt);
 
    cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'R' || arr[i][j] == 'G') {
                cnt++;
                bfsRG(i, j, arr);
            }
            else if (arr[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', arr);
            }
        }
    }
 
    printf("%d", cnt);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
반응형

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

 

1967번: 트리의 지름

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연

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
#include<iostream>
#include<vector>
#include<cstring>
 
using namespace std;
 
struct Node {
    int to;
    int dist;
};
 
int n;
 
vector<Node> list[10001];
int visited[10001];
int snode;
int diameter;
 
void dfs(int num, int dist)
{
    if (visited[num] == 1) {
        return;
    }
 
    if (diameter < dist) {
        diameter = dist;
        snode = num;
    }
 
    visited[num] = 1;
 
    for (int i = 0; i < list[num].size(); i++) {
        int next = list[num][i].to;
        int nextDist = list[num][i].dist;
        dfs(next, dist + nextDist);
    }
}
 
int main()
{
    cin >> n;
 
    for (int i = 0; i < n-1; i++) {
        int p, c, d;
        scanf("%d %d %d", &p, &c, &d);
        list[p].push_back({ c,d });
        list[c].push_back({ p,d });
    }
 
    dfs(1, 0);        //한 노드에서 가장 먼 노드를 찾기
 
    memset(visited, 0, sizeof(visited));
 
    dfs(snode, 0);    //위에서 찾은 노드에서 가장 먼 노드를 찾기
 
    cout << diameter;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13

+ Recent posts

티스토리툴바