[백준/C++] 24479 알고리즘 수업 - 깊이 우선 탐색 1

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

이번문제 너무 어려워서 해답도 찾아보고 좀더 이해해 보려고 했다..스스로는 해결 못했다.

하지만 제대로된 풀이글을 못찾고 거의 가져다 붙여넣기 식으로 해서 다시 차근차근 봐야 할 것 같다.

처음에 주어진 정수만큼의 배열을 잡아두고하는데 터져서 안되고..

그냥 정수의 조건을 무시하고 했더니되는데 이게왜 이런 원리인지 아직 확실히 모르겠다.

일단 여러군데  참조한것을 각각 따로 풀어봐야 겠다.

 

// 풀이방식 1
#include <iostream>
#include <vector>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector <vector<int>> graph;
vector <int> visited;
vector <int> sequence;
int N, M, R, Seq;

void input()
{
    cin >> N >> M >> R;
    graph.resize(N + 1);
    visited.resize(N + 1);
    sequence.resize(N + 1);
    int u, v;
    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());
}
void dfs(int n)
{
    sequence[n] = ++Seq;
    visited[n] = 1;
    int graphsize = graph[n].size(), v;
    for (int i = 0; i < graphsize; i++) {
        v = graph[n][i];
        if (visited[v] == 0) dfs(v);
    }
}
void sol()
{
    dfs(R);
    for (int i = 1; i < N + 1; i++)    printf("%d\n", sequence[i]);
}
int main()
{
    fastio;
    input();
    sol();
    return 0;
}

// 풀이방식2
#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector<int> graph[100001];
int visited[100001] = { 0, };
int result[100001];
int cnt = 0;

void dfs(int r) {
	if (visited[r] == 1) 
		return; // 방문 한 곳이면 return

	visited[r] = 1; // 방문하지 않았던 곳이면 1로만들고
	cnt++; // 카운트 증가
	result[r] = cnt; // 카운트 넣기
	for (int i = 0; i < graph[r].size(); i++) {
		dfs(graph[r][i]);
	}
}
int main() {
	fastio;
	int n, m, r;
	scanf("%d %d %d", &n, &m, &r);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b); // (1,4) (1,2) (2,3) (2,4) (3,4)
		graph[b].push_back(a); // (4,1) (2,1) (3,2) (4,2) (4,3)	
	}
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	dfs(r);
	for (int i = 1; i <= n; i++) {
		printf("%d\n", result[i]);
	}
}