[백준] 1260 DFS와 BFS.py

문제 링크 : http://acmicpc.net/problem/1260

💡 아이디어

문제를 어떤 방식으로 해결하려 했는지 그 과정을 적어주세요. 초기에 접근한 방법과 최종 접근이 차이가 없으면 한개만 적어도 됩니다.

초기 접근

• 그냥 애초에 잘못 생각해서,,, 처음에 입력받을 때 둘 다 덱큐에 넣고 bfs는 앞에서부터 하나씩 뽑아오고 dfs는,,, (사실 생각도 안 하고 있었음. 왜냐하면 bfs부터 생각했거든,,,) 그래서 2차원 덱큐 이런 거 찾아봤는데 안되는건지 내가 못 찾은 건지 아님 다른 곳에서 오류가 생겼던건지,,, 진짜 알 수 없는 오류가 좌르륵 떴다. 근데 나중에 보니 ㅋㅋ 벡터 오류였음 대황당... 벡터 오류인 거 깨닫고 다시 코드 복구하려고 했을 땐 이미 늦었다.

최종 접근

• 잠깐 덮었다가 다시 켜고 생각하니,,, 다시 머리가 돌아가는 듯한,,, 그런 착각^^이 들어서 다시 생각해봤다. 처음에는 2차원 벡터에 넣어주고! 그 다음에 dfs랑 bfs 함수를 하나씩 새로 다시 선언해주고! 했다.
• BFS는 말이지~ 사실 처음에 생각을 잘못해서 while True로 두고,,, 하려고 했는데 종료조건이 생각이 안 나더라,,, 근데 다시 생각해보니 큐!를 사용해야 하잖아! 그래서 함수 안에서 큐를 하나 새로 선언해주고 거기에 내가 탐색할 대가리들을 일단 넣어주고 하나씩 뽑아주는 형태!로 했다. 그러고 그 큐가 빌 때까지 반복하는,,, 그런 형태였다. 이 때 대가리는 어떻게 넣어주냐! 대가리는 말이지~ visited라는 vector를 새로 선언해두고 거기에 내가 방문했나 안 방문했나 기록해뒀음. 방문 안 한 대가리들 상대로 큐에 넣어줬다. 뭐... 그렇게 하니깐 되더라...
• DFS는,,, 사실 기억 안 나서 강의 다시 틀어서 그 수도코드로 나와있는 거 다시 봤다ㅋ 재귀로,,, 했다. visited 배열을 사실 처음에 전역으로 vector visited(N+1);로 하려니 처음에 N값이 제대로 안 들어가있는 상태로 선언? 정의? 되어서 벡터 사이즈가 안맞는다~ 하는 오류가 뜨더라구. 그래서 그냥 최대 크기인 1000으로 해서 전역으로 선언해뒀다. 이것도 bfs랑 마찬가지?로 방문 안 했을 때 재귀를 다시 돌도록 하고~ visited 바꿔주고~ 출력해주고~하는 형태로 했다. 이건 뭐 따로 어디에 저장하고 그러진 않았다.

📋 사용 스펙

어떤 알고리즘 또는 기법을 사용해 문제를 해결했는지 알려주세요

• 그래프
• DFS
• BFS

👨🏻‍💻 👩‍💻 코드

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

int N, M, V;
vector<int> visitedD(1001);	// DFS 위한 visited

void dfs(vector<vector<int>> v, int start) {
	visitedD[start] = 1;
	cout << start << " ";
	for (int i = 0; i < v[start].size(); i++) {
		int key = v[start][i];
		if (visitedD[key] == 0) {	// 방문하지 않았을 경우
			dfs(v, key);
		}
		else
			;
	}
}

void bfs(vector<vector<int>> v) {
	vector<int> visited(N + 1);

	queue<int> q;	// 큐 선언
	q.push(V);	// 하나씩 뒤에 넣어줌
	visited[V] = 1;	// 방문 확인

	while (!q.empty()) {	// 종료조건을 잘 생각해야함!
		int start = q.front();	// 큐의 앞대가리를 대상으로 그래프 확인
		cout << start << " ";
		q.pop();
		
		for (int i = 0; i < v[start].size(); i++) {
			int key = v[start][i];
			if (visited[key] == 0) {	// 방문하지 않았을 경우
				q.push(key);	// 큐에 넣어줌
				visited[key] = 1;
			}
			else;
		}
	}
}

int main() {

	cin >> N >> M >> V;

	vector<vector<int>> v(N+1);

	// 2차원 벡터에 넣어줬음
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	// 같을 때 숫자가 작은 것부터 탐색하기로 했으니깐,,, 정렬
	for (int i = 1; i <= N; i++)
		sort(v[i].begin(), v[i].end());

	dfs(v, V);
	cout << "\n";
	bfs(v);

	return 0;
}

부족했던 점

솔루션에 접근하기 까지 아쉬웠던 부분 들을 적어주세요. 솔루션을 참조하고나서야 고친 점들을 적어주세요. 솔루션의 링크도 적어주세요. 막힘 없이 구현했다면, 생략해도 좋습니다.

• 처음에 너무 어렵게 생각한 부분이 없지 않아 있었던 것 같기도 하다,,, 뭐 2차원 덱을 구현하고 어쩌구 저쩌구,,, 그래서 2차원 덱 돼? 아는 사람 있으면 좀 알려주쇼 ㅠ

배운 점

해당 문제를 통해 배운 내용 들을 적어주세요. 어떤 알고리즘, 코딩 기법,자료구조 등을 알게됐다. 문법적 요소도 좋습니다. 크게 없으면 생략해도 좋습니다.

• 나 사실 이번에야 제대로 DFS랑 BFS를 알게 됐다... 걍 이게 각각 깊이우선탐색 너비우선탐색이라는 건 알고 있었는데,,, 어떻게 구현하고? 그런 건 처음 알게 됐던 것 같다. 이제 방법을 알았으니! 다음에 이 방법 이용해서 이것저것 풀어봐야징. 이 스터디 넘 도움돼요 강추합니당~~~!! 정말 그냥 혼자 했을 땐 대충대충 알고 있었던 알고리즘이나 자료구조가 정리되는 느낌이다 ㅎㅅㅎ 감사합니다 여러분 모두~~~