인접리스트 구현 질문입니다.

Question

A star 알고리즘을 이용한 경로 탐색 소스가 있습니다. 그래프에 각 셀들은 Cell이라는 객체배열로 설계되어있습니다. S는 시작지점, B는 장애물, D는 목적지 입니다. S O O O O O O B O O O B D O O O O O O O Cell 객체 안에 그래프의 i행과 j열이라는 int형 변수를 이용해 S ( i=0, j=0) 기준으로 아래 칸 (i=1,j=0)과 오른쪽 칸 (i=0,j=1) 들을 탐색한 뒤 A Star 방식의 비용을 업데이트 합니다. 그런데 위 소스는 객체 배열을 통해서 그래프를 표현하고 있는데요 이것을 노드를 사용하는 소스로 바꾸고 싶습니다. 그럼 객체 배열들을 각각 노드로 바꾼 뒤 인접 셀들을 가리키는 변수를 선언해야 하는건가요? S = o = o || || || o = o = b || || || o = b = o 이렇게 된다면 가운데에 있는 셀은 위쪽,아래쪽,왼쪽,오른쪽을 가리키는 변수를 각각 가지고 있게 하면 되는건가요? 이 소스는 위쪽 칸의 AStar로 정하는 비용을 탐색하면서 업데이트 소스입니다. Cell t; if(current.i-1>=0){ t = grid[current.i-1][current.j];//t에 현재 칸의 위쪽 칸을 넣는다. checkAndUpdateCost(current, t, current.finalCost+V_H_COST); if(current.j-1>=0&&!(current.blockN&¤t.blockW)){ t = grid[current.i-1][current.j-1];//t의 현재 칸에 대각선 왼쪽위를 넣는다. checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST); } 여기서 current는 객체 Cell의 변수이며 객체를 저장한 큐에서 poll해서 사용하고 있습니다. 이 소스를 Linked List를 사용하는거로 바꾸려면 grid[current.i-1][current.j] // 위쪽 셀 검사 를 객체 배열에서 index로 위쪽을 검사하는것 대신 그 노드 기준으로 위쪽 예를 들면 class Cell{ private Node upNode } 를 만들어서 node.up으로 위쪽 노드를 가져오는 식으로 해야하나요? 답변 부탁드립니다. 아래는 현재 소스의 풀 소스입니다. import java.util.PriorityQueue; public class AStar { public static final int DIAGONAL_COST = 14; public static final int V_H_COST = 10; static class Cell{ boolean blockN = false; boolean blockS = false; boolean blockE = false; boolean blockW = false; int heuristicCost = 0; //Heuristic cost int finalCost = 0; //G+H int i, j; Cell parent; Cell(int i, int j){ this.i = i; this.j = j; } @Override public String toString(){ return "["+this.i+", "+this.j+"]"; } } //Blocked cells are just null Cell values in grid static Cell [][] grid = new Cell[5][5]; static PriorityQueue open; static boolean closed[][]; static int startI, startJ; static int endI, endJ; public static void setBlocked(int i, int j){ grid[i][j] = null; } public static void setStartCell(int i, int j){ startI = i; startJ = j; } public static void setEndCell(int i, int j){ endI = i; endJ = j; } static void checkAndUpdateCost(Cell current, Cell t, int cost){ if(t == null || closed[t.i][t.j])return;//t칸이 없거나. || t가 닫혀있다면 리턴 int t_final_cost = t.heuristicCost+cost; boolean inOpen = open.contains(t); if(!inOpen || t_final_cost=0){//위쪽에 블록이 있나 검사 t = grid[current.i-1][current.j]; if(t==null)current.blockN=true; } if(current.j-1>=0){//왼쪽에 블록이 있나 검사 t = grid[current.i][current.j-1]; if(t==null)current.blockW=true; } if(current.j+1=0){ t = grid[current.i-1][current.j];//t에 현재 칸의 위쪽 칸을 넣는다. checkAndUpdateCost(current, t, current.finalCost+V_H_COST); if(current.j-1>=0&&!(current.blockN&¤t.blockW)){ t = grid[current.i-1][current.j-1];//t의 현재 칸에 대각선 왼쪽위를 넣는다. checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST); } if(current.j+1=0){ t = grid[current.i][current.j-1];//왼쪽 검사 checkAndUpdateCost(current, t, current.finalCost+V_H_COST); } //y2 if(current.j+1=0&&!(current.blockS&¤t.blockW)){// t = grid[current.i+1][current.j-1];//t에 현재 칸의 왼쪽 아래 칸을 넣는다. checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST); } if(current.j+1((Object o1, Object o2) -> { Cell c1 = (Cell)o1; Cell c2 = (Cell)o2; return c1.finalCostc2.finalCost?1:0; }); //Set start position setStartCell(si, sj); //Setting to 0,0 by default. Will be useful for the UI part //Set End Location setEndCell(ei, ej); //객체배열을 돌면서 객체 배열 생성, 객체의 H값 부여 //H값 : 현재 for(int i=0;i "+current.parent); current = current.parent; } System.out.println(); }else System.out.println("No possible path"); } public static void main(String[] args) throws Exception{ //test(케이스 번호, x줄,y열,시작칸은x번째,y번째칸, 목적지는 x번째,y번째 칸, 블럭은 어디에?(배열)) test(1, 5, 5, 0, 0, 3, 2, new int[][]{{0,4},{2,2},{3,1},{3,3}}); test(2, 5, 5, 0, 0, 4, 4, new int[][]{{0,4},{2,2},{3,1},{3,3}}); test(3, 7, 7, 2, 1, 5, 4, new int[][]{{4,1},{4,3},{5,3},{2,3}}); test(1, 5, 5, 0, 0, 4, 4, new int[][]{{3,4},{3,3},{4,3}}); } }

인접리스트 구현 질문입니다.

0개의 답변

#linkedlist 목록