일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 삼성코딩테스트
- BFS
- DP문제
- 임베디드 딥러닝
- 코테 문제
- 초소형머신러닝
- 자료구조
- TensorFlow Lite
- 그리디
- 컴퓨팅사고
- sort
- bfs문제
- 삼성역량테스트
- 삼성코테
- tinyml
- 알고리즘
- 코테
- tflite
- 삼성역테
- 포스코 AI교육
- DP
- dfs
- MCU 딥러닝
- 포스코 교육
- 다이나믹프로그래밍
- 코딩테스트
- dfs문제
- 포스코 ai 교육
- 딥러닝
- 영상처리
- Today
- Total
코딩뚠뚠
[백준문제풀이] 10451 순열사이클 본문
풀이 일시 : 2020-10-13
문제 :
1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면
1 2 3 4 5 6 7 8
3 2 7 8 1 4 5 6
와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.
순열을 배열을 이용해
1 … i … n
π1 … πi … πn 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.
Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.
N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.
입력 :
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.
ex)
2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8
출력 :
각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.
ex)
3
7
풀이 :
dfs, 또는 bfs로 풀이가능하다. 그래프에 연결된 인자가 다시 자신에게로 돌아오면 순열사이클로 볼 수 있다. visit을 true로 만들어주고 count를 +1 해 주어 순열 사이클의 갯수를 구할 수 있다.
memset을 이용하여 테스트케이스마다 초기화해준다.
[기본문제풀이] BFS 너비우선탐색
풀이 일시 : 2020-08-30 BFS : 탐색 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것. 그 중 한 방법인 너비우선탐색은 루트 노드에서 시작해서 인접한 노드를 먼저 탐
dbstndi6316.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#define MAX 1001
using namespace std;
vector <int> v[MAX];
int visit[MAX];
void bfs(int x) {
queue<int>q;
q.push(x);
visit[x] = true;
while (!q.empty()) {
int ex = q.front();
q.pop();
for (int i = 0; i < v[ex].size(); i++) {
int z = v[ex][i];
if (visit[z] == 0) {
visit[z] = true;
q.push(z);
}
else if (z == x) {
visit[z] = true;
}
}
}
}
int main() {
int T, N;
int count=0;
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N;
for (int j = 1; j <= N; j++) {
int x;
cin >> x;
v[j].push_back(x);
}
for (int i = 1; i <= N; i++) { //순열사이클이 몇개인지 테스트한다. 모든 노드를 번갈아가며 검사
if (!visit[i]) {
bfs(i);
count++;
}
}
printf("%d\n", count);
//초기화
for (int i = 1; i <= N; i++) {
v[i].clear(); //벡터를 초기화해준다.
}
count = 0;
memset(visit, 0, sizeof(visit)); //테스트케이스를 여러 번 돌려야하므로 visit 을 초기화
}
return 0;
}
참고자료 : memset함수
[개념정리] memset함수
메모리를 조작하는 함수로는 대표적으로 memset, memcpy, memmove, memcmp 등이 있다. 그 중 메모리를 초기화하는 memset을 알아본다. memset함수란 메모리의 내용을 원하는 크기만큼 특정 값으로 세팅할
dbstndi6316.tistory.com
참고자료 : vector container
[개념정리] vector container
vector 란 C++ STL vector는 list계열의 container 종류이다. 자료구조의 스택과 구조가 비슷하다. vector를 생성하면 메모리 heap에 생성되며 동적할당 된다. vector 사용 선언 및 초기화 vector<자료형> 변수.
dbstndi6316.tistory.com
'알고리즘 문제풀이 > 백준문제풀이' 카테고리의 다른 글
[백준문제풀이] 9095 1,2,3더하기 (0) | 2021.01.01 |
---|---|
[백준문제풀이] 1476 날짜 계산 (0) | 2021.01.01 |
[백준문제풀이] 2178 미로 탐색 (0) | 2021.01.01 |
[백준문제풀이] 2331 반복수열 (0) | 2021.01.01 |
[백준문제풀이] 2667 단지번호붙이기 (0) | 2021.01.01 |