[9466] 텀 프로젝트

2023. 8. 8. 22:53· PS/DFS, BFS
728x90

https://www.acmicpc.net/problem/9466

 

9466번: 텀 프로젝트

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을

www.acmicpc.net

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int T;
int n;
vector<int> student;
vector<bool> visited;
vector<bool> group;
int ans;

void dfs(int start){
	visited[start] = true;
	int next = student[start];

	if(!visited[next]){
		dfs(next);
	}

	else if(!group[next]){
		while(1){
			if(next != start){
				next = student[next];
				ans++;
			}
			else{
				break;
			}
		}
		ans++; // 자기 자신

		/* 다른 코드
		for (int i = next; i != node; i = graph[i]) {
			cnt++;
		}
		cnt++;
		*/
	}

	group[start] = true;
}

int main(void){
	cin >> T;
	
	for(int i=0; i<T; ++i){
		cin >> n;
		student.resize(n+1);
		group = vector<bool>(student.size(), false);
		visited = vector<bool>(student.size(), false);
		ans = 0;
		
		for(int j=1; j<=n; ++j){
			cin >> student[j];
		}
		
		for(int k=1; k<=n; ++k){
			if(!visited[k]){
				dfs(k);
			}
		}

		cout << n-ans << '\n';
	}

	return 0;
}

dfs 문제이다.

문제의 표를 해석하다 보면 그래프 문제라는 걸 확인할 수 있다.

처음엔 num vector도 dfs인자에 받아서 num벡터에 여태까지 탐색한 수를 저장하고 만약 num벡터에 저장되어 있는 수를 다시 방문하면 그 수부터 그룹으로 묶는 알고리즘을 짰었는데 시간초과가 났었다.

결국엔 위의 코드와 같이 벡터 없이 while문을 활용해서 짜주었다.

다른 코드들을 보면 for문으로도 해결하던데 저렇게 하면 나같은 경우엔 헷갈려서 while문으로 짜주었다.

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'PS > DFS, BFS' 카테고리의 다른 글

[16234] 인구 이동  (0) 2023.07.18
[16236] 아기 상어  (0) 2023.07.13
[14503] 로봇 청소기  (0) 2023.06.19
[9205] 맥주 마시면서 걸어가기  (0) 2023.06.18
[2573] 빙산  (0) 2023.06.18
'PS/DFS, BFS' 카테고리의 다른 글
  • [16234] 인구 이동
  • [16236] 아기 상어
  • [14503] 로봇 청소기
  • [9205] 맥주 마시면서 걸어가기
프레딕
프레딕
250x250
반응형
프레딕
소소한 해킹 블로그
프레딕
전체
오늘
어제
  • 분류 전체보기 (241)
    • etc (1)
    • PS (72)
      • Greedy (4)
      • DFS, BFS (16)
      • DP (14)
      • Stack, Queue (2)
      • 재귀 (10)
      • 이분 탐색 (1)
      • 문자열 (4)
      • 분할 정복 (2)
      • 기타 알고리즘 (19)
    • Book Review (5)
      • 알고리즘 문제 해결 전략 (3)
      • Clean Code (1)
      • The Programatic Programmer (1)
    • Web Hacking (110)
      • Webhacking.kr (42)
      • DreamHack (38)
      • Information (18)
      • Los Rubiya (1)
      • WriteUp (11)
    • Web3 (24)
      • The Ethernaut (22)
      • Information (2)
    • Reversing (18)
      • Reversing.kr (4)
      • DreamHack (3)
      • Information (11)
    • Pwnable (3)
      • DreamHack (2)
    • Misc (1)
      • PyJail (1)
    • Network (6)
    • Dev (1)
      • Flask (1)

블로그 메뉴

  • 홈
  • 태그

공지사항

인기 글

태그

  • 시간복잡도
  • 알고리즘
  • Algorithm

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
프레딕
[9466] 텀 프로젝트
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.