[백준 / BOJ] 23040 누텔라 트리 (Easy)

문제

출처 : https://www.acmicpc.net/problem/23040

23040번: 누텔라 트리 (Easy)

빨간색과 검은색 정점들로 이루어진 트리가 있다.

시작은 검은색 정점, 나머지 정점은 모두 빨간색인 경우 이를 누텔라 경로라고한다.

트리에서 누텔라 경로의 갯수를 찾는 문제였다.

---

풀이

시간초과를 주의해야했던 문제였다.

 

논리는 아래와 같다.

검은색 정점에서 시작해, 거쳐간 빨간색 정점을 모두 더하면 해당 검은색 정점에서 갈 수있는 누텔라 경로의 갯수이다.

 

위 논리를 그대로 구현 하면되는데, N이 최대 10만이므로, 이렇게 구현할경우 N^2 시간복잡도로 시간초과가 나온다.

시간복잡도를 방지하기위해, 검은색 정점에서 시작했을때, 만난 빨간색 정점들을 "해당 경로의 최대 누텔라 경로의 갯수로 업데이트" 시켜줘야한다. 그 후, 해당 정점에 다시 방문했을때, 업데이트 된 경로의 수로 즉시 return 해준다.

(이때, 누텔라 경로를 업데이트할때, 경로별로 업데이트 해줘야함에 주의하자!)

 

모든 정점을 1번 밖에 방문하지않으므로, 시간복잡도는 O(N)이 된다.

 

주요 소스코드

	private long enterNutella(int idx, int v){
		if(nutella[idx] > 0L && leafColor[idx] != 'B') return nutella[idx];
		if(leafColor[idx] != 'B') nutellaStack.add(idx);
		visit[idx] = v;
		List<Integer> l = list.get(idx);
		long ret = 0L;
		for(int i = 0; i < l.size(); i++){
			int to = l.get(i);
			if(visit[to] == v || leafColor[to] == 'B') continue;
			long cnt = enterNutella(to, v);
			ret += cnt + 1L;
			if(leafColor[idx] == 'B') 
				while(!nutellaStack.isEmpty()) 
					nutella[nutellaStack.pop()] = cnt;
		}
		return ret;
	}

경로별로 최적화 시켜주기위해, 바텀업으로 올라오다 재귀를 시작한 시작위치에 올라왔을때, 경로를 최적화 해주는 부분을 주의깊게 보자.

 

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/23040%20%EB%88%84%ED%85%94%EB%9D%BC%20%ED%8A%B8%EB%A6%AC%20(Easy)/Main.java 

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃