백준 9466 텀 프로젝트(Java,자바)
이번에 풀어본 문제는
백준 9466번 텀 프로젝트 입니다.
📕 문제 링크
❗️코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int answer;
static int [] select;
static boolean [] isDone;
static boolean [] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while(t-- > 0)
{
answer = 0;
int N = Integer.parseInt(br.readLine());
select = new int[N+1];
isDone = new boolean[N+1];
visited = new boolean[N+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++)
{
int next = Integer.parseInt(st.nextToken());
select[i] = next;
}
for(int i = 1; i <= N; i++)
{
if(!isDone[i]) dfs(i);
}
sb.append(N-answer).append("\n");
}
System.out.print(sb);
}
static void dfs(int n)
{
visited[n] = true;
int next = select[n];
if(!visited[next]) dfs(next);
else
{
if(!isDone[next])
{
answer++;
isDone[next] = true;
while(next != n)
{
answer++;
next = select[next];
isDone[next] = true;
}
}
}
isDone[n] = true;
}
}
📝 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int answer;
static int [] select;
static boolean [] isDone;
static boolean [] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while(t-- > 0)
{
answer = 0;
int N = Integer.parseInt(br.readLine());
select = new int[N+1];
isDone = new boolean[N+1];
visited = new boolean[N+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++)
{
int next = Integer.parseInt(st.nextToken());
select[i] = next;
}
for(int i = 1; i <= N; i++)
{
if(!isDone[i]) dfs(i);
}
sb.append(N-answer).append("\n");
}
System.out.print(sb);
}
static void dfs(int n)
{
visited[n] = true;
int next = select[n];
if(!visited[next]) dfs(next);
else
{
if(!isDone[next])
{
answer++;
isDone[next] = true;
while(next != n)
{
answer++;
next = select[next];
isDone[next] = true;
}
}
}
isDone[n] = true;
}
}
📝 풀이
N명의 학생이 한명 씩 팀원을 지목할 때, 사이클이 형성되면 같은팀으로 간주하는 문제입니다. 자신을 선택할 수 있습니다.
한명씩만 선택할 수 있기 때문에 1차원 배열로 각 학생의 선택을 담아주고, 방문배열 두개를 활용하여 dfs탐색을 진행하면 됩니다.
방문한 노드이지만(visited) 아직 탐색이 종료되지 않았다면(!isDone) 방문의 끝, 즉 사이클이 형성된 것이므로, 선택된 사이클의 모든 팀원을 카운트해주면 됩니다.
📜 후기
조건이 간단해서 쉬울거라 생각했는데, 생각보다 많이 어려웠습니다. 두 개의 방문배열로 사이클 여부를 판단하는 것을 이해하는 데 시간이 조금 걸렸던 문제입니다.
Author And Source
이 문제에 관하여(백준 9466 텀 프로젝트(Java,자바)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jh5253/백준-9466-텀-프로젝트Java자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)