이것 저것 &

문제링크:https://www.acmicpc.net/problem/2668

dfs문제입니다.

N의 범위가 100밖에 안되기 때문에 모든 인자에 대하여 사이클 여부를 확인하는 식으로 진행해도 시간초과가 발생하지 않습니다.

1. 각 인덱스마다 해당 값을 사이클을 가지는지 확인합니다.

        1) 방문여부, start와 current의 위치가 같다면 해당값을 포함합니다.

        2) 방문하지 않았다면 방문을 표시하고, arr[current] 로 이동해서 확인합니다.

2. 사이클을 가진다면 해당값을 result배열에 포함합니다. (이때 인덱스가 작은값부터 포함하기 때문에 정렬할 필요가 없습니다.)

정답코드입니다.

#include <iostream>
#include <cstring>
using namespace std;

int n = 0, result_index = 0;
int arr[101] = { 0 };
int visited[101] = { 0 };
int result[101] = { 0 };

void dfs(int current,int start) {
	if (visited[current]) {
		if (current == start)
			result[result_index++] = start;
	}
	else {
		visited[current] = 1;
		dfs(arr[current], start);
	}

}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	
	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		dfs(i, i);
	}

	cout << result_index << endl;
	for (int i = 0; i < result_index; i++)
		cout << result[i] << endl;
}

문제링크:https://www.acmicpc.net/problem/2583

전형적인 dfs 문제입니다. (bfs로도 풀이는 가능합니다.)

분리된 공간의 넓이를 출력하면 되는 문제입니다.

위와같이 되어있어서 사각형을 판단하는데 어려움을 가지실 수 있습니다.

하지만 저건 그냥 일반점으로 보아도 무방합니다.

사각형 하나를 그냥 점으로 보세요.

보이시나요?

0~m, 0~n까지입니다. 

해당위치들을 표시해주고 dfs를 통해서 몇번 탐색이 가능한지 확인하고 결과를 도출합니다.

정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int m = 0, n = 0, k =0;
int arr[102][102] = { 0 };
int x, y, x2, y2;

int result[101] = { 0 };
int sum = 0, result_index = 0;
int x_dep[4] = { 1,-1,0,0 };
int y_dep[4] = { 0, 0,-1,1 };

void dfs(int yy, int xx) {
	
	arr[yy][xx] = -1;
	sum++;

	for (int i = 0; i < 4; i++)
	{
		int yyy = yy + y_dep[i];
		int xxx = xx + x_dep[i];

		if (yyy >= 0 && yyy < m && xxx >= 0 && xxx < n) {
			if (arr[yyy][xxx] == 0)
				dfs(yyy, xxx);
		}

	}
	
}
int main() {
	cin >> m >> n >> k;

	for (int i = 0; i < k; i++) {
		cin >> x >> y >> x2 >> y2;

		for (int j = y; j < y2; j++) {
			for (int u = x; u < x2; u++) {
				arr[j][u] = 1;
			}
		}
	}


	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 0) {
				sum = 0;
				dfs(i, j);
				result[result_index++] = sum;
			}
		}
	}

	sort(result, result + result_index);

	cout << result_index << endl;
	for (int i = 0; i < result_index; i++)
		cout << result[i] << " ";
	cout << endl;
}

저는 dfs가 가장 노력하는만큼 실력이 늘어나는 알고리즘이라고 생각합니다. :0

꼭 직접 작성해보세요. 화이팅! 

문제링크: https://www.acmicpc.net/problem/11403

기본적인 dfs, bfs 문제였습니다.

숫자범위도 n=100까지이고 dfs를 사용해도 지장이 없을 것 같아 직관적인 dfs 알고리즘을 사용해 구현하였습니다.

반복문을 통해 arr[i][j]=1일땐 dfs를 호출해 해당줄에서 방문이 가능한 도시를 체크합니다.

방문 이후에는 통합시켜주며 마무리합니다.

#include <iostream>
using namespace std;
int n = 0;
int arr[101][101] = { 0 };
bool visited[101];

void dfs(int y, int x) {
	
	for (int i = 1; i <= n; i++) {
		if (arr[x][i] == 1 && !visited[i]) {
			visited[i] = 1;
			dfs(y, i);
		}	
	}
	
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			cin >> arr[i][j];
			
	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= n; j++)
			visited[j] = 0;

		for (int j = 1; j <= n; j++)
			if (arr[i][j] == 1) {
				visited[j]=1;
				dfs(i, j);
			}

		for (int j = 1; j <= n; j++) {
			if (visited[j] == 1)
				arr[i][j] = 1;
		}
	}
	
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << endl;
	}
}

밑에는 dfs, bfs 를 안쓰고 O(n^3)만에 끝내는 컴팩트한 방법입니다.

#include <iostream>
using namespace std;
int main(){
	int n; 
	cin >> n;
	bool map[101][101] = {};
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++) cin >> map[i][j];
	}
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(map[i][k] && map[k][j]) map[i][j] = true;
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++) cout << map[i][j] << ' ';
		cout << '\n';
	}
}