티스토리 뷰
9466번: 텀 프로젝트
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을
www.acmicpc.net
풀이
처음에 사이클 체크를 어떻게 해야 하는지 엄청 고민했다...
결국 구글링하여 솔루션들을 참고했다 ㅠ
내가 시도하려는 풀이에선 방문체크 배열이 두 개가 필요함을 알 수 있었다.
- 방문 체크를 할 배열, 완전히 방문이 끝났음을 알리는 배열 두 개의
visited
를 확인할 배열이 필요 visited[n] = false
: 아직 방문안한 곳이므로 DFS 다음 탐색 node는n
visited[n] = true & finished[n] = false
- 방문은 했으나 완전히 방문이 끝나지는 않음 == 처음 시작노드로 돌아온 경우이므로 사이클에 해당됨
- for문을 재귀로 수행하며 사이클에 노드가 몇 개 있는지
cnt
에 저장
- 마지막에
전체 노드 개수 - cnt
를 해주면 정답
코드
import java.io.*; import java.util.*; public class Main { static int T, n, cnt; static final int SIZE = 100010; static int[] arr; static boolean[] visited, finished; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st; T = Integer.parseInt(br.readLine()); while(T-- > 0) { n = Integer.parseInt(br.readLine()); cnt = 0; arr = new int[SIZE]; visited = new boolean[SIZE]; finished = new boolean[SIZE]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken()); for (int i = 1; i <= n; i++) if (!visited[i]) explore(i); bw.write((n - cnt) + "\n"); } br.close(); bw.close(); } public static void explore(int n) { visited[n] = true; int next = arr[n]; if (!visited[next]) explore(next); else if (!finished[next]) { for (int i = next; i != n; i = arr[i]) cnt++; cnt++; } finished[n] = true; } }

'알고리즘' 카테고리의 다른 글
[백준] 1219. 오민식의 고민 (Java) (0) | 2021.07.13 |
---|---|
[백준] 16197. 두 동전 (Java) (0) | 2021.07.12 |
[백준] 1865. 웜홀 (Java) (0) | 2021.07.11 |
[프로그래머스] 코딩테스트 연습 > 해시 (JavaScript) (0) | 2021.03.11 |
[백준] 3055. 탈출 (Java) (0) | 2021.01.24 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 우선순위큐
- form
- 알고리즘
- BFS
- 문자열
- matches
- Validation
- swea
- 시뮬레이션
- 구현
- 이분탐색
- 브루트포스
- 정규식
- 프로그래머스
- dp
- 백트래킹
- regex
- dfs
- 해시
- vue.js
- 다익스트라
- 삼성역테기출
- java
- REACT
- 백준
- web
- CustomHook
- 그래프
- 벨만포드
- BigInteger
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함