욱이의 IT 생존일지

문제로 이동하기 https://www.acmicpc.net/problem/13549 접근 방식 앞서 소개 드렸던 이모티콘 문제와 마찬가지로, 이 문제도 BFS와 DP 모두 사용이 가능합니다. 저는 BFS로 해결했는데, 결과를 보니 DP에 비해 시간과 메모리 모든 면에서 처참했습니다 ㅜㅜ 추후 DP로 해결하는 방법도 포스팅하겠습니다. 이 문제에서 중요한 키워드는 "순간이동을 하는 경우에는 '0초' 후에 이동" 입니다. 즉, 가중치가 0인 간선이 존재한다는 것인데요, 지금까지 BFS로 풀 수 있는 중요한 키워드가 되는 말이 가중치가 모두 1이다. 라는 점이었다는 것을 생각해보면, 이 문제를 BFS로 접근할 수 없는 것이 아닌가 싶을 수 있는데요. 두 가지 방법을 생각해볼 수 있습니다. 큐 두 ..

접근 방식 이 문제는 BFS로도 접근이 가능하고, DP로도 가능합니다. DP가 더 빠른 성능을 보여주기 때문에 수행 시간에 민감하다면 DP로 접근하는 것이 바람직합니다. 여기서는 BFS를 연습하기 위해 BFS로 접근해보겠습니다. 이 문제에서 주의해야 하는 점은, 같은 정점에 있다고 해서, 실제 같은 정점이 아니라는 점입니다. 예를 들어, 횟수 등의 조건이 들어가게 되면, 해당 조건으로 인해 이용할 수 있는 간선이 달라지기 때문에 조건이 다른 상황에서의 정점은 같은 정점이라고 할 수 없습니다. 정리하자면, 같은 정점이기 위해서는, 해당 정점에서 이동할 수 있는 간선이 같아야 한다는 것입니다. 그러나 이 문제에서는 클립보드에 들어있는 이모티콘의 개수에 의해 정점마다의 상태가 달라집니다. 따라서 이 문제의 기..

접근 방식 오랜만에 풀어본 BFS 문제입니다. 일반 숨바꼭질 문제와 똑같습니다만 추가로 이동 방법까지 출력해야 하는 문제입니다. 이동 방법을 구하는 문제라면 이전에도 살펴보았듯이 이전 부모의 이력을 계속 기록해놓았다가 마지막에 역순으로 출력하는 식으로 해결할 수 있습니다. 이 문제에서는 visited 를 확인하는 배열을 따로 두지 않았습니다. 이유는 부모 이력을 기록하는 배열에 이력이 기록된 상태라면 이미 방문한 노드임을 확신할 수 있기 때문입니다. BFS를 수행하는 과정은 쉬운 BFS 문제들과 거의 유사하기 때문에 코드를 보면서 이해하시는 편이 빠를 것이라 생각합니다. 개선 사항 func printRoute(S int) { if P[S] == -1 { fmt.Fprintf(w, "%d ", S) ret..