문제 유형
n*n 크기의 격자판이 있다.
집은 1, 피자집은 2, 거리는 0으로 표시될 때
피자집과 집의 거리 즉, 피자 배달 거리는
|x1-x2| + |y1-y2|이다.
경제가 좋지 않아 전체 피자집에서 m개의 피자집만 살리고 나머지 피자집은 폐업하려고 한다.
m개의 피자집을 살렸을 때최소 도시 피자 배달 거리를 구하라.
필요 핵심 자료구조
int m // (살릴 피자집 갯수),
int[] px, py // (피자집 좌표를 담아둘 배열),
int cnt // (전체 피자집에서 m개의 피자집만 선택해서 조합할 때 전체 피자집 갯수를 알아야 하므로 선언한 변수),
int[] resultX, resultY // (전체 피자집에서 m개의 피자집을 선택한 경우를 담는 배열),
int temp1, temp2 // (피자 배달 거리를 담아둘 변수 |x1-x2| + |y1-y2|),
int temp3 // (하나의 집에서 모든 피자집으로 향하는 피자 배달 거리 중 최소 피자 배달 거리),
int temp4 // (각 집집마다 나온 temp3 값을 temp4에 모두 저장하기 위함 즉, 도시 피자 배달 거리),
DFS() 메서드 // 핵심 로직,
int result // 출력,
핵심 문제 해석
첫째 도시의 피자배달거리가 최소가 되는 경우를 구해야 한다.
그리고 m개의 피자집만 살리고 나머지는 폐업시킨다.
이 말은 즉슨, 조합의 경우를 생각해볼 수 있다.
둘째 최소 도시 피자 배달 거리를 구해야한다.
즉, 조합에서 나온 모든 경우의 도시 피자 배달 거리를 구하고,
그 중 최소 배달 거리를 결과로 출력해야 한다.
문제 풀이 과정
전체 피자집 갯수에서 m개 만큼만 살리고 나머지는 폐업하므로
조합을 생각했다.
예를 들어 6개의 피자집이 존재하는데 4개의 피자집만 살리고 나머지는 폐업한다면
6C4의 경우의 수가 존재하게 된다.
일단 전체 피자집의 좌표를 구해야 하므로
격자판에서 값이 2인 좌표를 담아줄 px, py 배열을 선언했다.
// 값이 2인 좌표 저장하기
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(arr[i][j] == 2){
px[cnt] = i;
py[cnt] = j;
cnt++;
}
}
}위 코드에서 cnt는 전체 피자집 갯수라고 생각하면 편하다.
px, py 배열은 n*n 크기로 설정해두었기 때문에 cnt 값을 통해 전체 피자집 갯수를 파악해야 한다.
n*n으로 설정한 이유는 격자판 안에 있는 모든 값이 2일 수도 있기 때문이다.
위 코드로인해 전체 피자집 좌표가 px, py에 담기게 되었다.
아래는 6개의 피자집이 있다고 가정했을 때 px, py 1번 인덱스부터 피자집 좌표를 담아둔 결과 값이다.
cnt의 경우 cnt++로 선언되어 있어서 마지막 피자집 좌표를 찾게되면 ++을 수행하게 되면서 6 -> 7로 반환된다.
위 px, py를 해석해보자면 1,2,3,3,4,4 는 x좌표를
3,3,2,4,1,4 는 y좌표를 의미한다.
이제 모든 피자집에서 m개의 피자집을 선택해야 한다.
그 로직은 아래와 같다.
for(int i = s; i < cnt; i++){
resultX[L] = px[i];
resultY[L] = py[i];
DFS(L+1, i+1);
}위와 같이 DFS를 사용해서 전체 피자집 중 m개를 선택하는 경우를 구할 수 있는데, 중요한건 아래와 같이 조건을 걸어야 한다.
if(L == m)만약 L == m이 되기 전까지만 for문을 돌려서 경우의 수를 찾고
L == m이 되었다는 것은 m개의 피자집을 선택했다는 의미이므로
문제 풀이 로직을 선언해야 한다.
그리고 위 코드에서 for문을 바라보면 i = s로 되어있는데,
s는 start를 의미한다.
public void DFS(int L, int s) {DFS가 위처럼 선언되어 있다. for문 안을 보면 아래와 같이
DFS(L+1, i+1);로 선언되어 있다.
i+1 부터 start 하라는 의미를 가진 for문이다.
이렇게 설정한 이유는 이미 선택한 조합의 경우를 반복해서 뽑는 경우를 방지하기 위함이다.
즉, 중복이 되는 경우를 방지하기 위함이다.
이제 거의 다 끝나간다.
마지막으로 각 조합의 경우마다 최소 도시 피자 배달 거리를 구하는 로직을 짜야 한다.
로직은 아래와 같이 선언했다.
if(L == m){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(arr[i][j] == 1){
int temp1;
int temp2;
temp3 = n;
for(int k = 0; k < L; k++){
if(i < resultX[k]) temp1 = (resultX[k] - i);
else temp1 = i - resultX[k];
if(j < resultY[k]) temp2 =(resultY[k] - j);
else temp2 = j - resultY[k];
temp3 = Math.min(temp3, temp1+temp2);
}
temp4 += temp3;
}
}
}
result = Math.min(result, temp4);
temp4 = 0;
}L == m 즉, m개의 피자집을 선택했을 때 로직이 실행된다.
이중 for문을 선언한 이유는 집의 좌표 위치를 찾기 위함이다.
아래 조건문을 보면 좌표 값이 1일 때 로직을 수행한다.
즉, 좌표 값이 집일 때 로직을 수행한다.
if(arr[i][j] == 1){temp1과, temp2는 피자 배달 거리를 담아둘 변수를 의미한다.
위 문제에서 얘기한 |x1-x2| + |y1-y2|와 같은 의미다.
i, j 좌표에서 전체 피자집으로 모두 이동해본 다음에 가장 적은 값을 temp3에 담는 것이다.
아래 그림을 보면 이해가 쉬울 것이다.
1,2의 좌표에서 모든 피자집으로 이동해봤을 때 피자 배달 거리가 최소가 되는 곳을 temp3에 담는다는 것이다.
1,2 좌표에서 최소 피자 배달 거리를 구했다면
다음 집인 2,1 좌표에서도 최소 피자 배달 거리를 구하고
그 다음 집에서도 최소 피자 배달 거리를 구하고
...
모든 집에서 최소 피자 배달 거리를 구해야 한다.
for문을 빠져 나갔다는 것은, 해당하는 집에서 모든 피자 배달 거리를 돌아봤고 최소 피자 배달 거리를 temp3에 담아줬다는 의미이다.
temp3에 담긴 최소 피자 배달 거리를
temp4에 저장해줘야 한다.
왜냐하면 문제에서는 최소 도시 피자 배달 거리를 구해야 하기 때문이다.
따라서 각각의 모든 집에서 구한 최소 피자 배달 거리를
temp4에 더해줘야 한다.
이렇게 temp4 값을 result에 담는다.
여기서 끝난게 아니다.
우리는 6개의 전체 피자집에서 4개의 피자집을 선택한 1개의 경우로 로직을 처리한 것이다.
이제 우리는 총 15가지의 조합의 경우의 수에서 1개의 경우를 구해본 것이다.
나머지 14개의 조합의 경우의 수를 모두 구한 뒤에
그 안에서 최소 도시 배달 거리를 구한 값을 result에 담아주고
main 함수에서 result를 반환해주면 되는 문제였다.
핵심 코드
public void DFS(int L, int s) {
if(L == m){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(arr[i][j] == 1){
int temp1;
int temp2;
temp3 = n;
for(int k = 0; k < L; k++){
if(i < resultX[k]) temp1 = (resultX[k] - i);
else temp1 = i - resultX[k];
if(j < resultY[k]) temp2 =(resultY[k] - j);
else temp2 = j - resultY[k];
temp3 = Math.min(temp3, temp1+temp2);
}
temp4 += temp3;
}
}
}
result = Math.min(result, temp4);
temp4 = 0;
}
else{
for(int i = s; i < cnt; i++){
resultX[L] = px[i];
resultY[L] = py[i];
DFS(L+1, i+1);
}
}
}개선된 점
첫번째 자료구조와 알고리즘을 그려나가는 능력이 많이 좋아졌다.
예전 같았으면 이해가 안되는 문제는 바로 정답을 봤을텐데,
지금은 문제가 어려워도 내가 알고있는 알고리즘이라면
풀다보면 정답 패턴이 보이기 때문에
계속해서 문제를 풀어나갈 수 있는 힘이 생긴 것 같다.
피드백, 개선할 점
첫째 문제를 이해하는데 오랜 시간이 걸렸다.
처음에는 m이 왜 주어지는지 이해하지 못했었다.
그래서 필요한 알고리즘을 놓친채 문제를 풀어나갔었다.
문제를 잘못 해석하는 일은 비일비재하다.
하지만,
문제를 풀어나가면서 자신이 문제를 제대로 이해하고 있는지,
문제에서 어떤걸 요구하는지 계속해서 체크하는 훈련을 하면 좋을 것 같다.
느낀점
첫번째 삼성 SW 역량평가 문제여서 그런가.. 내게는 난이도가 너무 높았다.
푸는데 하루 2시간씩 4일이나 걸렸다..
그래도 포기하지 않고,
계속 풀어서 정답을 찾아낸 스스로에게 칭찬해주고 싶다.
