https://www.acmicpc.net/problem/24479
이번문제 너무 어려워서 해답도 찾아보고 좀더 이해해 보려고 했다..스스로는 해결 못했다.
하지만 제대로된 풀이글을 못찾고 거의 가져다 붙여넣기 식으로 해서 다시 차근차근 봐야 할 것 같다.
처음에 주어진 정수만큼의 배열을 잡아두고하는데 터져서 안되고..
그냥 정수의 조건을 무시하고 했더니되는데 이게왜 이런 원리인지 아직 확실히 모르겠다.
일단 여러군데 참조한것을 각각 따로 풀어봐야 겠다.
// 풀이방식 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]);
}
}
'백준' 카테고리의 다른 글
[백준/C++] 1912 연속합 (0) | 2023.05.18 |
---|---|
[백준/C++] 14425 문자열 집합 (0) | 2023.05.15 |
[백준/C++] 10845 큐 (0) | 2023.05.03 |
[백준/C++] 2485 가로수 (유클리드호제법, 최대공약수) (0) | 2023.05.02 |
[백준/C++] 1914 하노이 탑 (0) | 2023.04.25 |
댓글