Today I Learned

오늘 할일
1. LeetCode
2. 영상처리 Chap 7~ Chap 8 공부
3. 인공지능개론 FAQ 20~
4. 소프트웨어 공학개론 과제
5. 영상처리 과제

오늘 한일
1. LeetCode

• 1466. Reorder Routes to Make All Paths Lead to the City Zero는 도시를 연결하는 길의 방향을 최소로 바꾸어 수도에 도달하게하는 문제이다.

/*
n개의 도시를 연결하는 오로지 하나의 길이 존재한다. 두 도시 사이는 너무 좁아서 한방향의 길만 존재한다.
connectinos[i]=[a,b]는 a->b를 의미한다.
올해에 수도인 0번째 도시에 행사가 있어 많은 사람들이 와야한다.
네 업무는 몇가지 길의 방향을 바꾸어 모든 도시가 수도에 방문할 수 있게해야한다.
이때 길의 방향을 최소로 바꾸는 횟수를 리턴하시오.
 */

첫번째로, 모든 도시에서 수도까지 가는 방향(노드) sequence가 필요하다. 그 후 sequence별로 direction contrast가 얼마나 필요한지를 체크하면 가장 간단할 듯 하다. 문제는 최소의 방향전환이 가능한지, 도시에서 수도까지 가는 방향이 여러개인지 등을 고려해야할 듯 하다.

두번째로, 수도에서 퍼진 각 branch마다 끝 노드를 파악해서 direction contrast를 수행해도 좋겠지만 그래도 겹치는 노드가 생긴다. 약간의 최적화만 수행될 듯 하다.

하지만 대략적인 코드를 작성해보니 첫번째 두번째의 방법은 너무 공간복잡도가 높아진다. connections를 최대한 활용할 방법이 없을까?