Java의 그래프 구현 예

이 기사에서는 처음부터 Java로 그래프 구현 예제를 볼 수 있습니다. Java에서 그래프 데이터 구조를 만들고 사용하는 방법을 배우고 많은 인터뷰 프로세스에서 본 실제 연습을 통해 연습합니다.

이 예는 흥미롭고 해결하기 어려운 문제입니다. 먼저 문제 자체와 Java에서 이를 해결할 수 있는 가능한 방법을 소개하겠습니다.

문제

배달 서비스 회사는 고객 주문을 배달하기 위해 배달 트럭의 경로를 계획하는 시스템을 만듭니다. 플래너는 그리드로 추상화된 각 주문에 대한 배송 영역을 생성합니다. 문제는 트럭이 주문을 배달하는 경로를 찾는 알고리즘을 작성하는 것입니다.

배송 지역은 정수의 2차원 그리드로 표시되며 여기서는 다음과 같습니다.

1은 액세스 가능한 영역을 나타냅니다

.

0은 액세스할 수 없는 영역을 나타냅니다

.

2는 주문 대상

을 나타냅니다.

이 연습은 올바른 데이터 구조를 사용하여 겉보기에 복잡한 문제를 훨씬 더 간단한 문제로 바꾸는 방법을 Java에서 보여주는 훌륭한 예입니다. 그래프 구현을 사용하면 문제가 더 간단해집니다.

시작하기 전에 고려해야 할 몇 가지 사항. 트럭은 그리드를 떠날 수 없으며 접근 가능한 영역을 통해 주문 목적지에 도착해야 합니다. 그리고 트럭은 한 번에 한 셀 위, 아래, 왼쪽 또는 오른쪽으로 이동할 수 있습니다.

다음은 입력 및 해당 출력이 있는 다양한 사례의 몇 가지 예입니다.

  Example 1
  grid = [[1,1,0],[0,1,2][0,1,1]]
  Output: [0,0][0,1][1,1][2,1][2,2][1,2]

  Example 2
  grid = [[1,1,1,1],[0,1,0,1],[0,1,0,1],[0,1,1,0],[0,1,2,1]]
  Output: [0,0][0,1][1,1][2,1][3,1][3,2]

해결책

이 문제에 대한 최상의 솔루션은 자바 그래프 구현을 사용하는 것입니다. 일반적으로 그래프는 그리드를 탐색해야 하는 모든 상황에 적합한 솔루션입니다.

이 솔루션에는 각 매트릭스 셀을 나타내는 Cell 클래스와 트럭이 탐색해야 하는 영역을 나타내는 DeliveryArea 클래스의 두 가지 클래스가 있습니다. 아래 스켈레톤, 클래스 및 메소드 서명만 참조하십시오. 다음 섹션에서 구현을 완료합니다.

public class Cell {
    public int row;
    public int col;

    public Cell(int row, int col){
        this.row = row;
        this.col = col;
    }

    public String hashKey(){
        return String.valueOf(this.row)+String.valueOf(this.col);
    }
}

import java.util.List;
import java.util.Map;

public class DeliveryArea {

    private final static int ACCESSIBLE_CELL = 1;
    private final static int NON_ACCESSIBLE_CELL = 0;
    private final static int DESTINATION = 2;

    public int[][] matrix;

    public DeliveryArea(int[][] matrix){
        this.matrix = matrix;
    }
    private Map<String, List<Cell>> buildGraph(){
        return null;
    }
    public List<Cell> findRoute(){
        return null;
    }
}

Check out the full solution