1. 문제 / 난이도 : Gold Ⅴ
2668번: 숫자고르기
세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절
www.acmicpc.net
2. 풀이 및 코드 설명
단순히 그래프의 순환을 찾아서 출력하는 문제. 순환을 찾기 -> 해당 순환의 첫노드와 마지막 노드까지를 answer 배열에 넣기 -> 다음 순환 찾기의 반복으로 풀 수 있었다.
(1) 순환 찾기
for (int i = 1; i <= N; i++) {
if (!visited[i] && !visited[nums[i]]) checkCycle(i); //현재 노드와 연결된 노드 둘 다 아직 방문한 적이 없는 노드라면 checkCycle
visited[i] = true; //visited 갱신
}- 현재 노드와 연결된 노드를 둘 다 보는 이유는 현재 노드는 당연히 방문한 적이 없어야 하고, 연결된 노드가 이미 방문된 노드라면 앞에서 순환 검사를 이미 끝마쳤다는 소리이기 때문
void checkCycle(int node) {
visited[node] = true; //visited 갱신
int next = nums[node];
//만일 순환이 발생한다면
if (visited[next]) {
addAnswer(next, node);//순환의 처음과 끝을 가지고 addAnswer수행
return;
}
checkCycle(next); //순환이 발생하지 않으면 연결된 다음 노드로 이동
}(2) answer배열에 추가하기
void addAnswer(int start, int goal) {
int current = start;
answer.push_back(current);
// 그래프를 타고 다음 노드로 넘어가며 goal과 같은 노드에 다다르기 전까지 answer 배열에 추가
while (current != goal) {
current = nums[current];
answer.push_back(current);
}
}
3. 전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int nums[101];
bool visited[101];
vector<int> answer;
void addAnswer(int start, int goal) {
int current = start;
answer.push_back(current);
while (current != goal) {
current = nums[current];
answer.push_back(current);
}
}
void checkCycle(int node) {
visited[node] = true;
int next = nums[node];
if (visited[next]) {
addAnswer(next, node);
return;
}
checkCycle(next);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) cin >> nums[i];
for (int i = 1; i <= N; i++) {
if (!visited[i] && !visited[nums[i]]) checkCycle(i);
visited[i] = true;
}
cout << answer.size()<<'\n';
sort(answer.begin(), answer.end());
for (auto& ele : answer) cout << ele << '\n';
}'알고리즘 공부 > Baekjoon' 카테고리의 다른 글
| [백준 4386/Python] 별자리 만들기 (0) | 2020.11.12 |
|---|---|
| [백준 11062/Python] 카드 게임 (0) | 2020.11.12 |
| [백준 16946/Python] 벽 부수고 이동하기4 (0) | 2020.11.06 |
| [백준 2572/Python] 보드게임 (0) | 2020.10.25 |
| [백준 1092/Python] 배 (0) | 2020.10.24 |
