반응형

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

 

3176번: 도로 네트워크

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/95?category=1073064 

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까

rudalsd.tistory.com

 

1. 희소 배열의 각 노드에 max, min 값을 각각 저장해줍니다.

 

2. 두 노드의 높이를 맞춰줄 때 Max, Min을 계속 갱신해줍니다.

 

3. Min과 Max를 출력해줍니다.

 

[ 소스 코드 ]

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
#include<cstdio>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int to;
    int max;
    int min;
};
 
int N, K;
int H;        //트리의 높이
node arr[100001][18];
vector<vector<node>> list;
int visited[100001];
int h[100001];    //노드의 높이
 
void dfs(int cur)    //arr[cur][0] 채우기
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur])
    {
        if (visited[next.to] != 1) {
            arr[next.to][0] = { cur, next.max, next.min };
            h[next.to] = h[cur] + 1;
            dfs(next.to);
        }
    }
}
 
void makeTree()        //트리 만들기
{
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= N; j++) {
            auto next = arr[j][i - 1];
            if (arr[next.to][i-1].to != 0) {
                int Max = max(next.max, arr[next.to][i - 1].max);
                int Min = min(next.min, arr[next.to][i - 1].min);
                arr[j][i] = { arr[next.to][i - 1].to, Max, Min };
            }
        }
    }
}
 
void Dist(int a, int b)    //a, b 사이의 가장 긴 도로와 짧은 도로 길이 구하기
{
    if (h[a] > h[b]) {    //a가 트리의 더 위에 있도록
        int temp = a;
        a = b;
        b = temp;
    }
 
    int Min = 987654321;
    int Max = 0;
 
    if (h[a] != h[b]) {    //높이가 다르다면 맞춰주기
        for (int i = H; i >= 0; i--) {
            int mask = 1 << i;
            if (h[b] - h[a] >= mask) {
                Min = min(Min, arr[b][i].min);
                Max = max(Max, arr[b][i].max);
                b = arr[b][i].to;
            }
            if (h[a] == h[b]) break;
        }
    }
 
    if(a!=b) {    //같은 높이일 때 서로 다른 숫자면
        for (int i = H; i >= 0; i--) {
            if (arr[a][i].to == arr[b][i].to || arr[a][i].to == 0 || arr[b][i].to == 0) continue;
            Max = max(Max, max(arr[a][i].max,arr[b][i].max));
            Min = min(Min, min(arr[a][i].min, arr[b][i].min));
            a = arr[a][i].to;
            b = arr[b][i].to;
        }
 
        Max = max(Max, max(arr[a][0].max, arr[b][0].max));
        Min = min(Min, min(arr[a][0].min, arr[b][0].min));
    }
 
    printf("%d %d\n", Min, Max);
}
 
int main()
{
    scanf("%d", &N);
 
    H = ceil(log2(N));
    list.resize(N + 1);
    h[1] = 1;
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, dist;
        scanf("%d %d %d", &a, &b, &dist);
 
        list[a].push_back({ b,dist,dist });
        list[b].push_back({ a,dist,dist });
    }
 
    dfs(1);
    makeTree();
 
    scanf("%d", &K);
 
    for (int i = 0; i < K; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        Dist(a, b);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
[ 백준 ] 11286번 - 절댓값 힙 (C++)  (0) 2022.08.23
[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
반응형

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

 

1780번: 종이의 개수

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수

www.acmicpc.net

 

 

[ 문제풀이 ]

 

분할 정복을 통해서 문제를 풀었습니다.

 

1. 원하는 부분의 숫자가 모두 같은 지 판단합니다.

 

2. 숫자가 다르다면 다시 9구역으로 나누어 1번을 반복합니다.

 

3. 숫자가 같다면 ans 배열에 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
#include<iostream>
 
using namespace std;
 
int N;
int arr[2200][2200];
int ans[3];
 
void conquer(int y1, int y2, int x1, int x2)
{
    int flag = 0;
    int cur = arr[y1][x1];
    for (int i = y1; i < y2; i++) {        //모두 같은 수인지
        for (int j = x1; j < x2; j++) {
            if (cur != arr[i][j]) {
                flag = 1;
                break;
            }
 
        }
    }
 
    int y = (y2 - y1) / 3;
    int x = (x2 - x1) / 3;
 
    if (flag == 0) {        //같은 수라면
        ans[cur + 1]++;
    }
    else {        //다른 수가 있다면
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                conquer(y1 + y * i, y1 + y * (i + 1), x1 + x * j, x1 + x * (j + 1));
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    conquer(0, N, 0, N);
 
    for (int i = 0; i < 3; i++) {
        printf("%d\n", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11286번 - 절댓값 힙 (C++)  (0) 2022.08.23
[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
반응형

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

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

끝나는 시간이 짧은 회의일수록 더 많은 회의에 참여할 수 있고, 끝나는 시간이 짧은 회의 중 시작하는 시간이 가장 빠른 회의를 하나씩 넣어가면서 문제를 풀었습니다.

 

1. 끝나는 시간이 짧은 회의일수록, 그중 시작하는 시간이 가장 빠른 회의일수록 앞으로 배치되게 정렬합니다.

 

2. 가장 앞에 있는 회의를 이전 회의의 끝나는 시간과 비교하여 이전 회의의 끝나는 시간보다 회의의 시작시간이 더 늦다면 ans를 1씩 더해줍니다.

 

3. 방금 시작한 회의의 끝나는 시간을 cur변수에 갱신시켜줍니다.

 

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct conference {
    int start;
    int end;
};
 
bool cmp(conference left, conference right) {        //정렬 순서
    if (left.end == right.end) return left.start < right.start;    //시작 시간이 빠를수록
    return left.end < right.end;    //끝나는 시간이 빠를수록
}
 
int N;
conference arr[100000];
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &arr[i].start, &arr[i].end);
    }
 
    sort(arr, arr + N, cmp);
 
    int cur = 0;
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        if (cur <= arr[i].start) {
            cur = arr[i].end;
            ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
[ 백준 ] 11727번 - 2xn 타일링 2 (C++)  (0) 2022.08.17
반응형

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

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. $A_{i} = A_{i-1}$의 배수이므로 큰 수부터 K에 값을 빼가면서 ans의 값을 1씩 더해줍니다.

 

2. K가 0이 될 때 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
#include<iostream>
 
using namespace std;
 
int N, K;
int arr[10];
int ans;
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = N - 1; i >= 0; i--) {
        while (K >= arr[i]) {
            K -= arr[i];
            ans++;
        }
        if (K == 0) break;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
[ 백준 ] 11727번 - 2xn 타일링 2 (C++)  (0) 2022.08.17
[ 백준 ] 14499번 - 주사위 굴리기 (C++)  (0) 2022.08.16
반응형

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

팀의 조합을 $_{N}\textrm{C}_{\frac{N}{2}}$로 뽑아 같은 팀끼리의 점수를 더해 각 값의 차를 ans에 갱신해주는 방법을 사용했습니다.

 

1. $\frac{N}{2}$명을 뽑아 팀을 만듭니다.

 

2. 같은 팀끼리 점수를 더해 각 값의 차를 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
#include<iostream>
 
using namespace std;
 
int N;
int arr[20][20];
int box[20];
int ans = 987654321;
 
void dfs(int level, int n)
{
    if (level == N / 2) {
        int a, b;
        a = b = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {    //같은 팀이면 값 더하기
                if (box[i] == 1 && box[j] == 1) {
                    a += arr[i][j];
                }
                else if (box[i] == 0 && box[j] == 0) {
                    b += arr[i][j];
                }
            }
        }
        ans = min(ans, abs(a - b));
        return;
    }
 
 
    for (int i = n; i < N; i++) {    //20 C 10
        box[i] = 1;
        dfs(level + 1, i + 1);
        box[i] = 0;
    }
}
 
int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    dfs(0, 0);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
[ 백준 ] 11727번 - 2xn 타일링 2 (C++)  (0) 2022.08.17
[ 백준 ] 14499번 - 주사위 굴리기 (C++)  (0) 2022.08.16
[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
반응형

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

 

11727번: 2×n 타일링 2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제는 간단한 점화식을 세워서 풀 수 있었습니다.

 

dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] * 2

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
 
using namespace std;
 
int n;
int dp[1001];
 
int main()
{
    cin >> n;
 
    dp[1] = 1;
    dp[2] = 3;
 
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] * 2;
        dp[i] %= 10007;
    }
 
    cout << dp[n];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
[ 백준 ] 14499번 - 주사위 굴리기 (C++)  (0) 2022.08.16
[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
반응형

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

 

14499번: 주사위 굴리기

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제에서는 x가 세로, y가 가로이기 때문에 잘 읽어보고 문제를 푸셔야 합니다.

 

1. 지도와 현재 주사위의 좌표를 입력받습니다.

 

2. 방향에 따라 주사위를 굴려주시고, 주사위의 윗면은 다른 변수에 저장하여 따로 관리해줍니다.

 

3. 바닥이 0이라면 주사위에 있는 숫자를 복사해주고, 아니라면 바닥에 있는 숫자를 주사위에 복사하고 바닥은 0으로 갱신해줍니다.

 

4. 따로 저장해 놓은 윗면의 값을 출력해줍니다.

 

[ 소스 코드 ]

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>
 
using namespace std;
 
int N, M, x, y, K;
int arr[20][20];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int dice[3][3];
int temp1;
int temp2;
 
int main()
{
    scanf("%d %d %d %d %d", &N, &M, &x, &y, &K);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < K; i++) {
        int dir;
        scanf("%d", &dir);
        int yy = y + dy[dir - 1];    //주사위가 움직일 좌표
        int xx = x + dx[dir - 1];
        if (xx >= 0 && xx < N && yy >= 0 && yy < M) {
            if (dir == 1) {    //동쪽
                if (arr[xx][yy] != 0) {
                    dice[1][2] = arr[xx][yy];
                    arr[xx][yy] = 0;
                }
                else {
                    arr[xx][yy] = dice[1][2];
                }
                temp1 = dice[1][0];
                for (int j = 0; j < 2; j++) {
                    dice[1][j] = dice[1][j + 1];
                }
                dice[1][2] = temp2;
                temp2 = temp1;
            }
            else if (dir == 2) {    //서쪽
                if (arr[xx][yy] != 0) {
                    dice[1][0] = arr[xx][yy];
                    arr[xx][yy] = 0;
                }
                else {
                    arr[xx][yy] = dice[1][0];
                }
                temp1 = dice[1][2];
                for (int j = 2; j > 0; j--) {
                    dice[1][j] = dice[1][j - 1];
                }
                dice[1][0] = temp2;
                temp2 = temp1;
            }
            else if (dir == 3) {    //북쪽
                if (arr[xx][yy] != 0) {
                    dice[0][1] = arr[xx][yy];
                    arr[xx][yy] = 0;
                }
                else {
                    arr[xx][yy] = dice[0][1];
                }
                temp1 = dice[2][1];
                for (int j = 2; j > 0; j--) {
                    dice[j][1] = dice[j - 1][1];
                }
                dice[0][1] = temp2;
                temp2 = temp1;
            }
            else {        //남쪽
                if (arr[xx][yy] != 0) {
                    dice[2][1] = arr[xx][yy];
                    arr[xx][yy] = 0;
                }
                else {
                    arr[xx][yy] = dice[2][1];
                }
                temp1 = dice[0][1];
                for (int j = 0; j < 2; j++) {
                    dice[j][1] = dice[j + 1][1];
                }
                dice[2][1] = temp2;
                temp2 = temp1;
            }
            printf("%d\n", temp2);
            y = yy;
            x = xx;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
[ 백준 ] 11727번 - 2xn 타일링 2 (C++)  (0) 2022.08.17
[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
반응형

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

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

 

 

[ 문제풀이 ]

 

덱(deque)이라는 자료구조를 활용하여 문제를 풀었습니다.

 

1. 사과의 위치와 시간에 따른 방향 정보를 입력받습니다.

 

2. 덱을 활용하여 머리와 꼬리의 정보를 저장합니다.

 

3. 사과를 먹으면 꼬리를 그대로 두고, 사과를 먹지 않는다면 꼬리를 덱에서 빼줍니다.

 

4. 벽이나 몸에 부딪히면 현재 시간을 출력해주고 종료합니다.

 

5. 정보를 바탕으로 배열에 값을 저장해줍니다.

 

[ 소스 코드 ]

 

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
#include<iostream>
#include<deque>
 
using namespace std;
 
struct pos {
    int y;
    int x;
};
 
int N, K, L;
int arr[101][101];            //보드
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int dir = 1;
deque<pos> dq;
int cnt;
char direction[10001];        //시간 X이후 움직일 방향 저장할 배열
 
int main()
{
    scanf("%d %d", &N, &K);
    for (int i = 0; i < K; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        arr[a][b] = 1;
    }
    scanf("%d", &L);
    for (int i = 0; i < L; i++) {
        int a;
        char b;
        scanf("%d %c", &a, &b);
        direction[a] = b;
    }
 
    dq.push_back({ 1,1 });
    arr[1][1] = 2;
 
    while (1)
    {
        int fy = dq.front().y;    //머리
        int fx = dq.front().x;
        int by = dq.back().y;    //꼬리
        int bx = dq.back().x;
 
        int yy = fy + dy[dir];    //이동할 좌표
        int xx = fx + dx[dir];
 
        cnt++;
 
        if (arr[yy][xx] == 2 || yy<1 || yy>N || xx<1 || xx>N) {    //몸통이거나 벽이라면
            printf("%d", cnt);
            return 0;
        }
 
        if (arr[yy][xx] != 1) {    //사과를 먹지 않으면
            arr[by][bx] = 0;
            dq.pop_back();
        }
 
        arr[yy][xx] = 2;
        dq.push_front({ yy,xx });
 
        if (direction[cnt] == 'L') {
            dir--;
        }
        else if (direction[cnt] == 'D') {
            dir++;
        }
 
        if (dir < 0) {
            dir = 3;
        }
        if (dir > 3) {
            dir = 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11727번 - 2xn 타일링 2 (C++)  (0) 2022.08.17
[ 백준 ] 14499번 - 주사위 굴리기 (C++)  (0) 2022.08.16
[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
반응형

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

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

 

 

[ 문제풀이 ]

 

bfs를 활용하여 문제를 풀었습니다.

 

1. 각 칸의 입력을 받으면서 값이 1이라면 queue에 넣습니다.

 

2. bfs를 돌리면서 cnt의 최댓값을 ans에 저장합니다.

 

3. arr배열에 있는 토마토 중 익지 않은 토마토가 하나라도 있다면 -1을 출력하고 아니라면 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[1000][1000];
int dy[4] = { -1,1,0,0 };
int dx[4] = {0, 0, -1, 1};
 
struct node {
    int y;
    int x;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &M, &N);
    queue<node> q;
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 1) {
                q.push({ i,j,0 });
            }
        }
    }
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
 
        ans = max(ans, cnt);
 
        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 < M) {
                if (arr[yy][xx] == 0) {    //익지 않은 토마토가 있다면
                    arr[yy][xx] = 1;
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) {        //안 익은 토마토가 하나라도 있으면
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0) {
                printf("-1");
                return 0;
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14499번 - 주사위 굴리기 (C++)  (0) 2022.08.16
[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
반응형

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

 

16928번: 뱀과 사다리 게임

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으

www.acmicpc.net

 

 

[ 문제풀이 ]

 

bfs를 활용하여 문제를 풀었습니다.

 

1. 각 칸을 자신으로 초기화합니다.

 

2. 사다리와 뱀을 입력받습니다.

 

3. bfs를 활용하여 100번 칸에 도착하면 답을 출력하고 종료합니다.

 

위의 3번 과정을 진행할 때 한 번의 과정 동안 6번의 반복을 하면서 방문 여부를 체크해주고, 방문하지 않았다면 queue에 넣어 다음 과정을 진행해 줍니다.

 

[ 소스 코드 ]

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>
 
using namespace std;
 
int N, M;
int arr[101];        //각 칸의 이동 위치
int visited[101];    //각 칸의 방문 여부
 
struct node {
    int cur;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= 100; i++) {    //각 칸의 이동 위치를 자신으로 초기화
        arr[i] = i;
    }
 
    for (int i = 0; i < N; i++) {    //사다리 입력
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a] = b;
    }
 
    for (int i = 0; i < M; i++) {    //뱀 입력
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a] = b;
    }
 
    queue<node> q;
    q.push({ 1, 0 });
 
    while (1)
    {
        int cur = q.front().cur;
        int cnt = q.front().cnt;
        q.pop();
 
        if (cur == 100) {    //100번 칸에 도착하면 cnt 출력 후 종료
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[cur] == 1) continue;
        visited[cur] = 1;
 
        for (int i = 1; i <= 6; i++) {
            int next = arr[cur + i];    //이동할 칸
            if (visited[next] != 1) {
                q.push({ next, cnt + 1 });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10

+ Recent posts

티스토리툴바