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

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

www.acmicpc.net

제목대로 연결 요소의 개수를 구하는 문제인데 배열 형태가 아니므로 각 정점을 인접 리스트로 구현해준다.

나는 int형 벡터를 갖는 배열로 구현하였다.

간선의 개수만큼 반복문을 실행하여 정점을 입력받아 u리스트에는 v를 추가하고 v리스트에는 u를 추가한다.

 

한 번 bfs를 시작할때 연결된 정점을 모두 방문한다. 즉, bfs가 한번 도는게 연결 요소 1개인 셈이다.

그러므로 모든 방문하지 않은 정점을 방문해서 bfs가 새로 실행될 때마다 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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
bool check[1000];
vector<int> list[1000];
 
void bfs(int x) {
    queue<int> q;
    q.push(x);
    check[x] = true;
 
    while(!q.empty()) {
        x = q.front();
        q.pop();
 
 
        //연결된 정점들을 검사
        for(int k=0; k<list[x].size(); k++) {
            int y = list[x][k];
            if(check[y] == false) {
                q.push(y);
                check[y] = true;
            }
        }
    }
}
 
int main() {
 
    int n,m;
    scanf("%d %d", &n,&m);
 
 
    //인접 리스트(벡터 배열로 구현)
    for(int i=0; i<m; i++) {
        int u, v;
        scanf("%d %d", &u,&v);
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    int ans = 0;
    for(int i=1; i<=n; i++) {
        if(check[i] == false) {
            ++ans;
            bfs(i);
        }
    }
 
    printf("%d", ans);
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 7569. 토마토 (3차원)  (0) 2019.06.27
[BOJ] 7576. 토마토  (0) 2019.06.27
[BOJ] 2178. 미로 탐색  (0) 2019.06.25
[BOJ] 4963. 섬의 개수  (0) 2019.06.25
[BOJ] 2667. 단지번호붙이기  (0) 2019.06.25

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

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

이 문제는 (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다.

문제에서는 1, 1이라고 한 곳은 실제로는 0, 0 이므로 주의해야 한다!

마찬가지로 마지막 칸 N, M도 (N-1, M-1) 칸을 출력해주면 된다.

 

최소 칸수를 구하는 문제이므로 bfs를 사용한다.

시작칸에서 부터 갈 수 있는 칸으로 단계적으로 진행하기 때문에 최단 거리로 이동할 수 있다.

이동할 때마다 각 칸에는 해당 칸까지의 이동 횟수를 저장해준다.

그러면 최종적으로 마지막 칸에 마지막 칸까지의 최소 이동 횟수가 저장된다.

 

 

문제에 나와있는 예시를 보면 아래와 같이 지도가 있는데

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

 

bfs를 통해 이동 횟수를 cnt배열에 저장해주면 다음과 같다.

1 0 9 10 11 12
2 0 8 0 12 0
3 0 7 0 13 14
4 5 6 0 14 15

 

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
#include <cstdio>
#include <queue>
using namespace std;
 
int n,m;
int map[100][100];
int cnt[100][100];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
int main() {
    scanf("%d %d", &n,&m);
 
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
 
    queue<pair<int,int> > q;
 
    //첫번째 칸에서 시작
    q.push(make_pair(0,0));
    cnt[0][0] = 1;
 
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int k=0; k<4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(map[nx][ny] == 1 && cnt[nx][ny] == 0) {
                q.push(make_pair(nx,ny));
 
                //이전 단계보다 1 증가(이동 횟수 증가)
                cnt[nx][ny] = cnt[x][y] + 1;
            }
        }
    }
 
    //마지막 칸을 출력
    printf("%d\n", cnt[n-1][m-1]);
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 7576. 토마토  (0) 2019.06.27
[BOJ] 11724. 연결 요소의 개수  (0) 2019.06.27
[BOJ] 4963. 섬의 개수  (0) 2019.06.25
[BOJ] 2667. 단지번호붙이기  (0) 2019.06.25
[BOJ] 14888. 연산자 끼워넣기  (0) 2019.06.20

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

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수

www.acmicpc.net

연결 요소를 찾는 문제이다. bfs나 dfs를 사용해서 풀 수 있다.

나는 bfs를 사용해서 풀었다.

아파트가 있고 아직 방문하지 않은(단지 번호가 붙어있지 않은) 모든 칸에 대해서 bfs를 실행해준다.

단지 번호(cnt)는 bfs가 새로 실행될때마다 증가한다.

단지 번호는 num이라는 int형 이차원 배열을 만들어서 붙여주고 이 배열을 사용하여 방문 체크도 해준다.

 

 

탐색을 모두 마쳤으면, 각 단지별 아파트 개수를 세준다.

새로운 ans 배열을 만들어서 num배열의 값을 index로 값을 증가시킨다.

즉, ans배열의 1번째에는 단지 번호가 1인 아파트의 개수가 저장되고 ans[2]에는 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
 
int n;
int cnt;
int map[25][25];
int num[25][25];
int ans[25*25];
 
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
void bfs(int x, int y) {
    queue<pair<int,int> > q;
    
 
//시작칸 큐에 넣어주고 단지 번호 붙여준다.
q.push(make_pair(x,y));   
    num[x][y] = cnt;
 
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
 
        //인전한 칸으로 이동
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            //범위 벗어나면 넘어간다.
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
 
            //아파트가 있고 아직 방문하지 않은 경우
            if(map[nx][ny] == 1 && num[nx][ny] == 0) {
             //큐에 넣어주고
                q.push(make_pair(nx,ny));
 
                //단지 번호를 붙여준다.
                num[nx][ny] = cnt;
            }
            
        }
    }
}
 
int main() {
 
    scanf("%d", &n);
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    
    cnt = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
 
 
         //집이 있는 곳이고 아직 방문하지 않은 경우 bfs를 실행
            if(map[i][j] == 1 && num[i][j] == 0) {
             //다음 연결 요소 이므로 단지 번호를 늘려준다.
                ++cnt;
                bfs(i,j);
            }
            
        }
    }
 
 
    //총 단지수를 출력
    printf("%d\n", cnt);
 
 
    //각 단지 번호를 인덱스로 ans배열의 값을 증가시킨다.
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(num[i][j] != 0) {
                ans[num[i][j]] += 1;
            }
        }
    }
 
    //문제 조건에서 정렬하라고 했으므로 정렬
    sort(ans+1, ans+cnt+1);
 
    for(int i=1; i<=cnt; i++) {
        printf("%d\n",ans[i]);
    }
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2178. 미로 탐색  (0) 2019.06.25
[BOJ] 4963. 섬의 개수  (0) 2019.06.25
[BOJ] 14888. 연산자 끼워넣기  (0) 2019.06.20
[BOJ] 6603. 로또  (0) 2019.06.20
[BOJ] 10971. 외판원 순회2 (DFS 풀이)  (0) 2019.06.20

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

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

www.acmicpc.net

주어진 N개의 숫자의 위치는 변하지 않고 숫자 사이의 연산자의 위치만 바꿔서 계산 결과의 최솟값과 최댓값을 출력하는 문제이다.

solve함수에서 index번째에서 사용할 수 있는 연산자를 사용하는 모든 경우를 구해준다.

연산자를 선택할 때마다 해당 연산자를 사용해서 계산한 값을 넘겨준다.

사용한 연산자는 처음 입력받은 사용할 수 있는 개수에서 -1을 해주고 탐색에서 돌아온 경우 다시 +1을 해준다.

이 부분을 안 해줘서 계속 최솟값과 최댓값이 같은 값으로 나왔었다...

 

N-1 개의 모든 연산자를 결정해준 경우 최종 계산된 값을 ans 벡터에 추가해준다.

마지막으로 ans 벡터를 정렬해주면 맨 앞에 위치한 값이 최솟값이고 맨 마지막에 위치한 값이 최댓값이 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<int> num;
vector<int> ans;
 
 
void solve(int index, int op[], int result) {
    //모든 연산자를 선택해준 경우
    if(index == n-1) {
        //계산 결과를 ans 벡터에 넣어준다.
        ans.push_back(result);
        return;
    }
    
    for(int i=0; i<4; i++) {
        //사용할 수 있는 i번째 연산자가 없는 경우
        if(op[i] == 0) continue;
        
        //연산자를 사용한다.
        op[i] -= 1;
 
        //각각 덧셈인 경우, 뺄셈인 경우, 곱셈인 경우, 나눗셈인 경우에 대해서 결과를 계산해서 넘겨준다.
        if(i == 0) {
            solve(index+1,op, result+num[index+1]);
        } else if(i == 1) {
            solve(index+1,op, result-num[index+1]);
        } else if(i == 2) {
            solve(index+1,op, result*num[index+1]);
        } else {
            solve(index+1,op, result/num[index+1]);
        }
 
        //i번째 연산자를 사용하는 경우를 위에서 보내줬으므로
        //다시 돌아왔을때 연산자의 상태를 원래대로 돌려준다.
        op[i] += 1;
    }
}
 
int main() {
    cin >> n;
 
    int op[4];
 
 
    //피연산자를 입력
    for(int i=0; i<n; i++) {
        int x;
        cin >> x;
        num.push_back(x);
    }
 
 
    //각 연산자의 개수를 입력
    for(int i=0; i<4; i++) {
        int x;
        cin >> x;
        op[i] = x;
    }
 
    solve(0,op, num[0]);
 
 
    //계산 결과를 정렬해준다.
    sort(ans.begin(), ans.end());
 
 
    //맨뒤의 값이 최댓값, 맨 앞의 값이 최소값이므로 각각 출력해준다.
    cout << ans.back() << '\n';
    cout << ans.front();
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 4963. 섬의 개수  (0) 2019.06.25
[BOJ] 2667. 단지번호붙이기  (0) 2019.06.25
[BOJ] 6603. 로또  (0) 2019.06.20
[BOJ] 10971. 외판원 순회2 (DFS 풀이)  (0) 2019.06.20
[BOJ] 10971. 외판원 순회2  (0) 2019.06.20

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

 

6603번: 로또

문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2

www.acmicpc.net

 

K개 중 6개를 고르는 문제이다. 고르는 개수가 정해져 있기 때문에 넥퍼뮤를 사용해도 좋지만 조합을 이용해서 구했다.

 

먼저 k개만큼 배열에 입력받고, 이 배열에서 6개를 고르는 모든 경우를 구해준다.

숫자를 고를때마다 lotto 벡터에 넣어주고 6개의 숫자를 고른 경우 lotto 벡터에 있는 값들을 모두 출력해주고 return

k개의 숫자를 사용할지 안 할지 모두 정한 경우(index 가 k를 넘어간 경우)에도 더 이상 고를 숫자가 없으므로 return 해준다.

 

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 <algorithm>
#include <vector>
using namespace std;
 
int k;
int num[12];
 
void solve(int index, int select, vector<int> &lotto) {
    //고를 수의 범위가 넘어감
    if(index > k) {
        return;
    }
 
    //6개를 모두 골랐다
    if(select == 6) {
 
        //고른 숫자들을 모두 출력해준다.
        for(int i=0; i<6; i++) {
            cout << lotto[i] << ' ';
        }
        cout << '\n';
        return;
    }
 
 
    //현재 index번째 숫자를 고른 경우를 탐색.
    //하나를 골랐으므로 select 값을 1 증가시킨다.
    lotto.push_back(num[index]);
    solve(index+1, select+1, lotto);
 
    //다시 빼주고 고르지 않는 경우를 탐색
    lotto.pop_back();
    solve(index+1, select, lotto);
 
}
 
 
int main() {
 
    while(true) {
        cin >> k;
        if(k == 0) break;
 
        for(int i=0; i<k; i++) {
           int x;
           cin >> x;
           num[i] = x;
        }
 
        vector<int> lotto;
        solve(0,0,lotto);
        cout << '\n';
    
    }
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2667. 단지번호붙이기  (0) 2019.06.25
[BOJ] 14888. 연산자 끼워넣기  (0) 2019.06.20
[BOJ] 10971. 외판원 순회2 (DFS 풀이)  (0) 2019.06.20
[BOJ] 10971. 외판원 순회2  (0) 2019.06.20
[BOJ] 10974. 모든 순열  (0) 2019.06.20

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

 

10971번: 외판원 순회 2

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다.

www.acmicpc.net

앞에서 next_permutation을 사용해서 풀었는데 dfs를 사용해서도 풀어봤다.

개인적으로 아직 넥퍼뮤가 익숙하지 않아서 dfs로 푸는 게 더 풀기 쉬웠다.

 

dfs를 사용할때는 방문 표시를 잘해주면 된다.

현재 도시를 방문하는 경우 check배열을 true값으로 바꿔주고 현재 도시를 선택하는 경우를 모두 해준 경우(탐색에서 돌아온 경우)

방문 표시를 지워준다(false 값으로 바꿔준다)

 

자세한 설명은 아래 코드를 참고!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
 
using namespace std;
int w[10][10];
int n;
int ans;
 
void dfs(int index,int cnt, int sum, bool check[]) {
 
    //첫번째 도시부터 마지막 도시까지 방문했으면
    if(cnt == n-1) {
 
        //마지막도시에서 시작 도시로 경로가 존재하지 않으면 return
        if(w[index][0] == 0) return;
        //그렇지 않으면 비용을 합에 더해준다.
        else sum += w[index][0];
 
        //최솟값이 초기값이거나 sum이 현재 최솟값보다 적은 경우
        if(ans == -1 || ans > sum) {
            ans = sum;
        }
 
        return;
    }
 
 
    //방문하지 않은 모든 도시로 가는 경우를 탐색
    for(int i=1; i<n; i++) {
 
        //i번째 도시를 방문했으면 넘어간다.
        if(check[i]) continue;
 
        //경로가 존재하지 않으면 넘어간다.
        if(w[index][i] == 0) continue;
 
 
        //i번째 도시를 방문
        check[i] = true;
        dfs(i,cnt+1,sum+w[index][i],check);
 
        //i번째 도시를 가는 경우에서 돌아왔으므로 방문표시를 없애준다.
        check[i] = false;
 
    }
 
}
 
 
int main() {
    cin >> n;
 
 
    //비용을 w배열에 입력
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> w[i][j];
        }
    }
 
 
    //최솟값을 저장
    ans = -1;
 
    //check 배열을 사용하여 방문 표시를 한다. false값으로 초기화
    bool check[10]={false};
 
    //0번째 도시를 시작점으로 잡고 탐색을 시작한다
    check[0] = true;
    dfs(0,0,0,check);
 
    cout << ans;
    
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14888. 연산자 끼워넣기  (0) 2019.06.20
[BOJ] 6603. 로또  (0) 2019.06.20
[BOJ] 10971. 외판원 순회2  (0) 2019.06.20
[BOJ] 10974. 모든 순열  (0) 2019.06.20
[BOJ] 9095. 1, 2, 3 더하기  (0) 2019.06.20

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

 

10971번: 외판원 순회 2

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다.

www.acmicpc.net

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP)라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나라고 문제 설명에 나와있다.

실제로 학교 알고리즘 수업에서도 배운 기억이 있다.

 

이 문제에서는 n의 범위가 (2 ≤ N ≤ 10) 이므로 다음 순열을 이용해서 모든 경로를 구해볼 수 있다.

모든 경로에서의 비용을 계산해서 최솟값을 구해준다.

다음 순열은 d 벡터를 만들어서 사용한다.

d벡터에는 n만큼의 수가 들어있다. 예를 들어, n 이 4이면 d에는 0, 1, 2, 3의 값이 들어 있고 각각은 도시를 의미한다.

이 d 벡터의 모든 순열을 구해줘서 모든 경로를 구할 수 있다.

즉, d 벡터의 값이 도시의 번호와 마찬가지이므로 d벡터의 값을 w배열의 index로 사용하면 된다.

 

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int w[10][10];
    vector<int> d(n);
 
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> w[i][j];
        }
    }
 
    for(int i=0; i<n; i++) {
        d[i] = i;
    }
 
    int ans = -1;
 
 
    //모든 경로 탐색
    do {
        int sum = 0;
        bool ok = true;
 
 
        //첫 번째 도시부터 마지막 도시까지의 비용을 더해준다.
        for(int i=0; i<n-1; i++) {
 
            //비용이 0인 경우, 즉 경로가 존재하지 않는 경우에는 ok를 false로 바꿔주고 break
            if(w[d[i]][d[i+1]] == 0) {
                ok = false;
                break;
            }
 
            sum += w[d[i]][d[i+1]];
        }
 
 
        //위에서 모든 경로가 존재하고(ok == true), 다시 마지막 도시에서 첫 번재 도시로 경로가 존재하는 경우
        //sum에 마지막 도시에서 첫 번째 도시로 가는 비용을 더해주고 최소값과 비교해준다.
        if(ok && w[d[n-1]][d[0]] != 0) {
            sum += w[d[n-1]][d[0]];
            if(ans == -1 || ans > sum) {
                ans = sum;
            }
        }
 
    } while(next_permutation(d.begin(),d.end()));
 
    cout << ans;
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 6603. 로또  (0) 2019.06.20
[BOJ] 10971. 외판원 순회2 (DFS 풀이)  (0) 2019.06.20
[BOJ] 10974. 모든 순열  (0) 2019.06.20
[BOJ] 9095. 1, 2, 3 더하기  (0) 2019.06.20
[BOJ] 6588. 골드바흐의 추측  (0) 2019.06.18

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

 

10974번: 모든 순열

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

www.acmicpc.net

N의 범위가 (1 ≤ N ≤ 8) 이므로 다음 순열을 구해서 모든 순열을 구할 수 있다.

java에서는 next permutaion함수를 직접 구현해줬어야 했는데

c++은 라이브러리가 있어서 좋다...ㅠㅠ

그냥 next_permutation을 써주면 된다...!!

 

next_permutation을 사용할 때는 do while로 사용해줘야 한다. 무조건 한 번은 실행되어야 하기 때문.

그리고 넥퍼뮤 돌릴 자료구조는 벡터를 사용한다.

넥퍼뮤 while문이 돌아갈 때마다 현재 배열을 순차적으로 출력해주면 끝!

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> a;
 
    for(int i=0; i<n; i++) {
        a.push_back(i+1);
    }
 
    do {
        for(int i=0; i<n; i++) {
            cout << a[i] << ' ';
        }
        cout << '\n';
    } while(next_permutation(a.begin(),a.end()));
 
    return 0;
}
Colored by Color Scripter

 

 
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 10971. 외판원 순회2 (DFS 풀이)  (0) 2019.06.20
[BOJ] 10971. 외판원 순회2  (0) 2019.06.20
[BOJ] 9095. 1, 2, 3 더하기  (0) 2019.06.20
[BOJ] 6588. 골드바흐의 추측  (0) 2019.06.18
[BOJ] 2609. 최대공약수와 최소공배수  (0) 2019.06.14

+ Recent posts

티스토리툴바