티스토리 뷰
배달 문제
최단거리
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