백준 33888번 [가오리 그래프](C++) -yes6686- 티스토리

백준 문제 풀이: 33888 (가오리 그래프)

---

문제 링크: https://www.acmicpc.net/problem/33888

문제 설명:

가오리 그래프는 특정 규칙을 가진 무방향 연결 그래프입니다. N개의 정점과 N+3개의 간선으로 구성되며, 총 6개의 핵심 정점(머리 A, 왼쪽 날개 B, 중심 C, 오른쪽 날개 D, 아래쪽 날개 E, 꼬리 F)과 N−6개의 일반 정점으로 이루어져 있습니다.

핵심 정점 사이에는 특정 쌍 간 단순 경로가 존재하고, 일반 정점은 항상 두 개의 정점과 연결되어 있으며 이 경로를 구성하는 중간 지점입니다. 주어진 그래프는 항상 가오리 그래프임이 보장되며, 정점 번호를 기준으로 핵심 정점을 판별할 수 있습니다. 단, D의 번호는 B보다 크다는 조건이 주어집니다.

---

문제 해결 코드

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

vector<int>v[51];
int visited[51];
int arr3[2];
int arr4[2];

void dfs(int x) {
	for (int i = 0;i < v[x].size();i++) {
		int k = v[x][i];
		if (visited[k]) continue;
		visited[k] = 1;
		if (v[k].size() == 2) {
			dfs(k);
		}
		else if (v[k].size() == 3) {
			if (arr3[0] == 0) arr3[0] = k;
			else arr3[1] = k;
		}
		else if (v[k].size() == 4) {
			if (arr4[0] == 0) {
				arr4[0] = k;
				dfs(k);
			}
			else {
				arr4[1] = k;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	for (int i = 0;i < n + 3;i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	int s;
	for (int i = 1;i <= n;i++) {
		if (v[i].size() == 1) {
			s = i;
		}	
	}
    
	visited[s] = 1;
	dfs(s);
	for (int i = 1;i <= n;i++) {
		if (v[i].size() == 3 && visited[i] == 0) {
			cout << i << " ";
		}
	}
	sort(arr3, arr3 + 2);
	cout << arr3[0] << " " << arr4[1] << " " << arr3[1] << " " << arr4[0] << " " << s << '\n';
}

---

코드 설명

• 핵심 알고리즘: 정점의 차수를 기반으로 핵심 정점을 분류합니다. 차수 1 → 꼬리(F), 차수 3 → 왼쪽/오른쪽 날개(B, D), 차수 4 → 중심/아래쪽 날개(C, E)
• 구현 세부사항:
  • dfs()로 일반 정점(차수 2)을 따라가면서 연결된 핵심 정점을 탐색
  • arr3, arr4에 각각 차수 3, 4인 정점 저장
  • B < D 조건을 기준으로 왼쪽/오른쪽 날개 구분
• 시간 복잡도 분석: O(N), 입력 크기(최대 50)에 대해 선형 탐색만 수행하므로 매우 효율적입니다.

---

결과

입력된 가오리 그래프의 핵심 정점들을 올바른 순서로 출력합니다:

출력 형식: 머리 A, 왼쪽 날개 B, 중심 C, 오른쪽 날개 D, 아래쪽 날개 E, 꼬리 F

다른 접근 방식이나 가오리 그래프를 구성하는 추가 조건이 궁금하다면 댓글로 함께 고민해보아요!