2024 - 07 - 12 C++ 코딩테스트 10주완성 D+17

DFS 와 BFS 비교

 

시간복잡도는 인접리스트로 이루어졌다면 O(V+E) 고 인접행렬로 이루어져 있다면
O(V^2) 가 되는 것은 동일하며 다음과 같은 차이가 있습니다.

 

DFS -> 메모리를 덜 씀. 절단점 등 구할 수 있음. 코드가 좀 더 짧으며 완전 탐색의 경우에 많이 씀

BFS -> 메모리를 더 씀. 가중치가 같은 그래프내에서 최단거리를 구할 수 있음. 코드가 더 김

"퍼져나간다. 탐색한다"라는 단어가 문제에 있을 시 DFS, BFS를 떠올리면 된다.

 

---

트리순회

트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말합니다.

이를 노드를 방문하는 순서에 따라 전위순회, 중위순회, 후위순회로 나누어져있습니다.

 

후위순회 : 자식들 노드를 방문하고 자신의 노드를 방문하는 것을 말합니다.

전위순회 : 먼저 자신의 노드를 방문하고 그 다음 노드들을 방문하는 것을 말합니다.

중위순회 : 왼쪽 노드를 먼저 방문 그다음의 자신의 노드를 방문하고 그 다음 오른쪽 노드를 방문하는 것을 말합니다.

 

---

연습코드

#include <bits/stdc++.h>

using namespace std;

vector<int> a[10];
bool visited[10];

//전위순회
void preorder(int node)
{
        if (visited[node] == false)
        {
            visited[node] = true;
            cout << node << " ";
            if (a[node].size() == 1)
            preorder(a[node][0]);

        else if (a[node].size() == 2)
        {
            preorder(a[node][0]);
            preorder(a[node][1]);
        }
    }
}

//중위순회
void inorder(int node)
{
    if (visited[node] == false)
    {
        if (a[node].size() == 1)
            {
            inorder(a[node][0]);
            visited[node] = true;
            cout << node << " ";
            }

        else if (a[node].size() == 2)
            {
            inorder(a[node][0]);
            visited[node] = true;
            cout << node << " ";
            inorder(a[node][1]);
            }
        else
            {
            visited[node] = true;
            cout << node << " ";
            }
   }
}

//후위순회
void postorder(int node)
{
    if (visited[node] == false)
    {
        if (a[node].size() == 1)
        {
            postorder(a[node][0]);
        }
        else if (a[node].size() == 2)
        {
            postorder(a[node][0]);
            postorder(a[node][1]);
        }

        visited[node] = true;
        cout << node << " ";
    }
}

int main()
{
    a[1].push_back(2);
    a[1].push_back(3);
    a[2].push_back(4);
    a[2].push_back(5);

    preorder(1);
    cout << endl;
    memset(visited, 0, sizeof(visited));
    inorder(1);
    cout << endl;
    memset(visited, 0, sizeof(visited));
    postorder(1);


}

---

 

 

미로 탐색 - 백준 2178 문제

 

입력

2차원 배열 선언을 위한 세로크기 N 과 가로크기 M 을 입력받는다.
그리고 그 배열안의 수를 0 또는 1로 입력받는다.

 

출력

(1,1) 에서 출발하여 (N,M)까지의 이동하는 최소값을 출력

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

int n, m;

int uy, ux;

const int max_n = 104;

int a[max_n][max_n];
int visited[max_n][max_n];

int dy[] = { -1, 0 , 1 , 0 };
int dx[] = { 0 , 1 , 0 , -1 };

void go(int y, int x)
{	
	queue<pair<int,int>> q;	
	q.push(make_pair(y, x));	

	while (q.size())
	{
		tie(y, x) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			uy = y + dy[i];
			ux = x + dx[i];
			if (uy >= n || uy < 0 || ux < 0 || ux >= m)
				continue;

			if (visited[uy][ux] == 0 && a[uy][ux])
			{
				q.push(make_pair(uy, ux));
				visited[uy][ux] = visited[y][x] + 1;				
			}

		}
	}
	

	return;
}

int main()
{
	cin >> n >> m;	
	for (int i = 0; i < n; i++)
	{
		
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &a[i][j]);
		}
	}

	visited[0][0] = 1;
	go(0, 0);

	cout << visited[n - 1][m - 1];

	return 0;
}

 

 

가중치가 같으므로 최단거리 알고리즘인 BFS(Brench First Search) 알고리즘을 이용한다.

Queue 를 이용하여, 순차적으로 탐색하여 탐색할때마다 
Visited 배열을 이용하여 더해줌으로써, 최단거리를 알 수 있습니다.

---

 

 

유기농 배추 - 백준 1012 문제

 

입력

처음 입력은 몇개의 테스트 케이스를 구현할건지에 대한 T를 입력,
그리고 각각 테스트 케이스에 대해 배추밭의 가로길이M, 배추밭의 세로길이N, 배추의 개수K를 입력받는다.

출력

각 테스트 케이스에 대한 필요한 배추흰지렁이 개수를 출력

 

실습코드

#include <bits/stdc++.h>

using namespace std;

int T,N,M,K,ret;

const int max_cnt = 51;

int m_ret[max_cnt];

int dy[] = { -1 , 0 , 1 , 0 };
int dx[] = { 0 , 1 , 0 , -1 };

int a[max_cnt][max_cnt] = { 0, };
int visited[max_cnt][max_cnt] = { 0, };

int uy, ux;

void dfs(int y, int x)
{	
	visited[y][x] = 1;	
	for (int i = 0; i < 4; i++)
	{
		uy = y + dy[i];
		ux = x + dx[i];

		if (uy >= N || uy < 0 || ux >= M || ux < 0)
			continue;

		if (a[uy][ux] && !visited[uy][ux])
		{			
			dfs(uy, ux);
		}
	}
	return;
}



int main()
{
	cin >> T;

	for (int i = 0; i < T; i++)
	{		
		fill(&a[0][0], &a[0][0] + 51 * 51, 0);
		fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);
		cin >> M >> N >> K;

		for (int j = 0; j < K; j++)
		{
			int cx, cy;
			cin >> cx >> cy;
			a[cy][cx] = 1;			
		}

		for (int y = 0; y < N; y++)
		{
			for (int x = 0; x < M; x++)
			{
				if (!visited[y][x] && a[y][x])
				{						
					dfs(y, x);
					ret++;
				}				
			}			
		}		
		m_ret[i] = ret;				
		ret = 0;
		N = 0;
		M = 0;
		K = 0;
	}

	for (int i = 0; i < T; i++)
	{
		cout << m_ret[i] << endl;
	}
	return 0;
}

 

 

코드가 문제없는데 백준 제출에서는 자꾸 틀렸다고 나와서

혹시나 입력받는 부분에서 문제가 있나보았더니 M,N 을 거꾸로 입력받고 있었다..ㅠ
백준이 정말 까다롭다고 생각하면서도 저거 하나 발견 못해서 1시간동안 헤맨 내가 어이가 없다 ㅋㅋㅋ

앞으로 더 신중하게 코딩해야겠다...!