Algorithm 공부 #08 - 탐색(깊이 우선 탐색과 너비 우선 탐색)

 

Algorithm 공부 - 탐색(깊이 우선 탐색과 너비 우선 탐색)

 

 

깊이 우선 탐색(Depth-First-Search)

    ● 그래프 완전 탐색 기법

    ● 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정한 후 최대 깊이까지 탐색을 마친 후 다른 분기로 이동

    ● 노드의 개수를 V, 엣지의 개수를 E라 하면 시간 복잡도는 O(V+E)

    ● 단절점 찾기, 단절선 찾기, 위상 정렬, 사이클 찾기 등의 문제에 활용됨

    ● 탐색 방법

       1. 인접 리스트로 그래프 표현하기 + 방문 여부를 체크할 배열 만들기 + 스택에 시작 노드 삽입하기

       2. 스택에서 노드를 POP한 후 그 노드와 인접 노드 삽입하기, 없다면 다음 노드로 이동

       3. 스택 자료구조에 값이 없을 때까지 계속해서 반복

 

 

 

백준 2751번 수 정렬하기2

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

11724번: 연결 요소의 개수

 

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

static vector<vector<int>>A; // 그래프를 인접 리스트로
static vector<bool>visit; // 방문 여부 체크 배열
void dfs(int v); // dfs함수
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	A.resize(N + 1);
	visit = vector<bool>(N + 1, false); // false로 초기화

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		A[u].push_back(v); // 양방향 그래프이므로
		A[v].push_back(u); // 각각 삽입
	}

	int count = 0; //결과값 출력 배열

	for (int i = 1; i < N + 1; i++) {
		if (!visit[i]) { // 방문하지 않은 점이므로
			count++; // 연결 요소 개수 증가시켜주고
			dfs(i); // dfs시작
		}

	}
	
	cout << count;
}

void dfs(int v) {
	
	if (visit[v]) // 이미 방문한 점이라면 탐색할 필요가 없음
		return;
	
	visit[v] = true; //방문 표시해주기
	
	for (int i : A[v]) {
		if (visit[i] == false) // 방문하지 않은 점이라면 탐색
			dfs(i); // 그 점도 dfs
	}

}

 

 

백준 2023번 신기한 소수

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

2023번: 신기한 소수

 

※ dfs로 탐색하면서 소수를 계속 만들어내야함 ※

● number와 자릿수를 인수로 가지는 dfs함수 만들기

● dfs함수

    자릿수 == N이고 N이 소수라면 N을 출력하고 아니라면 return

    for문을 돌려서 num*10+i로 숫자를 계속 만들어줌(i는 1,3,5,7,9만 => 뒤에 짝수면 소수가 아님)

    그래서 만든 숫자가 소수라면 dfs에 인수로 만든 숫자와 자릿수+1을 넘겨줌

● 소수 판정 함수

    for문을 2~num/2까지 돌려서 num을 i로 나눈 나머지가 0이 존재하면 false를,  그게 아니라면 true를 리턴

 

#include<iostream>
using namespace std;

int N;
void dfs(int num, int jari);
bool isprime(int number);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	dfs(2, 1);
	dfs(3, 1);
	dfs(5, 1);
	dfs(7, 1);

}

void dfs(int num, int jari) {

	if (jari == N) { // 만약 n자리만큼 자릿수를 만들었다면
		if (isprime(num)) // 소수라면 출력
			cout << num << '\n';
		return; // 아니면 그냥 return
	}

	for (int i = 1; i <= 9; i += 2) {
		int number = 10 * num + i;
		if (isprime(number)) // 새로 만든 수가 소수라면
			dfs(number, jari+1); // dfs
	}
}

bool isprime(int num) {
	for (int i = 2; i <= num / 2; i++) {
		if (num % i == 0) // 소수가 아님
			return false;
	}
	return true;
}

 

 

백준 13023번 ABCDE

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

13023번: ABCDE

 

※ 재귀의 깊이가 5이상이 되어야 한다는 점이 핵심 ※

● 인접 리스트와 방문 배열 생성 도착 여부 확인 변수(arrive)를 false로 초기화

● for문을 0~N-1까지 돌리고 dfs함수에는 현재 노드와 재귀함수의 깊이를 넘겨줌

● dfs함수

   재귀의 깊이가 5가 되거나 arrive값이 true라면 arrive를 true로 바꾸고 return

   그게 아니라면 visit[현재 정점 위치)를 true로 바꾸고 

   반복문을 돌려서 방문하지 않은 배열일 때 i와 depth+1을 넘겨줌

   반복문이 끝나고 방문했던 배열을 다시 false처리 해주는 것이 중요(이상하게 탐색될 수 있음)

● arrive값이 true라면 성공한 것이므로 1을, 그렇지 않다면 0을 출력

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

static vector<vector<int>>A; // 인접 리스트
static vector<bool>visit; // 방문 배열
void dfs(int now, int depth); // depth가 5가 되는게 핵심
static bool arrive;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	arrive = false; // 방문 확인 변수
	A.resize(N);
	visit = vector<bool>(N, false);

	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		A[s].push_back(e);
		A[e].push_back(s);
	}

	for (int i = 0; i < N; i++) {
		dfs(i, 1); // 정점과 depth를 넘겨줌
		if (arrive) // 만약 도착했다면 반복문 종료
			break;
	}
	if (arrive) // 친구 관계가 있음
		cout << 1;
	else
		cout << 0;
}

void dfs(int now, int depth) {

	if (depth == 5 || arrive) {
		arrive = true; // depth==5로 if문이 참인 경우
		return; // 더 이상 볼 필요가 없으므로 returna
	}
		
	visit[now] = true; // 방문하지 않은 배열 방문으로 체크

	for (int i : A[now]) {
		if (!visit[i])
			dfs(i, depth + 1); // 방문하지 않은 배열에 i랑 depth를 +1인		                       // 값을 해주어서 depth가 5일 떄까지
	}

	visit[now] = false; // false처리를 하지 않으면 탐색 순서가 달라질 수 있음

}

 

 

 

백준1260번 DFS와 BFS

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

1260번: DFS와 BFS

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

void bfs(int node);
void dfs(int node);
static vector<vector<int>>A;
static vector<bool>visit;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M,start;
	cin >> N >> M>>start;

	A.resize(N+1);
	visit = vector<bool>(N + 1, false);

	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		A[s].push_back(e);
		A[e].push_back(s);
	}

	for (int i = 1; i <= N; i++)
		sort(A[i].begin(), A[i].end());

	dfs(start);
	cout << '\n';
	fill(visit.begin(), visit.end(), false);
	bfs(start);

}

void dfs(int node) {
	cout << node << " ";
	visit[node] = true;

	for (int i : A[node]) {
		if (!visit[i])
			dfs(i);
	}
}

void bfs(int node) {
	
	queue<int>myqueue;
	myqueue.push(node);
	visit[node] = true;

	while (!myqueue.empty()) {
		int cur = myqueue.front();
		myqueue.pop();
		cout << cur << " ";
		for (int i : A[cur]) {
			if (!visit[i]) {
				visit[i] = true;
				myqueue.push(i);
			}
		}
	}
}

 

백준 2178번 미로 탐색

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

2178번: 미로 탐색

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

int A[101][101];
int visit[101][101];
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < M; j++) {
			A[i][j] = s[j] - '0';
		}
	}

	queue<pair<int, int>>myqueue;
	myqueue.push({ 0,0 });

	while (!myqueue.empty()) {
		pair<int, int>cur = myqueue.front();
		myqueue.pop();
		for (int i = 0; i < 4; i++) {
			int mx = cur.first + dx[i];
			int my = cur.second + dy[i];
			
			if (mx<0 || my <0  || mx>=N || my >= M)
				continue;
			if (visit[mx][my]||A[mx][my]==0)
				continue;
			myqueue.push({ mx,my });
			visit[mx][my] = visit[cur.first][cur.second] + 1;
		}
	}
	cout << visit[N-1][M-1]+1;
}

 

백준 1167번 트리의 지름

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

1167번: 트리의 지름

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

typedef pair<int, int> edge;
static vector < vector <edge> > A;
static vector<bool> visited;
static vector<int> m_distance;
void BFS(int node);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    A.resize(N + 1);

    for (int i = 0; i < N; i++) {
        int S;
        cin >> S;
        while (true)
        {
            int E, V;
            cin >> E;
            if (E == -1)break;
            cin >> V;
            A[S].push_back(edge(E, V));
        }
    }

    m_distance = vector<int>(N + 1, 0);
    visited = vector<bool>(N + 1, false);
    BFS(1);
    int Max = 1;
    for (int i = 2; i <= N; i++) {
        if (m_distance[Max] < m_distance[i])
            Max = i;
    }
    fill(m_distance.begin(), m_distance.end(), 0); 
    fill(visited.begin(), visited.end(), false); 
    BFS(Max);
    sort(m_distance.begin(), m_distance.end());
    cout << m_distance[N] << "\n";
}


void BFS(int index) {  
    queue<int> myqueue;
    myqueue.push(index);
    visited[index] = true;

    while (!myqueue.empty()) {
        int now_node = myqueue.front();
        myqueue.pop();
        for (edge i : A[now_node]) {
            if (!visited[i.first]) {
                visited[i.first] = true;
                myqueue.push(i.first);
                m_distance[i.first] = m_distance[now_node] + i.second;
            }
        }
    }
}