[백준 / Java] 2665. 미로만들기
문제문제 링크풀이이 문제는 (0, 0) ~ (N-1, N-1)로 가는데 검은 방을 흰 방으로 최소한으로 바꾸면서 갔을 때, 방 색을 바꾼 횟수를 구하는 문제입니다.즉, 방의 색을 바꾸는 횟수를 가중치로 생각했을 때, 가중치를 최소화하면서 끝 방까지 가는 경우를 구하면 됩니다.만약 일반 bfs처럼 푼다면 (N-1, N-1)에 가장 먼저 도달했을 때 방의 색을 바꾼 횟수가 최소가 아닐 수 있습니다.예시: 아래의 경우, 방 색을 전혀 바꾸지 않고도 끝 방에 갈 수 있지만, 방문하는 순서에 따라 방 색을 바꾸는 루트로 가장 먼저 N-1, N-1에 도달할 수 있음따라서 이 문제에서는 흰 방으로 이동하는 것은 가중치가 0, 검은 방으로 이동하는 것은 가중치가 1이고 큐에 그 칸의 정보를 넣었을 때 가중치가 더 작은..
2024. 6. 11.
