MZ 개발자

처음 떠오른 방법은 queue에다가 각 인접 노드를 {노드,가중치 합} 로 저장하고 큐를 순회하면서 해당 노드의 가중치 합을 최소로 만들어 주는 것이였다. 즉 BFS 방식을 떠올린 것이다. 하지만 이 문제를 BFS로 풀려면 큐에서 가중치가 0인 노드부터 방문해야 하는 조건이 붙는다. 위에 조건을 적용하지 않아 제출하면 자꾸 8%에서 틀렸다고 나왔다..... BFS로 해결되지 않아 다익스트라를 적용하였다. 다익스트라가 적용될 수 있는 이유는 "가중치가 모두 0 또는 양수이고, 특정 지점 a에서 b 지점까지의 최단 경로 가중치"를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다. 하지만 기존 다익스트라와 조금 다른점은 인접노드에 대한 정의가 나와있지 않기 때문에 각 지점에서 인접한 노드를 X+1, X-..

문제에서 여행 계획에 속한 도시 M이 주어지고 총 N 개의 여행 계획이 주어진다. 이때 여행계획을 달성할 수 있는지 없는지 확인하는 문제이다. 문제를 해결하기 위해 생각해낸 아이디어는 다음과 같다. 1. 만약 a-b-d-a-c 순서로 여행한다고 가정하였을경우 a-b, b-d, d-a, a-c 가 연결 되어있다면 무조건 갈수 있지 않을까? 2. 그럼 서로 연결되어있다는 것은 어떻게 알수 있을까? -> union - find를 활용하자!! Union - Find에서 핵심은 각각의 i,j에 대해 각각 root parent를 확인하고 둘중에 더 큰 집합으로 parent를 업데이트 해준다. 이렇게 구한 그래프와 그의 parent 정보를 바탕으로 계획에 있는 도시들이 모두 같은 root parent를 가질경우 여행..

이 문제의 특징은 특정 도시에서 출발하여 최단거리가 정확히 k 인 모든 도시를 출력하는것이다. (단 k인 도시가 존재하지 않은면 -1을 출력한다.) 문제를 읽으면서 최단거리 키워드가 나와 BFS응용 이라는 것을 알게 되었다. 하지만 기존에 내가 풀던 BFS문제는 상,하,좌,우로 이동하는 문제를 주로 풀었다. 비슷한 로직으로 접근하여 각 노드의 간선을 인접리스트로 구현하였고, x노드를 시작으로 갈수 있는 경로를 인접리스트를 순회하면서 탐색하였다. 핵심은 인접리스트 순회시 visited 표시를 하는것이다!!! 순회시 visited를 표시하지 않고 queue에서 pop 할때 visited를 표시해준다면 최단경로를 구할수 없다. 위의 그래프를 인접리스트를 순회할때 queue에 들어가는 값은 다음과 같다 {nod..