코딩테스트/백준

[백준] 15989번

seung_ho_choi.s 2024. 2. 12. 22:51
728x90

사이트

https://www.acmicpc.net/problem/15686

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

문제 

 

분석

약 5시간만에 푼문제였다... 어렵지 않다 생각했는데 매우 복잡했던 문제였다.(리펙토링 무조건 보기!!)

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

입력이 다음과 같으면 출력은 10이 나와야된다.

 

즉 입력부분에서 치킨집 즉 2가 5개 이므로 이 중 2개를 뽑아 집 즉 1과 거리가 최소가 나는 기준으로 치킨집(2)를 2개 뽑아야되는게 핵심이다!

 

리펙토링 전

 

이해하는데 크게 어렵지 않았고 구현도 간단하게 보였다. 먼저 

static int n;

static int m;

static int[][] street;

static boolean[][] chickenVisit;

static int min;

static int result;

static int resultMin = Integer.MAX_VALUE;

- 다음과 같이 정적 변수를 선언했다. 

- boolean 배열은 백트래킹으로 치킨집 5개 중 2개를 고를 때 이미 고른건 빼기 위함이다.

- result는 아래 코드를 보면 이해가 갈것이다.

 

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    st = new StringTokenizer(br.readLine());

    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());

    street = new int[n][n];
    chickenVisit = new boolean[n][n];

    for (int i = 0; i < n; i++) {
        st = new StringTokenizer(br.readLine());
        for (int j = 0; j < n; j++) {
            street[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    backTracking(0);

    System.out.println(resultMin);
}

- 입력받고 backTracking 함수로 이동하고 결과를 얻는 메인메소드이다!

public static int backTracking(int depth) {
    if (depth == m) {
        result = 0;
        resultMin = Math.min(resultMin, calculation());
        return 0;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (street[i][j] == 2 && !chickenVisit[i][j]) {
                chickenVisit[i][j] = true;
                street[i][j] = 3;
                backTracking(depth + 1);
                street[i][j] = 2;
                chickenVisit[i][j] = false;
            }
        }
    }
    return 1;
}

- 본격적인 리뷰 시작! backTracking 함수 이다.

 

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (street[i][j] == 2 && !chickenVisit[i][j]) {
            chickenVisit[i][j] = true;
            street[i][j] = 3;
            backTracking(depth + 1);
            street[i][j] = 2;
            chickenVisit[i][j] = false;
        }
    }
}

for 문을 보면 방문하지 않는 치킨집을 토대로 if문에 들어와서 

boolean을 true로 바꾸고 값을 3으로 바꿨다. 왜냐하면 뒤에서 최종적으로 다시 계산하기 위함이다! 

그리고 backTracking 재귀함수 호출이 시작되고 끝났으면 다시 2와 false로 바꿔준다.

 

if (depth == m) {
    result = 0;
    resultMin = Math.min(resultMin, calculation());
    return 0;
}

재귀함수가 계속 호출하고 depth가 치킨집 개수랑 같으면 위 if 문이 실행되고 calculation() 메소드가 실행된다. 

 

public static int calculation() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (street[i][j] == 1) {
                min = Integer.MAX_VALUE;
                result += search(i + 1, j + 1);

            }
        }
    }
    return result;
}

이 메소드는 일반 집의 관한 좌표를 반복문으로 search() 메소드에다가 갖다 주는 역할을 한다.

 

public static int search(int x, int y) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (street[i][j] == 3) {
                int absX = Math.abs(x - (i + 1));
                int absY = Math.abs(y - (j + 1));
                int sum = absX + absY;
                min = Math.min(min, sum);
            }
        }
    }
    return min;
}

그 후 search() 메소드는 기존에 3으로 표시되었던 치킨집들을 일반집과 거리를 비교하면서 값이 sum 변수에 저장이되고  

즉 우리는 입력이 치킨집 2개를 뽑아야 되니깐

먼저 일반집1+ 치킨집1이  sum 변수에 저장이 되서 min에 저장이 되고

그 후 일반집1+ 치킨집2 이 sum 변수에 저장이되서 이전 min 이랑 비교해서 둘 중 최솟값이 최종적으로 return 하게 되면서 calcultion 메서드로 이동하게 된다.  

 

public static int calculation() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (street[i][j] == 1) {
                min = Integer.MAX_VALUE;
                result += search(i + 1, j + 1);

            }
        }
    }
    return result;
}

그럼 다시 여기서는  저장된 값들이 result로 합치면서 모든 일반집과 치킨집의 최소거리를 구할 수 있다. 

 

 

test케이스는 맞았고 이론도 완벽했고 이상도 없어 보였다. 하지만!!!!!

시간 초과가 계속 떴다.... 계속 아무리 바꿔도 바꿔도 줄지 않았다... 고민을 정말 많이했다. 

 

문제점1 

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (street[i][j] == 2 && !chickenVisit[i][j]) {
            chickenVisit[i][j] = true;
            street[i][j] = 3;
            backTracking(depth + 1);
            street[i][j] = 2;
            chickenVisit[i][j] = false;
        }
    }
ublic static int search(int x, int y) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (street[i][j] == 3) {
                int absX = Math.abs(x - (i + 1));
                int absY = Math.abs(y - (j + 1));
                int sum = absX + absY;
                min = Math.min(min, sum);
            }
        }
    }
    return min;
}

 

위 코드에서 굳이 치킨집을 3으로 바꿔서 search() 메소드에서 다시 3인것을 조회하면 시간초과가 당연히 발생한다. 

그래서 list를 하나 선언해서 3을 바꾸지말고 미리 담아두는게 낫다고 생각했다.

 

문제점2

public static int calculation() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (street[i][j] == 1) {
                min = Integer.MAX_VALUE;
                result += search(i + 1, j + 1);

            }
        }
    }
    return result;
}

위 방식과 유사하게 1을 전부 부르고 있다. 이 코드 어디서 많이 보지 않았나?? 

for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < n; j++) {
        street[i][j] = Integer.parseInt(st.nextToken());
    }
}

바로 입력부분이다. 입력할때 if문 써서 1인거 있으면 미리 list에 담아두면 시간낭비가 덜 할 거 같다. 

 

문제점1과 문제점2만 보완하면 불필요한 for문들을 줄일 수 있다. 

 

마지막 문제점 

위와 같은 문제점으로 해결을 해도 여전히 시간초과가 떴다...

 

백트래킹은 함수를 많이 호출한다. 즉 불필요한 함수 호출로 인해 시간초과가 발생할 수 있다. 

그러면 사전에 먼저 불필요한 함수를 제거를 하는게 맞다. 

 

너무 분하고 해결하고 싶어서 잘때 생각을 해봤는데 생각이났다!

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

 

위 입력문을 볼 때 치킨집은 5개고 이 중 2개를 뽑아서 최소를 구해야 된다.

이전 코드는 진짜 모든 경우의 수를 봤다. 이해하기 쉽게 입력 부분에서 치킨집을 좌표순으로 번호를 매기면 1 2 3 4 5 가 되는게

 

이전 코드는 

(1,2) (1,3) (1,4) (1,5)

(2,1) (2,2) (2,3) (2,4)

(3,1) (3,2) (3,4) (3,5)

(4,1) (4,2) (4,3) (4,5)

(5,1) (5,2) (5,3) (5,4)

 

위 표를 보듯이 순서와 상관없이 중복이 되는 치킨집들이 있다. ( (1,2) (2,1) 이런거!! )

 

즉 이거를 제거해야 된다. 좌표 크기를 비교하면서 제거하면 된다. 

제거하면 경우의 수가 총 10번이다. 이전 코드는 20번이었는데 말이다!!  

 

리펙토링 이후

static int n;

static int m;

static int[][] street;

static boolean[][] chickenVisit;
static int result;

static int resultMin = Integer.MAX_VALUE;
static int cnt;
static List<int[]> chicken;
static List<int[]> home = new ArrayList<>();

static int x, y;

위와 같이 정적 변수를 선언했다. x y는 차차 설명! 

 

for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < n; j++) {
        street[i][j] = Integer.parseInt(st.nextToken());
        if (street[i][j] == 1) {
            home.add(new int[]{i, j});
        }
    }
}

 

메인메소드는 이전 코드랑 유사하고 입력받은 부분에서 위와 같이 1일때 미리 list에 넣어주었다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (street[i][j] == 2 && !chickenVisit[i][j]) {
            if (!chicken.isEmpty()) {
                int[] pair = chicken.getLast();
                x = pair[0];
                y = pair[1];
            }
            if (chicken.isEmpty() || x <= i) {
                if (y <= j || x!=i) {
                    chickenVisit[i][j] = true;
                    chicken.add(new int[]{i, j});
                    backTracking(depth + 1);
                    chicken.removeLast();
                    chickenVisit[i][j] = false;
                }
            }
        }
    }
}

 

backTracking 함수에 for문 쪽이다. 차근 차근 보자! 

 

이전 코드와 동일하게 치킨집이고 방문하지 않는 치킨집만 if문으로 입장한다.

if (!chicken.isEmpty()) {
    int[] pair = chicken.getLast();
    x = pair[0];
    y = pair[1];
}

처음 만나는게 이 코드인데 chicken 리스트가 비어있지 않을때 들어온다. 

if (chicken.isEmpty() || x <= i) {
    if (y <= j || x!=i) {
        chickenVisit[i][j] = true;
        chicken.add(new int[]{i, j});
        backTracking(depth + 1);
        chicken.removeLast();
        chickenVisit[i][j] = false;
    }
}

즉 이 코드로 처음에 들어오게 된다. 그러면 처음들어온 치킨집의 좌표인(0,1)을 리스트에 넘겨주고 재귀함수를 호출한다. 

 

if (!chicken.isEmpty()) {
    int[] pair = chicken.getLast();
    x = pair[0];
    y = pair[1];
}

 

그럼 또 다시 이 코드로 오게 되는데 이번에 chicken 리스트가 안비워져 있다. 

그러면 리스트의 마지막 항목을 pair로 할당하고 각각 x(0) 랑 y(1) 를 얻게 된다.

이 코드는 위에서 언급했듯이 치킨집의 중복 경우의 수를 피하기 위함이다! 

 

if (chicken.isEmpty() || x <= i) {
    if (y <= j || x!=i) {
        chickenVisit[i][j] = true;
        chicken.add(new int[]{i, j});
        backTracking(depth + 1);
        chicken.removeLast();
        chickenVisit[i][j] = false;
    }
}

 

그럼 다시 여기로 와서 이번에 x<=i 일로 조건이 성립이 되면서 들어오게 된다. 이때 새로 들어온 좌표는 (1,0) 으로 가정하겠다. 

 

그럼 다음 또 if문에 걸리게 된다. (0,1) (1,0) 을 비교 하면 당연히 (1,0) 이 아래에 있기 때문에 더 크다고 판단해야 된다. 

y <= j || x!=i

 

그래서 위와 같은 조건을 걸어 두면 된다. 

그러면 또 다시 재귀함수를 호출하게 된다! 

 

backTracking(depth + 1);
chicken.removeLast();
chickenVisit[i][j] = false;

 

재귀함수 호출이 chicken 리스트의 마지막 원소를 제거해야된다.  그래야지 다음 원소들이 차례로 비교할 수 있기 때문이다. 

public static int calculation() {
    for (int[] home1 : home) {
        int min = Integer.MAX_VALUE;
        for (int[] chicken1 : chicken) {
            int absX = Math.abs(chicken1[0] - home1[0]);
            int absY = Math.abs(chicken1[1] - home1[1]);
            int sum = absX + absY;
            min = Math.min(min, sum);
        }
        result += min;
    }
    return result;
}

 그리고 이젠 depth가  치킨집의 개수 m이랑 같으면 위 메서드를 들어오게 된다. 

간단한 계산 문제고 이전 코드와 동일하게  result로 반환하면 

 

정답이 나오게 된다! 

 

 

전체 코드

package backtracking;

import java.io.*;
import java.util.*;

public class Back15989 {
    static int n;

    static int m;

    static int[][] street;

    static boolean[][] chickenVisit;
    static int result;

    static int resultMin = Integer.MAX_VALUE;
    static List<int[]> chicken;
    static List<int[]> home = new ArrayList<>();

    static int x, y;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        street = new int[n][n];
        chickenVisit = new boolean[n][n];
        chicken = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                street[i][j] = Integer.parseInt(st.nextToken());
                if (street[i][j] == 1) {
                    home.add(new int[]{i, j});
                }
            }
        }
        backTracking(0);
        bw.write(String.valueOf(resultMin));
        bw.flush();
        bw.close();
    }

    public static int backTracking(int depth) {
        if (depth == m) {
            result = 0;
            resultMin = Math.min(resultMin, calculation());
            return 0;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (street[i][j] == 2 && !chickenVisit[i][j]) {
                    if (!chicken.isEmpty()) {
                        int[] pair = chicken.get(chicken.size()-1);
                        x = pair[0];
                        y = pair[1];
                    }
                    if (chicken.isEmpty() || x <= i) {
                        if (y <= j || x!=i) {
                            chickenVisit[i][j] = true;
                            chicken.add(new int[]{i, j});
                            backTracking(depth + 1);
                            chicken.remove(chicken.size()-1);
                            chickenVisit[i][j] = false;
                        }
                    }
                }
            }
        }
        return 1;
    }

    public static int calculation() {
        for (int[] home1 : home) {
            int min = Integer.MAX_VALUE;
            for (int[] chicken1 : chicken) {
                int absX = Math.abs(chicken1[0] - home1[0]);
                int absY = Math.abs(chicken1[1] - home1[1]);
                int sum = absX + absY;
                min = Math.min(min, sum);
            }
            result += min;
        }
        return result;
    }
}

 

음 근데 백준에서는 

chicken.removeLast();
int[] pair = chicken.getLast();

 

위 두 메서드를 적용 할 수 없다해서 

int[] pair = chicken.get(chicken.size()-1);
chicken.remove(chicken.size()-1);

이렇게 바꿔줘야 된다...

 

결과

 

느낀점

 

와 백트래킹을 마스터했다고 느꼈는데 이 문제는 나를 한층더 발전시킨 문제였다. 

백트래킹은 시간 초과가 많이 일어나므로 불필요한 함수 호출을 제거해야 된다! 꼭!!! 

 

역시 골드다운 문제였다! 

728x90