# 9466

3개의 포스트

백준 9466

1. 문제 [Gold III] 텀 프로젝트 - 9466 문제 링크 성능 요약 메모리: 400456 KB, 시간: 1756 ms 분류 깊이 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을

2023년 5월 24일
·
0개의 댓글
·

백준 9466 텀 프로젝트

정말 어려운 문제였다. 풀이를 봐도 어려워서 5번 넘게 봤다. 두고두고 보고 복습하기 위해 기록한다. 아이디어 사이클이 존재하고, 사이클 주변에는 사이클로 들어오는 선들이 있는 형태가 된다. O(N^2) 풀이 사이클에 포함된 학생부터 반복문을 돌리게 되면 언젠가는 자기 자신으로 돌아온다. 사이클에 포함되지 않는 학생은 아무리 해도 자기 자신으로 돌아올 수 없다. 즉 최초로 방문한 학생이 자기 자신인지 확인하는 과정 => n번 이내에 자기 자신으로 돌아오는지 확인만 하면 된다. 허나 이 방법은 시간 초과가 날 수 있다. 방문한 노드를 반복해서 방문할 수 있기 때문에 비효율적이다. O(N) 풀이 방문한 노드를 다시 방문하지 않기 위해 방문체크를 넣음 => BFS 활용 풀이

2023년 2월 23일
·
0개의 댓글
·
post-thumbnail

텀 프로젝트

Problem link: https://www.acmicpc.net/problem/9466 트리-like한 그래프가 주어질 때, 사이클에 포함된 노드의 수를 세는 문제로 볼 수 있다. DFS를 진행할 때, 노드 X를 방문하고 노드 Y를 방문하려는데 이미 Y가 방문된 상태라고 해보자. 만약, 노드 Y가 아직 DFS가 완료되지 않은 지점이라면 노드 Y~X사이의 모든 노드는 사이클에 속한다. 적당히 VISIT 배열과 VISTI COUNT, 그리고 방문 이력을 잘 저장해주고 있으면 어렵지 않게 풀 수 있다.

2021년 8월 20일
·
0개의 댓글
·