섹션 8. DFS, BFS 활용 15. 피자배달거리(DFS)

문제

• N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다.
• 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다.
• 행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
• 도시에는 각 집마다 “피자배달거리”가 있는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는
• 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.
• 집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다.
• 예를 들어, 도시의 지도가 아래와 같다면

• (1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다.
• 최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다.
• 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.
• 시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.
• 도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

입력

• 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.
• 둘째 줄부터 도시 정보가 입력된다.

출력

• 첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

입출력 예제

---

풀이방식

이번 문제는 DFS에 대한 문제이다.

---

설계과정

1. ArrayList를 사용해서 집과 피자집의 좌표들을 저장한다.

2. 좌표값이 1이면 배열 hom에 해당 좌표값을 넣고, 2이면 배열 piz에 해당 좌표값을 넣는다.

3. 재귀를 이용해서 존재하는 피자집 중에서 M개의 피자집을 구한다.

4. L이 M과 같다면 첫번째 집과 살아남은 피자집들의 거리값들을 하나씩 다 구한다.

5. 이 때, 거리값중에서 최소값들을 sum 에 누적해서 도시의 피자 거리를 구한다.

6. 마지막으로 result와 sum 중에 최소값을 출력해서 결과를 구한다.

---

풀이과정

1. 각 변수들을 선언한다.

• 피자집의 개수 len 을 선언한다.
• M개의 피자집 combi[ ] 을 선언한다.
• 집의 좌표를 저장할 ArrayList hom 을 선언한다.
• 집의 좌표를 저장할 ArrayList piz 을 선언한다.
• 도시의 피자거리를 저장할 sum 을 선언한다.

2. tmp가 1이라면 배열 hom에 해당 좌표값을 넣고, 2이면 배열 piz에 해당 좌표값을 넣는다.

• 배열 hom은 집을 의미하므로 집의 좌표들을 add 한다.
• 배열 piz는 피자집을 의미하므로 피자집의 좌표들을 add 한다.

3. DFS 메소드를 작성한다.

 

4. L이 M과 동일하지 않다면 for문을 통해 재귀함수를 호출한다.

• L이 M과 동일하지 않다는 것은 M개 만큼의 피자집을 뽑아내지 못했다는 것이다.
• s 부터 len 까지 도는 for 문을 통해 combi[L] 배열에 i 값을 넣어서 콤비의 값 즉, 살아남은 피자집의 ArrayList index 번호를 넣는다.
• L+1, i+1을 DFS 함수의 파라미터로 넣어서 재귀함수를 호출한다.

5. L이 M과 동일하다면 도시의 최소거리를 구하는 코드를 작성한다.

• 필요로 하는 피자집을 모두 구했으므로 거리를 구해야한다.

6. hom 배열에서 값을 하나씩 꺼내는 for문을 작성한다.

•  집과 살아남은 피자집들의 거리값들을 하나씩 다 구하는 for문이다.

7. 그 안에 combi 배열에서 값을 하나씩 꺼내는 for문을 작성한다.

• 살아남은 피자집의 ArrayList index 번호를 꺼낸다.

8. 피자 배달 거리를 구하기 위해 Math.abs로 문제에 있는 거리를 구하고, Math.min 으로 최소값을 구한다.

• Math.abs() : 절대값을 리턴한다.
• Math.min() : 최소값을 리턴한다.
• piz 는 ArrayList 이므로 i 번째중에서 x, y 좌표값을 꺼내야 한다.
• hom에서 각 좌표인 h를 꺼냈으므로 h로 x, y 좌표값을 꺼낸다.

9. sum에 구한 최소 거리를 누적해서 더한다.

 

10. Math.min을 사용해서 result와 sum 중 최소값을 리턴한다.

---

더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.