[BOJ] 백준 21606. 아침 산책 (Gold III)

요즘 웹개발 공부를 하느라 백준을 많이 풀지 못해서 풀어본 문제.

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

21606번: 아침 산책

생긴게 트리dp, DFS처럼 생겨서 해결해보려 한 문제이다.

---

의식의 흐름 및 해설

사실 맨 처음에 생각난 것은 '인접행렬과 그래프' 이다. 

즉, 아래 문제가 먼저 떠오른 것이다.

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

12850번: 본대 산책2

그런데 이 문제는 실내, 실외가 구분이 돼있다는 점, 다시 실내에 도착하면 더 이상 진행하지 않는다는 점, 그리고 출발점과 도착점이 다르다는 점과 같이 수많은 차이점이 존재하여 전혀 다른 문제라는 걸 바로 알아챌 수 있다.

 

그 다음으로 생각난 것은 트리dp, DFS 였으나, O(N^2) 풀이밖에 떠오르지 않아 한참을 고민했다.

이 문제같은 경우는 N이 최대 20만이기 때문에 O(N^2)으로 진행할 경우 TLE를 받는다.

 

이 문제를 O(N)으로 줄일 수 있는 방법은 아래와 같다.

 

어차피 실내 <-> 실내이면서, 중간에 실내를 거치지 않는 길의 개수를 구하는 문제이기 때문에,

실외를 하나의 컴포넌트로 생각하여, 그 주변에 인접한 실내의 개수를 dfs로 count해주면 된다. 예를 들어, 주변 인접 실내의 개수가 5개이면, 답에 5*4를 더해주면 된다. 같은 길이어도, 출발점과 도착점이 뒤바뀐 길도 다른 길로 계산하는 문제이기 때문에 2로 나눠줄 필요가 없다.

 

또한, 실내 <-> 실내 길 사이에 실외가 하나도 없는 경우는 위 방법으로 count되지 않으므로, 

실내이면서 주변 인접 실내인 경우를 count해준다.

 

이렇게 하면 1번부터 N번까지 탐색 O(N), 중간에 DFS가 있긴 하지만, i번에서 DFS로 i~j번까지 탐색한다고 치면, 이후에 i+1~j번까진 이미 DFS로 탐색했기 때문에 추가적으로 탐색할 필요가 없으므로 O(N)의 시간복잡도로 처리할 수 있다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int MAX = 200001;
const int MOD = 1e9 + 7;
ll N, ans;
string s;
vector<int> v[MAX];
bool visit[MAX];
ll dfs(int cur) {
	ll ret = 0;
	visit[cur] = true;
	for (auto i : v[cur]) {
		if (!visit[i]) {
			if (s[i] == '0')
				ret += dfs(i);
			else
				ret++;
		}
	}
	return ret;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> s;
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i = 0; i < N; i++) {
		if (s[i] == '1') {
			for (auto j : v[i])
				ans += s[j] == '1';
		}
		else {
			if (visit[i])
				continue;
			ll ret = dfs(i);
			ans += ret * (ret - 1);
		}
	}
	cout << ans << "\n";
}

---

여러 노드를 문제 조건에 따라 하나의 컴포넌트 단위로 보는 관점이 되게 신기했다.

또한, 이 문제를 treeDP로도 풀 수 있다는데, 위 방법을 이용하지 않은 트리dp 풀이가 딱히 떠오르지 않기 때문에, 트리dp 문제 연습을 많이 해봐야겠다.