DeJa
Techvu
DeJa
전체 방문자
51,021
오늘
19
어제
54
  • Techvu (60)
    • DesignPatterns (3)
      • 생성 (0)
      • 구조 (1)
      • 행동 (2)
    • Refactoring (0)
    • DataStructures (0)
    • Algorithms (24)
      • 기본 지식 (12)
      • 문제 풀이 (12)
    • OOP (0)
    • TDD (2)
    • DDD (0)
    • Programming Languages (9)
      • Java (9)
      • Kotlin (0)
    • Spring (1)
    • JPA (7)
    • Web (1)
      • 기본 지식 (1)
      • 실무 경험 (0)
    • CS (12)
      • Network (1)
      • OS (8)
      • DataBase (3)
      • Server (0)
    • Git (1)
    • Conferences (0)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

  • Study
  • GitHub
  • Medium Blog

인기 글

  • 스키마(Schema)
    2022.01.08
    스키마(Schema)
  • 자바 버전별 역사 및 특징
    2022.01.12
    자바 버전별 역사 및 특징
  • 깃허브 사용 방법
    2021.12.15
    깃허브 사용 방법
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • JPA 는 과연 1차 캐시를 통해서 Repeatable R⋯
    2021.12.27
    JPA 는 과연 1차 캐시를 통해서 Repeatable R⋯

태그

  • DATABASE
  • OS
  • network
  • java
  • 알고리즘
  • JPA
  • 디자인패턴
  • TDD
  • web
  • CS
  • Spring

최근 댓글

  • 글 잘읽고 가요.
    아이폰
  • 컴파일러자체에서 꼬리재귀를 지원하지 않으니 static으로⋯
    aaa
  • 압도적 감사
    ㅇㅇㅇ

최근 글

  • Write a test code right now
    2022.03.24
    Write a test code right now
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • POJO, JavaBean, Entity, VO, DTO
    2022.02.08
    POJO, JavaBean, Entity, VO, DTO
  • TDD with Agile
    2022.02.05
    TDD with Agile
  • Java Stream 기초
    2022.01.23
    Java Stream 기초

티스토리

hELLO · Designed By 정상우.
DeJa

Techvu

[BOJ 15686] 치킨 배달
Algorithms/문제 풀이

[BOJ 15686] 치킨 배달

2022. 1. 3. 21:58
728x90

치킨 배달

BOJ 15686 : 치킨 배달

해설

✔ N X N 크기의 도시 존재
✔ 도시는 1 X 1 크기
✔ 도시의 각 칸은 좌표 형태(r,c) 이며 '빈칸' OR '치킨집'
✔ r 과 c 는 1부터 시작
✔ 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
✔ 도시의 치킨 거리는 모든 집의 치킨 거리의 합
✔ (r1, c1) 과 (r2, c2) 사이의 거리는 Math.abs((r1 - r2) + (c1 - c2))
✔ 0은 빈칸, 1은 집, 2는 치킨집

# 입력 예시 1번
(1, 1, #0) (1, 2, #0) (1, 3, #HOUSE) (1, 4, #0) (1, 5, #0)
(2, 1, #0) (2, 2, #0) (2, 3, #CHICKEN) (2, 4, #0) (2, 5, #HOUSE)
(3, 1, #0) (3, 2, #HOUSE) (3, 3, #CHICKEN) (3, 4, #0) (3, 5, #0)
(4, 1, #0) (4, 2, #0) (4, 3, #HOUSE) (4, 4, #0) (4, 5, #0)
(5, 1, #0) (5, 2, #0) (5, 3, #0) (5, 4, #0) (5, 5, #CHICHKEN)

1,3,HOUSE 의 치킨 거리 값은 1
2,5,HOUSE 의 치킨 거리 값은 2
3,2,HOUSE 치킨 거리 값은 1
4,3,HOUSE 치킨 거리 값은 1

도시의 치킨 거리 최솟값 = 모든 집의 치킨 거리의 합(1 + 2 + 1 + 1)

# 입력 예시 2번
(1, 1, #0) (1, 2, #CHICKEN) (1, 3, #0) (1, 4, #HOUSE) (1, 5, #0)
(2, 1, #HOUSE) (2, 2, #0) (2, 3, #HOUSE) (2, 4, #0) (2, 5, #HOUSE)
(3, 1, #0) (3, 2, #0) (3, 3, #0) (3, 4, #0) (3, 5, #0)
(4, 1, #CHICKEN) (4, 2, #0) (4, 3, #0) (4, 4, #HOUSE) (4, 5, #HOUSE)
(5, 1, #CHICKEN) (5, 2, #CHICKEN) (5, 3, #0) (5, 4, #HOUSE) (5, 5, #CHICHKEN)

여기서 치킨집 2개만 남기고 폐업 -> 그러면 2개를 남길 치킨집을 선택해야 함

현재 그래프에서 치킨집을 자료구조 형태로 표현하면 다음과 같음.

chickens = { (1,2), (4,1), (5,1), (5,2), (5,5) }

chickens(치킨집 좌표를 담고 있는 리스트)에서 5개 중에서 2개를 선택해야 하니 조합을 사용해야 함

조합은 서로 다른 n 개의 원소를 가지는 어떤 집합 에서 순서에 상관없이 r 개의 원소를 선택하는 것

이렇게 선택된 2개는 각 집으로부터 치킨 거리를 구할때 사용, 따라서 이중 반복문 필요

dfs() {
    int result = 0;
    for(집) {
        int temp = INTEGER.MAX_VALUE;
        for(치킨집) {
            if(조합으로 선택된 치킨집) {
                // 집과 선택된 치킨집과의 최소 거리가 temp 에 담긴다.
                거리 = Math.abs(집x - 치킨x) + Math.abs(집y - 치킨y);
                temp = Math.min(temp, 거리);
            }
        }
        // 최소 거리의 합 = 도시의 치킨 거리의 최솟값
        result += temp;
    }
    // 기존 answer 에 담긴 도시의 치킨 거리 최솟값과
    // 조합으로 선택된 도시의 치킨 거리 최솟값을 비교하여 작은 값을 answer 로 갱신
    answer = Math.min(answer, result);
}

조합을 사용하여 부분 집합 구하기

구현

public class Main {

    static int N;
    static int M;
    static final int HOUSE = 1;
    static final int CHICKEN = 2;
    static int[][] graph;
    static List<Position> houses = new ArrayList<>();
    static List<Position> chickens = new ArrayList<>();
    static boolean[] visited;
    static int answer = Integer.MAX_VALUE;

    static class Position {
        private int x;
        private int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

    public static void main(String[] args) {
        input();
        combinationByDfs(chickens, visited, 0, M);
        System.out.println(answer);
    }

    static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        graph = new int[N + 1][N + 1];

        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                int value = sc.nextInt();
                graph[r][c] = value;
                if(value == HOUSE) {
                    houses.add(new Position(r, c));
                }
                if(value == CHICKEN) {
                    chickens.add(new Position(r, c));
                }
            }
        }
        visited = new boolean[chickens.size()];
    }

    /**
     * 조합을 이용하여 부분집합 구하기
     * @param chickens 치킨 집
     * @param visited 해당 원소를 사용하는지 여부
     * @param currentIndex 현재 인덱스
     * @param r 뽑을 개수
     */
    static void combinationByDfs(List<Position> chickens, boolean[] visited, int currentIndex, int r) {
        if(r == 0) {
            calculateMinDistance(chickens, visited);
            return;
        }
        if(currentIndex == chickens.size()) {
            return;
        } else {
            visited[currentIndex] = true; // currentIndex 에 해당하는 원소를 사용한다라는 의미
            combinationByDfs(chickens, visited, currentIndex + 1, r - 1);

            visited[currentIndex] = false; // currentIndex 에 해당하는 원소를 사용하지 않는다라는 의미
            combinationByDfs(chickens, visited, currentIndex + 1, r);
        }
    }

    // 도시의 치킨 거리 최솟 값 계산하기
    static void calculateMinDistance(List<Position> chickens, boolean[] visited) {
        // 집과 치킨 집을 비교
        int result = 0;
        for (int i = 0; i < houses.size(); i++) {
            int temp = Integer.MAX_VALUE;
            for (int k = 0; k < chickens.size(); k++) {
                if(visited[k]) { // 치킨 집은 조합으로 선택된 치킨집이어야 함
                    int distance = Math.abs(houses.get(i).x - chickens.get(k).x)
                            + Math.abs(houses.get(i).y - chickens.get(k).y);
                    temp = Math.min(temp, distance);
                }
            }
            result += temp; // 도시의 치킨 거리 누적
        }
        answer = Math.min(answer, result);
    }
}
728x90
저작자표시 비영리 동일조건
  • 카카오스토리
  • 트위터
  • 페이스북

'Algorithms > 문제 풀이' 카테고리의 다른 글

이것이 코딩테스트다 : 금광  (0) 2022.01.07
[BOJ 14502] 연구소  (0) 2022.01.06
[BOJ 16234] 인구 이동  (0) 2021.12.31
[BOJ 1715] 카드 정렬하기  (0) 2021.12.18
[BOJ 18352] 특정 거리의 도시 찾기  (0) 2021.12.18
    'Algorithms/문제 풀이' 카테고리의 다른 글
    • 이것이 코딩테스트다 : 금광
    • [BOJ 14502] 연구소
    • [BOJ 16234] 인구 이동
    • [BOJ 1715] 카드 정렬하기
    알고리즘
    DeJa
    DeJa
    Tech Blog
    댓글쓰기
    [BOJ 14502] 연구소
    다음 글
    [BOJ 14502] 연구소
    [BOJ 16234] 인구 이동
    이전 글
    [BOJ 16234] 인구 이동

    티스토리툴바