기록장

문제https://www.acmicpc.net/problem/2665n*n 바둑판에서 검은 방(벽면)을 뚫어 시작점(0*0)부터 끝점(n-1, n-1)까지 갈 때, 뚫는 벽의 최소 개수를 구하는 문제이다.풀이0-1 BFS 알고리즘이 문제는 0-1 BFS 알고리즘을 사용하여 풀 수 있는 문제다. 간선의 가중치가 모두 다를 때 다익스트라로 최단 거리를 찾을 수 있었다면,간선의 가중치가 다르긴 한데 0과 1밖에 없는 경우 다익스트라보다 더 효율적인 방법으로 0-1 BFS를 쓸 수 있다. 이 블로그에 내용이 잘 정리되어있다.https://krrong.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-0-1-BFS [알고리즘] 0-1 BFS📌 Intro 0-1 B..

보호되어 있는 글입니다.

오늘 시험에 다익스트라가 나온대서 정리하고 넘어가려고 한다.예전에 최소비용 구하기 풀면서 정리해둔 글이 있어서 풀이를 가져왔다.  https://nkdev.tistory.com/74 [백준/Java] 1916번 : 최소비용 구하기🌵 문제 분석https://www.acmicpc.net/problem/1916출발 도시 번호, 도착 도시 번호가 A, B로 주어질 때 A에서 B까지 가는 데 드는 최소 비용을 출력하여라.입력 :N(도시의 개수)M(버스의 개수)a(출발 도시 번nkdev.tistory.com 💡가중치가 있는 그래프의 최단 거리를 구할 때는 다익스트라를 사용  최단 거리를 구할 거면 BFS를 쓰면 되는데 왜 다익스트라를 또 배우는가? 일반적인 BFS는 가중치를 고려하지 않는다. 간선 가중치를 고려..