BFS 6

[BOJ/16946/Golang] 백준 16946 - 벽 부수고 이동하기 4

문제로 이동하기 https://www.acmicpc.net/problem/16946 여담 아... 처음엔 시간초과로, 이후엔 갈피를 잡지 못하다가, 결국 힌트를 보고 나서야 아 맞네!! 하고 바로 풀어냈습니다 ㅋㅋㅋ 엄청 단순하게 생각했는데.. 어림도 없지! ㅜㅜ 접근 방식 단순하게 생각하면, 매번 벽을 만날 때마다, 주변에 몇 개의 공간이 있는지 일일이 세면서 진행하는 방법도 생각해볼 수 있습니다. 하지만, 이렇게 하는 경우, O((N^3)(M^3)) 이라는 시간 복잡도를 얻게 됩니다. NM이 10만이라는 점을 고려해볼 때, 이 방법으로는 불가능하다는 결론에 이르게 됩니다. 그리고 저는 이를 미리 생각치 않아 시간 초과로 고생을 좀 했습니다.. 반면, 연결된 빈 방의 개수를 그룹별로 미리 한 번에 구해..

PS/BOJ 2021.06.09

[BOJ/12886/Golang] 백준 12886 - 돌 그룹

문제로 이동하기 https://www.acmicpc.net/problem/12886 여담 Gold 5 문제입니다. BFS에는 나름 자신감이 붙게 만들어준 문제입니다. 이제는 Gold도 두렵지 않다..! 뭐 이런거죠 ㅋㅋㅋ.. 사실 흔한 BFS 문제들과 비슷한 패턴으로 풀리는 문제라서.. 크게 어렵진 않습니다. 접근 방식 우선 상황에 대한 정리가 필요합니다. 현재 주어진 정점은 무엇이고, 가고자 하는 정점은 무엇인지 알아야 합니다. 그리고 현재 주어진 정점에서 이동할 수 있는 방법의 수, 다시 말해 간선의 종류는 어떻게 되는지 정리해볼 필요가 있습니다. 현재 주어진 정점 현재 주어진 정점은 당연하게도 (A, B, C) 입니다. 가고자 하는 정점 모든 그룹에 있는 돌의 개수를 같게 만드는 상황이 목표입니다...

PS/BOJ 2021.06.08

[BOJ/16947/Golang] 백준 16947 - 서울 지하철 2호선

문제로 이동하기 https://www.acmicpc.net/problem/16947 접근 방식 큰 순서는 다음과 같습니다. 그래프 내의 모든 사이클과 사이클에 속한 정점을 구한다. 사이클에 속한 정점에 연결된 정점들 중 사이클에 속하지 않은 정점을 방문하며 거리를 구한다. 하지만 이 문제에서 핵심은 사이클을 찾고, 사이클에 속한 정점을 구하는 과정입니다. 위 2번은 그저 찾아낸 정점으로부터 DFS 또는 BFS를 수행하면 쉽게 찾을 수 있습니다. 물론 DFS보다는 BFS로 찾는게 더 효율적입니다. 이유는 후에 설명 드리겠습니다. 트리 N개의 정점과 N-1개의 간선으로 이루어진 그래프는 트리입니다. 트리는 사이클이 없으며, 최단 경로를 DFS와 BFS로 구할 수 있습니다. 만약 이 트리에 간선이 하나 더 추..

PS/BOJ 2021.06.05

[BOJ/13549/Golang] 백준 13549 - 숨바꼭질 3 - BFS로 풀이

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

PS/BOJ 2021.06.04

[BOJ/14226/Golang] 백준 14226 - 이모티콘 - BFS로 풀이

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

PS/BOJ 2021.06.03

[BOJ/13913/Golang] 백준 13913 - 숨바꼭질 4

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

PS/BOJ 2021.06.02