[백준] 백준 문제 풀이 - 1260 DFS/BFS

👩🏻‍💻 문제링크

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

 

1260번: DFS와 BFS

 

✍️ 아이디어

1. 문제 이해

• 처음에 연결리스트로 접근 하려고 했다가 너무 복잡해서 dfs 까지만 구현하고 멈춤
• 배열로 구현 해서 답이 나왔으나 왠지 모르게 틀림 (왜맞틀?)

2. 내가 생각 못한것은 방문했는지 안했는지 방문일지를 따로 만드는것을 생각하지 못했다!!

-> 난 결과값 저장공간을 따로 만듬

 

3. fill_n(visited, 1001, 0); 를 사용하여 visited의 모든 메모리를 0으로 초기화

✍️소스코드

<나의 코드>

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

int main()
{
    int N,M,V;
    cin >> N >> M >> V; 
	int graph[N+1][N+1]={0};
	for(int i=0; i<M; i++){
        int u,v;
        cin>>u>>v;
        graph[u][v]=1;
        graph[v][u]=1;
    }
    
    //dfs
	vector<int> result1; result1.push_back(V);
	int num=N+1;
	int n=V;
	while(num--)
	{
		for(int m=0; m<N+1; m++)
		{
			if(graph[n][m]==1 && find(result1.begin(), result1.end(), m) == result1.end())
			{
				result1.push_back(m);
				n=m;
				break;
			}
			else
				continue;
		}
	}
	for(auto iter=result1.begin(); iter!=result1.end(); iter++)
	{
		cout<<*iter<<" ";
	}
	cout<<"\n";
    
    //bfs
	vector<int> result2; result2.push_back(V);
	queue <int> q; q.push(V); num=N+1;
	while(!q.empty())
	{
		n=q.front();
		q.pop();
		for(int m=0; m<N+1; m++)
		{
			if(graph[n][m]==1 && find(result2.begin(), result2.end(), m) == result2.end())
			{
				result2.push_back(m);
				q.push(m);	
			}
		}
	}
	for(auto iter=result2.begin(); iter!=result2.end(); iter++)
	{
		cout<<*iter<<" ";
	}
	cout<<"\n";
}

 

 

<대다수의 코드> 재귀 DFS

#include<iostream>
#include<queue>


using namespace std;

int line[1001][1001];
int visited[1001]; //방문일지;;
int n, m, v;
queue<int> q;
void dfs(int idx) {
    cout << idx << ' ';

    for (int i = 1; i <= n; i++) {
        if (line[idx][i] && !visited[i])
        {
            visited[i] = 1;
            dfs(i);
        }
    }


}
void bfs(int idx) {

    q.push(idx);

    while (!q.empty()) {

        idx = q.front();

        q.pop();

        cout << idx << ' ';

        for (int i = 1; i <= n; i++) {
            if (line[idx][i] && !visited[i]) {
                q.push(i);
                visited[i] = 1;
            }
        }


    } 


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

    cin >> n >> m >> v;


    for (int i = 0; i < m; i++) {
        int from, to;
        cin >> from >> to;
        line[from][to] = 1;
        line[to][from] = 1;
    }
    visited[v] = 1;
    dfs(v);

    cout << '\n';
    fill_n(visited, 1001, 0);
    visited[v] = 1;
    bfs(v);
    return 0;
}

 

<연결리스트 기반의 코드>

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(vector<int>* graph, int start, bool* visited) {
	if (visited[start] != true) {
		visited[start] = true;
		cout << start << ' ';
		for (auto it = graph[start].begin(); it != graph[start].end(); it++) {
			if (visited[*it] != true) {
				dfs(graph, *it, visited);   //함수의 재귀 호출 이용
			}
		}
	}
	else return;
}

void bfs(vector<int>* graph, int start, int n) {
	bool* visited = new bool[n + 1];
	for (int i = 0; i < n + 1; i++) visited[i] = false;

	queue<int> queue;

	visited[start] = true;
	queue.push(start);
	cout << start << ' ';

	if (graph[start].empty()) {  //연결된 간선이 없는 경우 출력 후 바로 리턴
		cout << '\n';
		return;
	}

	while(!queue.empty()) {
		start = queue.front();
		queue.pop();

		if (graph[start].empty()) {  //연결된 간선이 없는 경우 출력 후 바로 리턴
			cout << start << '\n';
			return;
		}

		for (auto it = graph[start].begin(); it != graph[start].end(); it++) {
			if (visited[*it] != true) {
				visited[*it] = true;
				queue.push(*it);
				cout << *it << ' ';
			}
		}
	}

	cout << '\n';
}

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

	int n, m, start;
	cin >> n >> m >> start;

	int u, v;
	vector<int>* graph = new vector<int>[n + 1];

	for (int i = 0; i < m; i++) {
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}

	bool* visited = new bool[n + 1];
	for (int i = 0; i < n + 1; i++) visited[i] = false;

	dfs(graph, start, visited);
	cout << '\n';
	bfs(graph, start, n);

	return 0;
}

 

 

체감난이도	걸린시간	참고	사용 문법
중	30min	x	벡터, 큐, dfs/bfs