안녕

0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 이전 풀이 2023.02.03 - [Computer Science/알고리즘] - [백준 - Python] 6087 - 레이저 통신 [백준 - Python] 6087 - 레이저 통신 0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 ..

0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 1. 풀이 방법 + 23.02.04에서 문제를 다시 채점하니 시간 초과가 났습니다.ㅜ 이 문제를 보고 맨 처음 떠오른 생각은 다익스트라였다. 최단 거리를 먼저 찾고, 최단 루트에서 방향이 바뀌는 부분이 거울이니까 그만큼 하면 되겠지 라는 생각을 했다. 하지만 이런 생각은 틀린게, 최단 루트가 최소 거울 개수를 보장하지 않는다! 아래 예시를 보자.. 중간으로 가는 루트가 가..