꽤 새로운 유형의 문제를 풀었다. 그래프나 Matrix에서 탐색하는게 아닌 n이라는 노드가 주어졌을때. 색이 다른 Edge 벡터에 각 노드가 배치되어있는데 Directed Graph 이고 각 노드가 이어질려면은 연결되있는 edge에 색이 달라야한다. 즉, 빨강 색 라인의 Edge 가 이어질려면은 파랑색 라인을 타야한다는 뜻이다.
문제는 여기서 각 노드가 이동하는데 제일 짧은 루트를 저장해야하고 존재하지 않는다면 -1을 리턴하면 된다.
처음에 이 문제를 풀때는 뭔가 많이 복잡하게 생각했었던건지 문제가 잘 안풀렸었다. 그러나 다음날 다시 봐보고 생각해보니 굉장히 간단한 문제였다. 처음에는 색을 임의로 설정할수있게 adj 벡터안에 넣을때 0은 빨강, 1은 파랑을 뜻하는 의미에서 넣었고 처음에 시작하는 0번쨰 노드는 3번의 랜덤 컬러를 부여했다.
그 다음부터는 일반적인 BFS였지만, 가장 짧은 루트를 찾기 위해 priority_queue를 사용했으며 만약 dist 가 업데이트가 안된 장소면은 어차피 priority_queue는 제일 짧은 루트를 줄수밖에 없기때문에 -1 일 경우 dist 를 새로 업데이트 될수있게 했다.
여기서 중요한점은 for 룹안에 그래프를 탐색하는 과정에서 visited 를 마킹할수있게 미리 p.second 를 3으로 지정해준것이다.
배운점:
- BFS와 그래프를 같이 활용한 문제 풀기
- 가장 짧은 distance 를 구하는 여러가지 방법
성장하는 사람