BOJ 15462 - The Bovine Shuffle(usaco silver, dfs)

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

 

int arr[] : 각 위치에 소가 몇마리 있는지

int odr[] : 다음 위치 가리키는 배열

int mcnt[] : 각 위치마다 배치됐던 소의 최소값.

 

초기상황 : 배열에 소가 1마리씩 들어있음

 

위치에 따라 다음 이동 위치가 주어지기 때문에 dfs, bfs를 생각했으나 현재 상태를 어떻게 표현해야할지 감이 안와서 이런 생각을 해봤다. "무한히 시뮬레이션 하는데 제한시간이 주어졌다는 것은 반복되는 상태가 생긴다는 뜻이고, bfs dfs로 풀 수 있다는 건 시뮬 돌리다보면 시간 안에 답이 나온다는 뜻이니까 시간에 맞게 최대한 시뮬 돌려보면 나오지않을까?"

 

shuffle 1회에 O(1e5), 전체 O(le8)안에 끝내야 하므로 시뮬을 1e3회 돌려봤다.

 

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1e5 + 2;
const int INF = 1e9;

int odr[MAX], mcnt[MAX], arr[MAX];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> odr[i];
	fill(mcnt, mcnt + MAX, 1);
	fill(arr, arr + MAX, 1);

	int tc = 1000;
	while (tc--) {
		int tarr[MAX] = { 0 };
		for (int i = 1; i <= n; i++) 
			tarr[odr[i]] += arr[i];
		for (int i = 1; i <= n; i++) {
			arr[i] = tarr[i];
			mcnt[i] = min(mcnt[i], arr[i]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) if (mcnt[i] != 0)ans++;

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

일단 ac맞긴 했지만 너무 조잡하므로 kks227님 코드를 찾아봤다

 

 

 

@kks227 kks227 유사코
88c96a5 on 7 Jan
28 lines (25 sloc)  527 Bytes
  
#include <cstdio>
using namespace std;
const int MAX = 100000;

int N, next[MAX], result;
bool visited[MAX], finished[MAX];

void dfs(int curr){
	visited[curr] = true;
	if(!visited[next[curr]]) dfs(next[curr]);
	else if(!finished[next[curr]]){
		for(int i = next[curr]; i != curr; i = next[i])
			++result;
		++result;
	}
	finished[curr] = true;
}

int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i){
		scanf("%d", next+i);
		--next[i];
	}
	for(int i = 0; i < N; ++i)
		if(!visited[i]) dfs(i);
	printf("%d\n", result);
}

소 하나 하나 추적해나가는데, 1번 소의 이동경로를 dfs해서 사이클이 생기면 사이클이 생긴 위치 모두 항상 소가 있게 된다.(초기에 모든 위치에 소가 있었기 떄문에 가능한 것임.)