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

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

반응형

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

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

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

의식의 흐름 및 해설

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

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

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

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

그 다음으로 생각난 것은 트리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 #include #include #include #include #include #include #include #include #include #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 pl; typedef pair pll; const int MAX = 200001; const int MOD = 1e9 + 7; ll N, ans; string s; vector 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 << "

"; }

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

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

반응형

from http://kth990303.tistory.com/141 by ccl(A) rewrite - 2021-09-18 15:26:29