| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 6023 | 1403 | 855 | 22.861% |
문제
어느 점에서 출발하여 그래프 상에 있는 모든 간선을 지나되 한번 지난 간선은 다시 지나지 않고 출발점으로 돌아오는 회로를 오일러 회로라 한다. 단, 그래프는 양방향 그래프가 주어진다.
문제는 그래프가 주어졌을 때 오일러 회로 경로를 출력하는 것이다.
입력
첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 개 있을 수 있다. 인접행렬의 값은 두 정점 사이의 간선 개수를 의미하며, 0보다 크거나 같고, 10보다 작거나 같은 정수이다.
입력으로 주어지는 그래프에는 루프 (양 끝점이 같은 간선)는 없다. 또, 입력으로 주어지는 그래프는 모두 연결되어 있다.
출력
첫 줄에 방문하는 점 순서를 공백으로 구분하여 출력한다. 단, 시작점은 어느 위치에서든 상관없고 아무 경로만 하나 찍으면 된다. 불가능한 경우에는 -1을 출력한다.
접근
오일러회로의 필요충분조건은 모든 노드가 짝수개의 엣지를 갖는 것이다.
이 부분만 미리 체크해주고, DFS로 쭉 순회를 돌려주면 된다.
풀이
주의할 점은, DFS에서 출력은 순회를 끝내고 해야된다.
이렇게해야 처음 점과 마지막 점이 일치함을 보장할 수 있다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, arr[1001][1001];
void DFS(int node)
{
FUP(i, 1, N)
{
if (arr[node][i])
{
arr[node][i]--;
arr[i][node]--;
DFS(i);
}
}
COUT2(node, "");
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
bool ok = true;
CIN(N);
FUP(i, 1, N)
{
int cnt = 0;
FUP(j, 1, N)
{
CIN(arr[i][j]);
cnt += arr[i][j];
}
if (cnt % 2) ok = false;
}
if (!ok) COUT(-1);
else DFS(1);
return 0;
}
Beginner