반응형

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

 

14939번: 불 끄기

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

처음엔 dfs를 활용해서 풀었으나 100%에서 계속 틀렸습니다가 떠서 비트 마스킹으로 풀었습니다.

 

첫 줄의 스위치를 누르는 모든 경우의 수를 구한 후 arr [ i - 1][ j ]의 전구가 켜져 있다면 arr [ i ][ j ]의 스위치를 눌러서 끄고, 마지막에 마지막 줄에 전구가 다 꺼져있다면 불을 끌 수 있는 경우이므로 이때의 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
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
#include<iostream>
 
using namespace std;
 
char arr[10][10];
char temp[10][10];
int dy[5] = { -1,1,0,0,0 };
int dx[5] = { 0,0,0,-1,1 };
int cnt;
int ans = 999;
 
void turn(int y, int x)        //스위치를 누르면 상태 변경
{
    for (int i = 0; i < 5; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy >= 0 && yy < 10 && xx >= 0 && xx < 10) {
            if (temp[yy][xx] == 'O') {
                temp[yy][xx] = '#';
            }
            else {
                temp[yy][xx] = 'O';
            }
        }
    }
}
 
int check()        //전구를 다 끌 수 있는지 체크 후 0 또는 1 return
{
    for (int i = 1; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (temp[i - 1][j] == 'O') {
                turn(i, j);
                cnt++;
            }
        }
    }
 
    for (int i = 0; i < 10; i++) {
        if (temp[9][i] == 'O') {
            return 0;
        }
    }
 
    return 1;
}
 
 
//void dfs(int level)
//{
//    if (level == 10) {
//        int ch = check(cnt);
//        if (ch) {
//            ans = min(ans, ch);
//        }
//        return;
//    }
//
//    for (int i = 0; i < 2; i++) {
//        if (i == 0) {
//            turn(0, level, arr);
//            cnt++;
//            dfs(level + 1);
//            turn(0, level, arr);
//            cnt--;
//        }
//        else {
//            dfs(level + 1);
//        }
//    }
//}
 
int main()
{
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int t = 0; t < 1024; t++) {        //모든 경우의 수
        cnt = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                temp[i][j] = arr[i][j];
            }
        }
 
        for (int i = 0; i < 10; i++) {
            if (t & (1 << i)) {
                turn(0, i);
                cnt++;
            }
        }
 
        if (!check()) continue;        //check()가 0이면 continue
 
        ans = min(ans, cnt);
    }
 
    if (ans == 999) {
        cout << -1;
    }
    else {
        cout << ans;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
반응형

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

 

12850번: 본대 산책2

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

준영이가 정보관에서 1분 후 이동할 수 있는 건물은 전산관과 미래관입니다. 또한 전산관에서 1분 후 이동할 수 있는 건물은 신양관, 미래관 그리고 정보관입니다. 이를 행렬로 표현하면 다음과 같습니다.

 

그렇다면 각 건물에서 2분 후 이동할 수 있는 건물은 어떻게 구할 수 있을까요? 바로 1분 후 이동할 수 있는 건물들에 대한 행렬을 서로 곱하면 됩니다.

 

따라서 n분 후 이동할 수 있는 건물을 구하는 방법은 다음과 같습니다.

 

n % 2 == 0 일 때

mat( n / 2 ) * mat( n / 2 )

 

n % 2 == 1 일 때

mat( n - 1 ) * mat( 1 )

 

재귀를 통해 D번 이동했을 때 mat( D )의 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
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
#include <unordered_map>
 
#define ll long long
 
using namespace std;
 
vector<vector<ll>> mat = {        //연결되어 있으면 1
    {0,1,1,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {1,1,0,1,1,0,0,0},
    {0,1,1,0,1,1,0,0},
    {0,0,1,1,0,1,1,0},
    {0,0,0,1,1,0,0,1},
    {0,0,0,0,1,0,0,1},
    {0,0,0,0,0,1,1,0}
};
 
int D;
ll MOD = 1000000007;
unordered_map<int, vector<vector<ll>>> m;
 
vector<vector<ll>> multi(vector<vector<ll>> A, vector<vector<ll>> B)    //A, B 행렬 곱
{
    vector<vector<ll>> ret;
    for (int i = 0; i < 8; i++) {
        vector<ll> tmp;
        for (int j = 0; j < 8; j++) {
            ll sum = 0;
            for (int k = 0; k < 8; k++) {
                sum += A[i][k] * B[k][j];
                sum %= MOD;
            }
            tmp.push_back( sum );
        }
        ret.push_back( tmp );
    }
 
    return ret;
}
 
vector<vector<ll>> dfs(int num)        //행렬을 num번 곱했을 때 배열
{
    if (m.find(num) != m.end()) {
        return m[num];
    }
    if (num % 2 == 0) {
        return m[num] = multi(dfs(num / 2), dfs(num / 2));
    }
    else {
        return m[num] = multi(dfs(num - 1), dfs(1));
    }
}
 
int main()
{
    cin >> D;
 
    m[1] = mat;
 
    dfs(D);
 
    cout<<m[D][0][0];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
반응형

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

 

2098번: 외판원 순회

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/36?category=1064608 

 

[ 알고리즘 ] 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)

오늘 설명할 알고리즘은 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)입니다. 조합 최적화 문제로 전산학에서 연구된 가장 유명한 문제 중 하나입니다. 이 문제의 요구사항은 간단합니다.

rudalsd.tistory.com

 

위 글을 먼저 읽고 오시는 것을 추천드립니다!

 

이번 문제에서는 경로가 없는 경우도 존재하기 때문에 경로가 없는 경우 가지 않는다는 조건만 추가해주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<cstring>
 
using namespace std;
 
int N;
int arr[16][16];
int dp[16][(1<<16)];
int visitedAll;
 
int dfs(int node, int via)
{
    if (via == visitedAll) {
        if (arr[node][0] == 0) return 987654321;
        return arr[node][0];
    }
 
    if (dp[node][via] != -1) return dp[node][via];    //방문한 적 있다면 dp[vode][via]출력
    dp[node][via] = 987654321;            //아닐경우
 
    for (int i = 0; i < N; i++) {
        if (via & (1 << i)) continue;    //이미 방문
        if (arr[node][i] == 0) continue;    //길이 없다면
        dp[node][via] = min(dp[node][via], arr[node][i] + dfs(i, via | (1 << i)));
    }
    return dp[node][via];
}
 
int main()
{
    cin >> N;
 
    visitedAll = (1 << N) - 1;
    memset(dp, -1, sizeof(dp));
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
 
    int ans = dfs(0, 1);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
반응형

오늘 설명할 알고리즘은 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)입니다. 조합 최적화 문제로 전산학에서 연구된 가장 유명한 문제 중 하나입니다. 이 문제의 요구사항은 간단합니다. 각 도시들을 한 번씩 방문하고, 여행을 시작한 도시로 다시 돌아오는 최단 경로를 구하는 것입니다.

 

외판원 순회 문제의 경우 도시(N)의 개수가 10개 이하일 때와 16개 이하일 때 2가지로 나눠서 생각할 수 있습니다.

 

[ 동작 원리 ]

 

먼저 N이 10개 이하일 때는 완전 탐색을 통하여 구할 수 있습니다. 10개의 도시를 모두 한 번씩 방문하고 시작했던 도시로 돌아오는 방법은 모두 10! = 3628800이므로 충분히 완전 탐색을 통하여 구할 수 있습니다.

 

여기서 가장 중요한 포인트는 시작점이 어디여도 상관이 없다는 것입니다.

 

 

예를 들어

1→2→3→4→5→1,

2→3→4→5→1→2,

3→4→5→1→2→3,

…

위의 모든 경로가 이동거리가 같은 것을 볼 수 있습니다. 하지만 위의 방법은 겹치는 경로가 많이 발생하고 이를 줄일 수 있다면 더 많은 도시를 경유할 수 있을 것입니다. 따라서 N의 개수를 16개까지 더 늘려보겠습니다.

 

N이 16개 이하일 때는 dp을 통하여 구할 수 있습니다. dp [ 현재 도시 ][ 방문한 도시 ] = 남은 도시들을 방문할 수 있는 최단 경로입니다. 현재 도시에서 나머지 도시들을 방문할 때 최단 경로를 저장함으로써 중복되는 계산과정을 줄일 수 있습니다.

 

그리고 이때 방문한 도시는 비트 마스킹을 통해서 구현합니다. 위의 그래프처럼 5개의 도시가 있다고 생각하면 모두 방문했을 때 비트는 11111일 것입니다. 만약 1번 도시를 제외하고 모든 도시를 방문했다면 11110이 됩니다.

 

이를 점화식으로 표현하면 dp [ 현재 도시 ][ 방문한 도시 ] = min( dp [ 현재 도시 ][ 방문한 도시 ], 현재노드에서 i번 도시까지 거리 + dp[ i ][ 방문한 도시 ] )가 됩니다.

 

이를 통해 다음 문제를 풀 수 있습니다.

https://rudalsd.tistory.com/37

 

[ 백준 ] 2098번 - 외판원 순회 (C++)

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈..

rudalsd.tistory.com

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[ 알고리즘 ] 오일러 피 함수(Euler's phi function)  (0) 2022.07.09
[ 알고리즘 ] 포함 배제의 원리(Inclusion–exclusion principle)  (0) 2022.06.30
[ 알고리즘 ] 모듈러 연산(Modular Arithmetic)  (0) 2022.06.29
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)  (0) 2022.06.11
[ 알고리즘 ] 벨만 포드 알고리즘(Bellman-Ford Algorithm)  (0) 2022.06.08
반응형

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

 

14003번: 가장 긴 증가하는 부분 수열 5

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

lower_bound를 잘 활용하고 각 수의 index를 잘 저장해주면 쉽게 풀 수 있는 문제입니다.

 

먼저 각 수의 index를 저장할 index배열을 만듭니다. 그리고 각 수가 LIS의 몇 번째 인덱스에 있는지 계속 체크해주면서 index 배열에 저장해줍니다.

 

10 20 10 30 20 50

 

위의 수열을 예로 들면 

 

 

그리고 나서 index배열의 끝에서부터 값이 큰 수부터 차례로 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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N;
vector<int> lis;
vector<int> ans;
int arr[1000001];        //전체 배열
int index[1000001];        //lis 좌표를 저장하기 위한 배열
 
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        if (i == 0) {
            lis.push_back(arr[i]);
            index[i] = lis.size();        //lis의 몇번 째에 있는지 저장
        }
        else {
            if (*lis.rbegin() < arr[i]) {
                lis.push_back( arr[i] );
                index[i] = lis.size();    //lis의 몇번 째에 있는지 저장
            }
            else {
                auto idx = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
                lis[idx] = arr[i];        
                index[i] = idx + 1;        //lis의 몇번 째에 있는지 저장
            }
        }
    }
 
    int cnt = lis.size();
 
    for (int i = N - 1; i >= 0; i--) {    //반대부터 index를 1씩 줄여가며 순서대로 저장
        if (index[i] == cnt) {
            ans.push_back(arr[i]);
            cnt--;
        }
 
        if (cnt == 0) break;
    }
 
    cout << lis.size() << endl;
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << " ";
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
반응형

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

 

9328번: 열쇠

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

queue 두 개를 활용해서 bfs를 돌리면 쉽게 구할 수 있는 문제였습니다.

 

먼저 맵을 입력받을 때 탐색이 좀 더 쉽도록 배열의 1번 인덱스부터 w, h까지 입력을 받습니다. 그 이유는 가장 바깥쪽의 테두리는 자유롭게 다닐 수 있게 하여서 맵에 들어갈 수 있는 입구가 있다면 들어갈 수 있도록 설정하면 0, 0에서 시작하면 되기 때문입니다.

 

 

문을 만나면 키를 가지고 있는지 확인한 다음에 키가 있다면 그냥 열고 지나가고, 없다면 다음에 열쇠가 생겼을 때 열 수 있도록 door이라는 queue에 문의 좌표를 저장해 두었습니다.

 

그리고 키를 만나면 이 키로 열 수 있는 문이 있는지 체크하고 있다면 그 좌표를 q에 집어넣고, 없다면 그냥 지나가는 방법으로 문제를 풀었습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
 
using namespace std;
 
char arr[111][111];            //지도
int visited[111][111];        //방문 여부 체크
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
int main()
{
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        int h, w;
        int key[26] = { 0 };        //몇번 키를 가지고 있는지 체크할 배열
        memset(visited, 0, sizeof(visited));
        memset(arr, 0, sizeof(arr));
        queue<pos> q;
        queue<pos> door[26];        //열쇠가 없는 문에 닿았을 때 좌표 저장
        int cnt = 0;
        cin >> h>> w;
 
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                cin >> arr[i][j];
            }
        }
 
        string str = "";
        cin >> str;
        if (str != "0") {
            for (int i = 0; i < str.size(); i++) {
                key[str[i] - 'a']++;
            }
        }
 
        q.push({ 0,0 });
        visited[0][0] = 1;
 
        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 <= h + 1 && xx >= 0 && xx <= w + 1) {
                    if (visited[yy][xx] == 1 || arr[yy][xx] == '*') continue;
                    visited[yy][xx] = 1;
                    
                    if (arr[yy][xx] >= 'A' && arr[yy][xx] <= 'Z') {
                        if (key[arr[yy][xx] - 'A'] == 1) {    //열쇠가 있다면 통과
                            q.push({ yy,xx });
                        }
                        else {
                            door[arr[yy][xx] - 'A'].push({ yy,xx });    //없다면 좌표를 저장
                        }
                    }
                    else if (arr[yy][xx] >= 'a' && arr[yy][xx] <= 'z') {
                        key[arr[yy][xx] - 'a'] = 1;        //키를 가지고 있다고 체크
                        while (!door[arr[yy][xx] - 'a'].empty()) {    //키로 열 수 있는 문 좌표 q에 push
                            int curKey = arr[yy][xx] - 'a';
                            int curY = door[curKey].front().y;
                            int curX = door[curKey].front().x;
                            door[curKey].pop();
                            q.push({ curY,curX });
                        }
                        q.push({ yy,xx });
                    }
                    else if (arr[yy][xx] == '$') {        //문서면 cnt++
                        cnt++;
                        q.push({ yy,xx });
                    }
                    else {
                        q.push({ yy,xx });
                    }
                }
            }
        }
 
        cout << cnt << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
반응형

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

 

1167번: 트리의 지름

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지

www.acmicpc.net

 

 

[ 문제풀이 ]

 

풀이 방법을 생각해내는데 시간이 조금 걸렸지만 방법만 알아낸다면 매우 쉬운 문제였습니다.

 

먼저 지름은 어떤 점에서 출발하던 지 가장 먼 곳에 있습니다. 이를 이용하여 먼저 한 점에서 가장 먼 점을 찾고, 그 점으로부터 가장 먼 점을 찾으면 지름을 구할 수 있습니다.

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
int V;
vector<node> list[100001];
int visited[100001];
int startNode;
int ans;
 
void dfs(int num, int dist)            //시작점으로부터 가장 먼 노드와 거리를 저장
{
    if (visited[num] == 1) {
        return;
    }
    visited[num] = 1;
 
    if (ans < dist) {
        ans = dist;
        startNode = num;
    }
 
    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 >> V;
 
    for (int i = 0; i < V; i++) {
        int n;
        cin >> n;
        while (1) {
            int to;
            scanf("%d", &to);
            if (to != -1) {
                int dist;
                scanf("%d", &dist);
                list[n].push_back({ to,dist });
            }
            else {
                break;
            }
        }
    }
 
    dfs(1, 0);        //1번 노드에서 가장 먼 노드 저장
    memset(visited, 0, sizeof(visited));
    dfs(startNode, 0);    //시작 노드부터 가장 먼 노드와 거리 저장
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
반응형

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

 

17404번: RGB거리 2

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/12

 

[ 백준 ] 1149번 - RGB거리 (C++)

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주..

rudalsd.tistory.com

위 글을 먼저 보고 오는 것을 추천드립니다!!

 

일반 RGB거리와 다른 점은 1번 집과 N번 집도 색깔이 같으면 안 된다는 조건입니다.

 

따라서 일반적인 RGB거리의 답을 구하는 방식으로 구하되 마지막에 1번 집과 N번 집이 같지 않을 때의 최솟값을 구하면 되는 문제입니다.

 

[ 소스 코드 ]

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
#define MAX 987654321
 
#include <iostream>
 
using namespace std;
 
int N;
 
int arr[3][1001];        //각 색의 가격을 저장할 배열
int dp[3][1001];        //각 색을 칠했을 때의 총 가격
 
int main()
{
    cin >> N;
    int ans = MAX;
    for (int i = 1; i <= N; i++) {
        cin >> arr[0][i] >> arr[1][i] >> arr[2][i];
    }
 
    for (int i = 0; i < 3; i++)    //첫 집의 색깔을 졍해주기
    {
        for (int j = 0; j < 3; j++) {
            if (i == j) dp[j][1] = arr[j][1];    //첫 집의 색만 가격 입력
            else dp[j][1] = MAX;                //나머지 색은 가격 MAX
        }                                        //다음 집에서 첫 집의 색을 고르지 못하도록 하기 위해서
 
        for (int j = 2; j <= N; j++) {
            dp[0][j] = min(dp[1][j - 1], dp[2][j - 1]) + arr[0][j];    //앞의 집의 색 중 가격이 싼 색의 값과 지금 집 색의 값을 더함
            dp[1][j] = min(dp[0][j - 1], dp[2][j - 1]) + arr[1][j];
            dp[2][j] = min(dp[0][j - 1], dp[1][j - 1]) + arr[2][j];
        }
 
        for (int j = 0; j < 3; j++) {
            if (i != j) {                //마지막 집이 첫 집과 색이 같으면 안되기 때문에 i!=j 조건 넣기
                ans = min(ans, dp[j][N]);
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
반응형

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

 

7662번: 이중 우선순위 큐

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적

www.acmicpc.net

 

 

[ 문제풀이 ]

 

문제 난이도에 비해 생각을 좀 해야 하는 문제였습니다.

 

먼저 최댓값과 최솟값을 각각 저장할 maxpq와 minpq를 각각 만들고 입력받는 모든 수들을 넣습니다. 값을 넣을 때 map을 만들어 줘서 현재 그 숫자가 남아있는지 없는지를 체크합니다. 값을 뺄 때는 각각의 큐에서 빼지만 map과 비교하여 없는 숫자라면 계속 pop()해주고, 있는 숫자라면 map에서 빼고 난 후 pq에서 빼줍니다.

 

위 과정을 반복하면 현재 남아있는 숫자들이 map에 저장되어 있고, maxpq와 minpq를 모두 map과 비교하여 없는 숫자들을 pop해줍니다. 그러면 남은 숫자들이 pq에 각각 저장되어 있을 것이고 만약 큐 하나라도 비어있다면 EMPTY를 출력해주고 아니라면 각각의 pq에서 top을 출력해주면 됩니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <queue>
#include <unordered_map>
 
using namespace std;
 
int main()
{
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        priority_queue<int> maxpq;        //최댓값 저장
        priority_queue<int, vector<int>, greater<int>> minpq;    //최솟값 저장
        unordered_map<int, int> m;        //현재 남아있는 숫자 저장
 
        int k;
        cin >> k;
        for (int i = 0; i < k; i++) {
            char ch;
            cin >> ch;
            if (ch == 'I') {
                int num;
                cin >> num;
                maxpq.push(num);
                minpq.push(num);
                m[num]++;
            }
            else {
                int num;
                cin >> num;
                if (num == -1) {
                    if (!minpq.empty()) {
                        while (m[minpq.top()] == 0) {    //없는 숫자가 남아있다면
                            minpq.pop();                //모두 pop
                            if (minpq.empty()) {
                                break;
                            }
                        }
                        if (!minpq.empty()) {
                            m[minpq.top()]--;
                            minpq.pop();
                        }
                    }
                }
                else {
                    if (!maxpq.empty()) {
                        while (m[maxpq.top()] == 0) {    //없는 숫자가 남아있다면
                            maxpq.pop();                //모두 pop
                            if (maxpq.empty()) {
                                break;
                            }
                        }
                        if (!maxpq.empty()) {
                            m[maxpq.top()]--;
                            maxpq.pop();
                        }
                    }
                }
            }
        }
 
        while (!maxpq.empty()) {        //없는 숫자 pop
            if (m[maxpq.top()] == 0) {
                maxpq.pop();
            }
            else {
                break;
            }
        }
 
        while (!minpq.empty()) {        //없는 숫자 pop
            if (m[minpq.top()] == 0) {
                minpq.pop();
            }
            else {
                break;
            }
        }
 
        if (maxpq.empty()) {
            cout << "EMPTY" << endl;
        }
        else {
            cout << maxpq.top() << " " << minpq.top() << endl;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
반응형

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

티스토리툴바