멍멍멍

배달 문제 배달 문제 최단거리 bfs dp 문제 요약 링크 : https://www.acmicpc.net/problem/1175 장애물(#)과 지나갈 수 있는 곳(.)으로 구성된 격자판안에 있는 시작점(S)에서 출발해서 두 군데(C)에 배달하는데 걸리는 최소시간을 구하는 문제다. 이때 같은 방향으로 두번 이동 할 수 없다는 조건이 붙는다. 접근 이 문제는 정해진 출발점에서 도착점까지의 최소 거리를 구하는 전형적인 최단거리 문제보다 어려워 보인다. 아래 두 조건 때문이다. 두 군데에 배달해야함 같은 방향으로 두번 이동할 수 없음 같은 방향으로 두번 이동할 수 없다는 조건은 각 지점의 상태를 들어온 방향을 기준으로 오른쪽(0), 오(1), 위(2), 아래(3)로 구체화해서 다음 지점으로 이동할 때 이 방향을..