글 읽기 - 질문] dfs 풀이, 지우는 노드를 미리 방문처리하는 알고리즘

hwanseok_dev 3년 전 0

먼저 다른 질문에 있었던 방법으로는 AC를 받았습니다.

(노드 정보 입력 받아서 전체 리프 노드 count) - (지울 노드의 하위 리프 노드 count) [+ 지운 노드의 부모가 leaf가 되는 경우 + 1]

제가 생각한 풀이로 다시 풀고 있는데 문제가 무엇인지 모르겠습니다.

1. 각 노드의 child를 인접리스트로 정리

1. 지워야하는 노드를 dfs 하기 전에 방문처리를 한다.

1. 특정 노드의 자식이 없거나, 자식들이 모두 방문처리(이미 노드 삭제된 경우) 되었으면 리프노드이다.

알고리즘의 문제인지 구현의 문제인지 모르겠습니다. 도와주세요!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
vector<int> v[50];
vector<bool> visited(50, false);

vector<int> root;
int ans = 0;
void dfs(int x) {
	visited[x] = true;

	bool flag = true; // 리프노드이면 true
	for (int i = 0; i < v[x].size(); i++) {
		int next = v[x][i];
		if (!visited[next]) {
			dfs(next);
			flag = false; // 방문하지 않는 자식 노드가 있는 경우
		}
	}
	if (flag)ans++;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;

	int t = 0;
	for (int i = 0; i < n; i++) {
		cin >> t;
		if (t == -1) {
			root.push_back(i);
		}
		else {
			// t는 i의 루트
			v[t].push_back(i);
		}
	}
	cin >> t;
	// 지워야하는 노드 방문처리
	visited[t] = true;

	for (int i = 0; i < root.size(); i++) {
		if (!visited[i]) {
			dfs(i);
		}
	}
	cout << ans << "\n";
	return 0;
}

hwanseok_dev 3년 전 0

루트가 여러개인 경우는 고려하지 않아도 됩니다.

위 코드의 문제점은 루트를 삭제하는 경우에 대해서 오류가 있었습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
vector<int> v[50];
vector<bool> visited(50, false);

int root = 0;
int ans = 0;
void dfs(int x) {
	// 이미 방문한 노드인 경우 종료
	if (visited[x]) return;

	// 노드방문
	visited[x] = true;

	bool flag = true; // 리프노드이면 true
	for (int i = 0; i < v[x].size(); i++) {
		int next = v[x][i];
		if (!visited[next]) {
			dfs(next);
			flag = false; // 방문하지 않는 자식 노드가 있는 경우
		}
	}
	if (flag)ans++;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;

	int t = 0;
	for (int i = 0; i < n; i++) {
		cin >> t;
		if (t == -1) {
			root = i;
		}
		else {
			// t는 i의 루트
			v[t].push_back(i);
		}
	}
	cin >> t;
	// 지워야하는 노드 방문처리
	visited[t] = true;

	dfs(root);
	cout << ans << "\n";
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문] dfs 풀이, 지우는 노드를 미리 방문처리하는 알고리즘

hwanseok_dev 3년 전 0

hwanseok_dev 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말