📎 문제링크 백준 3055번 🤔 문제 이해 및 알고리즘 유형 비버와 물이 동시에 상하좌우로 이동한다. 이때 1) 비버는 물과 바위를 뛰어 넘을 수 없음 2) 물은 둥지와 바위를 덮을 수 없음 결과적으로 비버가 둥지에 도착하는 가장 최소 시간을 구하는 문제 알고리즘 유형 BFS 💡 문제 해결 방법 물과 비버가 동시에 이동해야 하기 때문에 큐를 2개로 설정해서 저장 1) roadmap을 먼저 탐색하면서 물이 나오면 water 큐에 삽입 2) 비버의 위치가 나오면 start 지점으로 저장 or q(큐)에 삽입 3) D(둥지의 위치)가 나오면 end 지점으로 저장 bfs를 수행 -> 비버와 물이 동시에 이동하는게 포인트!! 1) 물을 따로 bfs 수행 2) 비버도 따로 bfs 수행 💻 코드 처음 작성한 코드 i..
전체 글
📎 문제링크 백준 7569번 🤔 문제 이해 및 알고리즘 유형 상자 안에 있는 토마토가 모두 익는 날짜를 출력하는 문제 단, 상하좌우,위아래에 접해 있는 토마토만 익을 수 있으며, 모두 익는데 가장 최소한의 날짜를 출력하는 문제 알고리즘 유형 BFS 💡 문제 해결 방법 BFS로 문제를 푸는 것은 알았지만 DAY를 어떻게 계산해줘야 할지 몰라 어려웠다. 생각하지 못한 점 1) 익은 토마토의 좌표를 true_deque에 저장할 것 2) 익지 않은 토마토의 갯수를 unripe에 저장할 것 3) 처음상태에서- 토마토가 모두 다 익었을 상황, 익은 토마토가 없는 상황 고려 4) bfs를 다 돌린 상태에서 - 토마토가 모두 다 익었을 상황에는 day를 출력, 다 돌렸음에도 익지 않은 토마토가 있을 경우 -1 출력 5..
보호되어 있는 글입니다.
보호되어 있는 글입니다.
보호되어 있는 글입니다.
참고사이트 : 다익스트라 알고리즘 나무위키- 다익스트라 알고리즘 다익스트라 최단경로 with Python 다익스트라 알고리즘이란? 다익스트라 알고리즘은 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신 하는 알고리즘이다. 즉, 가장 적은 비용으로 빠르게 정답에 도달하는 경로를 찾아내는 문제에서 주로 사용한다. 그림으로 살펴 보자. 1.아직 확인되지 않은 거리는 전부 초기값을 무한으로 설정한다. 2.루프를 돌려 이웃 노드를 방문하고 거리를 계산한다. 3.각 경로의 비용을 누적으로 저장한다. 이때 저장한 값이 다른 경로와 비교했을 때 작으면 가장 작은 값으로 업데이트를 진행한다. 4.계속 반복 후 목표점까지의 최단 거리를 찾는다. 다익스트라 알고리즘 구현 방법 1. 순차탐색 시간복잡도 : O(n^2)- 일일..