너비 우선 탐색 4

[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/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