MZ 개발자

이 문제는 정점 쌍이 주어지면 트리의 부모가 누구인지 찾는 문제이다. 문제의 예제 입력이 너무 깔끔하게 되어있어서 쉽게 생각할 수 있지만 현재 노드에서 어떤 인접리스트를 탐색해야 할지 생각이 필요한것 같다. 처음 문제를 보았을때 인접리스트를 바로 떠올리지는 않았다. 유니온-파인드인가..?? 생각을 해봤는데 아닌것 같았고.... 뭔가 다음 노드로 이동할때 마다 이동한 노드의 부모 노드를 표시해줘야 할것 같은데 한참을 생각하다가 인접리스트를 이용한 완전 탐색을 떠올렸다. 문제의 예제를 인접리스트와 그래프로 표현하면 다음과 같다. 이제 그래프 완전 탐색을 하면서 현재의 노드의 부모가 어떤건지 표현해주면 된다. 여기서 주의할 점은 단순 dfs로 문제를 풀때 이미 탐색이 끝난 노드는 재방문 하지 않돌고 visit..

이 문제는 A라는 수를 DSLR 규칙을 이용하여 B로 바꾸는데 필요한 최소한의 명령어를 나열하여 출력하는 문제이다. 처음 문제를 보았을때 숫자를 자릿수로 쪼개서 deque으로 저장할까 라는 생각을 하였다. 이 방법을 이용하면 L,R은 쉽게 풀수 있지만 D,S는 자릿수를 다시 계산해야 하는 번거로움이 생긴다. 그냥 숫자로 접근해보자!! DSLR을 숫자로 접근해보면 다음과 같은 식으로 표현할 수 있다. D: (n * 2) % 10000 S: (n - 1) < 0?9999:n - 1 L: (n % 1000) * 10 + (n / 1000) R: (n % 10) * 1000 + (n / 10) 이제 A숫자에서 B로 만들기 위해 우리는 DSLR을 반복해서 수행해야 한다. 처음에는 시뮬레이션 문제인가 헷갈렸다. 알..

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

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