public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
이 문제에 핵심
1. 팀원이 되려면 모든 학생이 되고 싶은 학생이 포함되어야 합니다.(즉, 사이클이 이루어져야 한다.)
2. 각 학생들은 팀이 되고 싶은 학생이 1명 존재하며, 자기 자신일 수 도 있습니다.
3. 모든 팀을 만들었을 때 팀에 속하지 않은 인원 수를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. DFS탐색으로 사이클 존재하는지 탐색하고 사이클에 속하지 않은 인원을 구분합니다.
3. 탐색이 끝난 뒤 사이클에 속하지 않은 인원의 수를 결과로 출력합니다.
DFS 탐색!
사이클이 존재할 때!
DFS탐색 중 방문했었던 정점으로 이동할 때 :사이클 발생
사이클이 발생하면
해당 사이클에 속하는 정점을 모두 사이클에 포함된다고 설정!
포함되는 것을 설정할 때에는 DFS를 재귀로 구현하였기 때문에 다시 돌아오기 때문에 사이클 발생한 정점까지 되돌아가는 동안 모두 사이클에 포함되는 것으로 표현할 수 있습니다.
이후 되돌아갈 때 사이클에 포함되지 않는 정점들은 더 탐색해도 사이클에 포함될 수 없기 때문에 다음 DFS 탐색에 포함되지 않도록 설정합니다.
cycle[] 배열이 있을 때
0 : 탐색하지 않은 정점
1 : 사이클에 포함되는 정점
2 : 사이클에 포함되지 않는 정점
구분하였습니다.
이러한 방식으로 모든 정점에 대하여 탐색 가능할 때 DFS탐색하여 사이클에 포함되지 않는 정점의 개수를 구하였습니다.
예제입력이 진행되는 과정을 살펴보시면 이해하시기 편하실 것입니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
※1번째 테스트케이스만 진행과정을 보여드리겠습니다.
N : 7
2. DFS탐색으로 사이클 존재하는지 탐색하고 사이클에 속하지 않은 인원을 구분합니다.
되고 싶은 팀원을 자신으로 적은 학생은 자신이 하나의 팀으로 속함!(사이클 존재)
자신을 찍은 { 3 } 번 학생은 1개의 팀으로 설정!
cycle[3] = 1
DFS 탐색 진행!
1번 학생을 시작으로 탐색!
3번 학생은 이미 사이클이 존재하기 때문에 X
1번 학생은 사이클에 포함될 수 없다!
cycle[1] = 2
2번 학생 탐색
1번 학생은 사이클에 포함 될 수 없기 때문에 2번 학생은 1번 학생과 팀을 만들 수 없습니다.
2번 학생은 사이클에 포함될 수 없다!
cycle[2] = 2
4번 학생 탐색!
4번 학생을 시작으로 4 ▶ 2 ▶ 6 ▶ 4 사이클 발생!
재귀를 통해 돌아갈 때 사이클이 발생한 지점까지는 모두 사이클에 포함!
cycle[6] = 1
cycle[7] = 1
cycle[4] = 1
5번 학생 탐색!
3번 학생은 이미 사이클이 존재하기 때문에 X
5번 학생은 사이클에 포함될 수 없다!
cycle[5] = 2
3. 탐색이 끝난 뒤 사이클에 속하지 않은 인원의 수를 결과로 출력합니다.
사이클에 속하지 않는 인원 : cycle[i] == 2인 인원
{1, 2, 5}
3결과로 출력합니다.
BufferedReader를 사용하여 입력되는 정보를 저장합니다.
StringTokenizer를 이용하여 학생들에 대한 정보를 띄어쓰기 기준 나누었습니다.
팀을 하고 싶은 학생을 자신으로 선택한 학생은 각각의 사이클(팀)으로 만들었습니다.
탐색이 가능한 학생들을 기준으로 dfs함수를 실행하여 사이클 존재 유무를 확인합니다.
탐색이 종료되었을 때 사이클에 포함되지 않는 학생들을 결과로BufferedWriter에 저장하였습니다.
BufferedWriter에 저장된 결과값을 출력하였습니다.
dfs함수는 cycle[nxt] == 2이면 내가 원하는 학생은 사이클에 포함되지 않으므로 자동적으로 자신도 사이클에 포함되지 않습니다.
dfs함수는 사이클이 형성되면 사이클 기준 학생을 기준으로 돌아가면서 사이클에 있는 학생들을 저장합니다.
결과코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
static int[] graph; //각 학생이 팀원이 되고 싶은 친구 저장 배열
static boolean[] visited; //DFS탐색시 방문 확인 배열
static int[] cycle; //학생 사이클 관련 배열
static int point = 0; //사이클 발생한 지점 변수
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
//T만큼의 테스트케이스 진행
for(int tc = 1;tc<=T;tc++) {
int N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine()," ");
visited = new boolean[N+1];
cycle = new int[N+1];
graph = new int[N+1];
//각 학생 팀이 되고 싶은 학생 번호 저장
for(int i=1;i<=N;i++) {
int nxt = Integer.parseInt(st.nextToken());
if(i == nxt) //자기 자신일 때 사이클 생성 완료!
cycle[i] = 1;
graph[i] = nxt;
}
//탐색되지 않은 인원들 DFS 탐색 진행!
for(int i=1;i<=N;i++) {
if(cycle[i] != 0)
continue;
point = 0;
dfs(i);
}
int answer = 0;
//사이클에 포함되지 않은 학생 수 구하기
for(int i=1;i<=N;i++)
if(cycle[i] == 2)
answer++;
bw.write(String.valueOf(answer)); //학생 수 BufferedWriter 저장
bw.newLine();
}
bw.flush(); //결과 출력
bw.close();
br.close();
}
//DFS 탐색을 통해 사이클이 존재하는지 확인 및 사이클 포함되는 학생 구분 함수
static boolean dfs(int idx) {
int nxt = graph[idx];
//팀을 하고싶은 학생이 사이클에 포함되지 않은 학생일 때
if(cycle[nxt] != 0) {
cycle[idx] = 2;
return false;
}
//사이클이 만들어질 때
if(visited[nxt]) {
cycle[idx] = 1; //현재 학생 사이클 포함 학생 저장
point = nxt; //사이클 형성되는 기준 학생 설정
return true;
}
//팀을 하고 싶은 학생 탐색
visited[idx] = true;
boolean flag = dfs(nxt);
visited[idx] = false;
//사이클이 형성된 영역일 때
if(flag) {
cycle[idx] = 1; //사이클 포함 학생으로 저장
if(idx == point) //기준점일 때 이전 학생들은 사이클 포함 X
return false;
}else
cycle[idx] = 2; //사이클 포함하지 않는 학생일 때
return flag;
}
}
댓글