티스토리 뷰
배달 문제
최단거리 bfs dp
문제 요약
링크 : https://www.acmicpc.net/problem/1175
장애물(#)과 지나갈 수 있는 곳(.)으로 구성된 격자판안에 있는 시작점(S)에서 출발해서 두 군데(C)에 배달하는데 걸리는 최소시간을 구하는 문제다. 이때 같은 방향으로 두번 이동 할 수 없다는 조건이 붙는다.
접근
이 문제는 정해진 출발점에서 도착점까지의 최소 거리를 구하는 전형적인 최단거리 문제보다 어려워 보인다. 아래 두 조건 때문이다.
- 두 군데에 배달해야함
- 같은 방향으로 두번 이동할 수 없음
같은 방향으로 두번 이동할 수 없다는 조건은 각 지점의 상태를 들어온 방향을 기준으로 오른쪽(0), 오(1), 위(2), 아래(3)로 구체화해서 다음 지점으로 이동할 때 이 방향을 사용하지 않도록 해서 쉽게 해결 할 수 있다.
두 군데 배달해야한다는 조건이 처음 문제를 접했을 때 까다롭게 느껴졌는데 이를 두가지 방법으로 접근해서 해결했다.
- dp 배열을 정의해서 푸는 방법
- bfs 탐색시 상태를 구체화해서 정의하는 방법 (훨씬 간단함)
백준온라인저지에 이 문제가 dp 문제로 분류되있어서 문제를 처음 보고 첫번재 풀이인 dp 방식으로 접근했는데 두번째 풀이가 훨씬 간단하다.
풀이1
dp 배열을 정의해서 푸는 방법
두 C지점을 C1, C2로 이름을 붙여 부르기로 하자.
이때 시작점에서 출발해서 두 군데를 들렀다 가는 방법은 아래 두가지 방법 중 하나다.
- S -> C1 -> C2
- S -> C2 -> C1
위 경로를 S->C1, S->C2 / C1->C2, C2->C1 로 나누어 각각 구한 후 합치도록 하자.
S -> C1, S -> C2 이동 최소시간을 구하기 위해 dp 배열을 다음과 같이 정의한다.
dp[0][i][j][k] : 시작점에서 부터 출발해서 k방향으로 (j,i) 점에 들어올 때 이동한 최단거리
C1 -> C2 이동 최소 시간을 구하기 위해 다음과 같이 정의한다.(C2->C1이동 최소시간은 C1->C2이동 최소시간과 동일하기 때문에 하나만 구한다.)
dp[1][i][j][k] : C1에서 부터 출발해서 k방향으로 (j,i) 점에 들어올 때 이동한 최단거리
( k방향은 0(왼쪽), 1(오른쪽), 2(위), 3(아래)를 말한다. )
그리고 최단거리를 구하는 bfs 탐색을 통해 위 dp배열을 채운다.
그리고 dp[0][i][j][k]과 dp[1][i][j][k]을 이용해서 위 1, 2 방법의 경로를 선택했을 때 걸리는 최소시간을 얻을 수 있다.
- S -> C1 -> C2 경로 : dp[0][C1.y][C1.x][k1] + dp[1][C2.y][C2.x][k2] (12가지)
- S -> C2 -> C1 경로 : dp[0][C2.y][C2.x][k1] + dp[1][C1.y][C1.x][k2] (12가지)
(이때 k1과 k2는 다르고 0이상 3이하의 정수이다.)
위 24가지의 조합 중 답이 반드시 존재하고 그 중 최솟값이 답이된다.
소스 보기
풀이2
풀이1보다 훨씬 간단하다.
bfs탐색을 이용한 최단거리 구하는 전형적인 문제를 푸는 과정과 크게 다르지 않다.
두 C를 구분하기 위해 둘 중 하나를 C, 나머지 하나를 K라 하자.
현재 지점에 어떤 방향으로 진입했는가와 C와 K를 지났는지 여부를 구체화하여 상태로 같이 담아주고 전형적인 bfs탐색을 이용한 최단거리 구하는 문제 풀이 과정을 진행하면 된다.
이때 동일한 상태에 2번 이상 진입하는 것을 막기 위해 구체화된 visited배열을 다음과 같이 정의한다.
visited[i][j][k][c][k] : (j, i) 지점에 k방향으로 진입한다. 이때 C와 K를 지났는지 여부를 c와 k에 0, 1로 담는다.
예시) visited[5][2][3][0][1] : 현재 (2,5) 지점에 아래 방향으로 진입한 상태인데 c는 아직 안들렀고 k는 이미 들른 상태이다.
소스 보기
- Total
- Today
- Yesterday