https://www.acmicpc.net/problem/7576BFS로 푸는 문제고, 시간초과에 유의해야 한다. visted를 bool로 하지 않고 int값으로 하여, 이 전에 있던 곳에서 +1을 해 날짜를 더해나가는 방식으로 구현하였다.#include #include #include using namespace std;int x, y, answer = 0;vector> list;vector> visited;int dx[4] = { -1 , 0, 1, 0 };int dy[4] = { 0, 1, 0, -1 };void init(){ int input; cin >> x >> y; list = vector>(y, vector(x, 0)); visited = vector>(y, vector(x, 0)); fo..

https://www.acmicpc.net/problem/11724BFS, DFS 전부 다 상관없지만, 필자는 BFS를 사용하였다.연결 요소는 간단하게 말해서 그래프의 개수이다.#include #include #include using namespace std;vector> graph;vector visited;int bfs(int start){ if (visited[start]) return 0; queue que; que.push(start); visited[start] = true; while (!que.empty()) { int current = que.front(); que.pop(); for (int i = 0; i > N >> M; graph = vector>(N + 1); visit..

https://www.acmicpc.net/problem/7562문제에서 주어진 내용에 있는 '최소 몇 번' 이라는 문구를 보고 BFS로 풀었다.#include #include #include using namespace std;vector> answer;vector> visited;int dx[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };int dy[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };void bfs(int X, int Y, int I){ queue> que; visited[Y].at(X) = true; que.push(make_pair(Y, X)); while (!que.empty()) { int currentY = que.front().first; ..

https://www.acmicpc.net/problem/1697이전글에 풀었던 미로 탐색에서 사용하였던 방법을 응용하면 되는 문제이다.#include #include #include using namespace std;vector list;vector visited;vector answer;void bfs(int start){ int size = list.size(); queue que; que.push(start); visited[start] = true; while (!que.empty()) { int current = que.front(); que.pop(); if (current - 1 >= 0) { if (!visited[current - 1]) { que.push(curr..

https://www.acmicpc.net/problem/2178최소 칸 수를 확인하기 위해서 DFS보다는 BFS로 푸는 것이 좋다고 하여, BFS로 풀어보았다.#include #include #include #include using namespace std;vector maze;vector> visited;vector> answer;int N, M;int dx[4] = { -1, 0, 1, 0 };int dy[4] = { 0, 1, 0, -1 };void bfs(){ queue> que; int x, y = 0; visited[0].at(0) = true; answer[0].at(0) = 1; que.push(make_pair(0, 0)); while (!que.empty()) { y = que.f..

https://www.acmicpc.net/problem/2606DFS, BFS 어느 것을 사용해도 상관없지만, 필자는 BFS를 이용하였다.#include #include #include #include using namespace std;vector> list;vector visited;int bfs(){ queue que; int answer = 0; visited[1] = true; que.push(1); while (!que.empty()) { int current = que.front(); que.pop(); for (int i = 0; i > N >> M; list = vector>(N + 1); visited = vector(N + 1, false); for (int i = 0; i >..

https://www.acmicpc.net/problem/2444524444번 문제에서 내림차순으로 변경하는 것 말고는 같은 문제이다.#include #include #include #include using namespace std;vector> list;vector visited;int visitedOrder = 1;void dfs(int start){ queue que; visited[start] = visitedOrder++; que.push(start); while (!que.empty()) { int current = que.front(); que.pop(); for (int i = 0; i b;}int main(){ int N, M, R; cin >> N >> M >> R; list ..

https://www.acmicpc.net/problem/24444BFS의 기초를 다질 수 있는 문제이다.#include #include #include #include using namespace std;vector> list;vector visited;int visitedOrder = 1;void dfs(int start){ queue que; visited[start] = visitedOrder++; que.push(start); while (!que.empty()) { int current = que.front(); que.pop(); for (int i = 0; i > N >> M >> R; list = vector>(N + 1); visited = vector(N + 1, 0); for ..

https://www.acmicpc.net/problem/1260주어진 입력에 맞춰 DFS와 BFS로 방문하는 순서 그대로 출력하면 되는 문제이다.#include #include #include #include using namespace std;bool visited[1001];vector graph[1001];void solution_dfs(int start){ visited[start] = true; cout que; que.push(start); visited[start] = true; while (!que.empty()) { int corrent = que.front(); que.pop(); cout > N >> M >> V; for (int i = 0; i > v1 >> v2; gra..