백준 1260번 : DFS와 BFS

문제 접근

---

1. 정직한 제목, 정직한 풀이
   
     DFS와 BFS 구현하는 문제다. 그래프를 알면 그냥 풀면 된다.

 

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

1260번: DFS와 BFS

 

 

 

문제 코드

---

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

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void print_DFS(int current_vertex)
{
	visited[current_vertex] = true;
	cout << current_vertex << ' ';

	for (int edge_num = 0; edge_num < graph[current_vertex].size(); ++edge_num)
	{
		int next_vertex = graph[current_vertex][edge_num];

		if (visited[next_vertex])
			continue;

		print_DFS(next_vertex);
	}
}

void print_BFS(int start_vertex)
{
	queue<int> bfs;

	bfs.push(start_vertex);
	visited[start_vertex] = true;

	while (!bfs.empty())
	{
		int current_vertex = bfs.front();
		bfs.pop();
		cout << current_vertex << ' ';

		for (int edge_num = 0; edge_num < graph[current_vertex].size(); ++edge_num)
		{
			int next_vertex = graph[current_vertex][edge_num];

			if (visited[next_vertex])
				continue;

			bfs.push(next_vertex);
			visited[next_vertex] = true;
		}
	}
}

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

	int N, M, V, start, end;

	cin >> N >> M >> V;

	graph.resize(N + 1);
	visited.resize(N + 1);

	for (int edge_num = 0; edge_num < M; ++edge_num)
	{
		cin >> start >> end;

		graph[start].push_back(end);
		graph[end].push_back(start);
	}

	for (int vertex_num = 1; vertex_num <= N; ++vertex_num)
	{
		sort(graph[vertex_num].begin(), graph[vertex_num].end());
		graph[vertex_num].erase(unique(graph[vertex_num].begin(), graph[vertex_num].end()), graph[vertex_num].end());
	}
	
	fill(visited.begin(), visited.end(), false);
	print_DFS(V);
	cout << '\n';

	fill(visited.begin(), visited.end(), false);
	print_BFS(V);

	return 0;
}

 

 

 

느낀 점

---

    Class 3으로 넘어가면서 미해결 된 문제를 확인해 보니 standard 태그 붙은 문제 2개가 그래프 문제였다. 따라서 레콩키스타의 첫 번째 자료 구조는 그래프로 생각하고 진행하려고 한다.

 

 

1. 문제를 풀고 WA를 받으면, 고민을 하자.
   
     WA 받으면 일단 질문 게시판으로 가서 반례 확인하는 습관이 계속 나온다. 혼자서 고민하는 습관을 들이자.
   
   
2. 문제를 자세히 확인하고, 범위를 제대로 설정하자.
   
     위의 문제에서 N의 범위는 1~1,000인데 0~999로 계산하고 있었다. 범위를 잘 확인하자.
   
   
3. 각 함수에 필요한 헤더 파일을 제대로 넣자.
   
     아마도 visual studio에는 기본적인 내장 헤더 파일 같은게 있는 것 같다. 코드에 생각 없이 sort 함수 넣고 돌렸더니 잘 동작하길래 제출했는데, 헤더 파일을 선언하지 않아서 WA를 받았다. 헤더 파일을 제대로 명시하도록 하자. 그렇다고 bits/stdc++. h 헤더 파일을 사용하자니 헤더 파일을 다 때려 넣는 게 약간 꺼림칙해서 일단은 조금 더 신경 써봐야 될 것 같다.