티스토리 뷰
2668번: 숫자고르기
세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절
www.acmicpc.net
아이디어
숫자들을 정점으로 생각하면 뽑은 숫자들의 집합이 일치한다 => 사이클이 있다고 볼 수 있다.
사이클을 검출하는 방법 : DFS
DFS를 돌다가 DFS가 아직 다 돌지않은 정점을 만나게 되면 사이클이 있다고 생각할 수 있다.
(다만 방문여부와는 별개로 생각해줘야한다. 처음 방문하는 정점도 DFS를 다 돌진 않은 상태니까)
DFS를 돌면서 자신이 이전에 방문한 정점을 저장해준다면 DFS가 다 안돈 정점부터
차례대로 자기 자신을 만날 때 까지 정답배열에 넣어주면 답을 구할 수 있다.
void dfs(int cur){
if(vis[cur]){
// 만약 방문한 적이 있지만 해당 정점이 DFS를 다 돈 상황이라면 더 들어가주지 않아도된다.
if(fin[cur]) return;
else{
// 하지만 해당 방문한 적이 있지만 DFS를 다 안돌았다면 onCase라는 것이다.
// 해당 정점부터 정답에 넣어주고 현재 정점이 나올 때까지 정점들을 넣어준다.
ans.push_back(cur);
int i=par[cur];
while(i!=cur){
ans.push_back(i);
i=par[i];
}
return;
}
}
vis[cur]=1;
for(auto i:adj[cur]){
if(!fin[i]){
par[i]=cur;
dfs(i);
}
}
// *DFS가 끝났다는 것을 반드시 써주자*
fin[cur]=1;
}
'Algorithms & PS' 카테고리의 다른 글
[최소 스패닝 트리] 프림 알고리즘 (0) | 2021.11.16 |
---|---|
[20040] Union-find로 그래프 상의 사이클 검출 (0) | 2021.11.16 |
[22991] 수요응답형 버스 (박제용) (2) | 2021.10.18 |
선분 교차 판별법 (0) | 2021.08.28 |
[2342] Dance Dance Revolution (0) | 2021.06.13 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday