[Java] 알고리즘 - 지하철 노드 탐색 (연결리스트, 트리 탐색 응용)

안녕하세요. 명월입니다.

이 글은 Java에서 지하철 노드 탐색 (연결리스트, 트리 탐색 응용) 알고리즘에 대한 글입니다.

사실 이 글은 최초 4년전에 작성한 글인데 정말 아무 생각 없이 작성했었는데 의외로 많은 사람들이 참고하는 듯하네요.

이전에 소스도 너무 정리도 안되어 있었고(패턴 적용이 안되어 있음), 에러도 발생한다고 해서 다시 작성했습니다.

먼저 이 소스를 처음 만든 이유는 그 때 맡았던 프로젝트가 고속도로 요금 징수 프로그램을 만들었습니다.

그게 일본 고속도로라서 한국 고속도로 요금 징수표와는 다를 듯합니다. 각 톨게이트에서 입차, 출차의 거리를 계산하여 도로 요금을 계산하는 것입니다.

한국 고속도로는 아마 고속도로 내에서 빙빙 도는 게 불가능 할 듯하지만, 일본은 고속도록가 꽤 엉겨있어　고속도로 내에서 빙빙 도는 게 가능합니다. 그러다 보니 고속도로 요금을 계산하기가 어려운데, 그냥 입차 톨게이트에서 출차 톨게이트까지의 가장 싼 요금로 계산을 해서 징수합니다.

이건 dijkstra알고리즘입니다. 사실 이 알고리즘을 만들 당시에는 몰랐었는데 담당자한테 물어보니 dijkstra 알고리즘이 맞다고 합니다.(어떤 분이 댓글에 달아주셔서 알았습니다. 감사합니다.)

참고로 일본 고속도로는 사도로가 많아서 각 도로마다 요금이 다르기 때문에 꼭 짧은 거리가 싼 것은 아닙니다. 구간마다 요금이 다 틀린데 예를 들면 서울에서 대전까지 1만원이고 대전에서 광주까지 1만원입니다. 대전에서 부산을 거쳐 광주로 가면 5천원이라고 합시다.

거리는 서울 부산 광주가 더 길지만 요금이 싸다고 하면 실제 자동차가 서울에서 광주까지 갔을 때 요금을 2만원을 내보내는게 아니고 1만5천으로 계산해서 내보내 줍니다.

더 이상의 프로젝트 내용은 기밀이라 자세하게 설명은 못하는데 그 당시에 제가 퇴근길에 일본 지하철 노선을 보니 비슷하더라고요.

한국 지하철로 예를 들면 2호선은 순환 지하철이라 제가 노원이서 탑승을 하고 사당에서 내린다고 하면 마음먹으면 하루 종일 빙빙도는게 가능합니다. 그럼 어떻게 요금을 징수할까하는 게 문제인데. 한국은 구간마다 가격차이가 없을 테니 그냥 최단 거리를 계산해서 요금을 징수하는 방식을 택할 것입니다.

고속도로와 지하철의 차이는 고속도로는 입차에서 출차까지 거치는 톨게이트가 없이 거리 계산으로 계산하는데, 지하철은 각 역마다 노드가 정해져 있으니 계산이 더 편합니다.

누가 또 질문을 하셔서 실제 톨게이트에서는 차가 지나갈 때마다 이 알고리즘을 돌려서 계산을 해버리면 속도가 엄청나게 느립니다. 그래서 처음 계산할 때는 알고리즘을 돌리고 데이터를 모두 데이터 베이스에 넣습니다.

예를 들면 서울에서 광주는 1만5천원, 서울에서 대전은 1만원 서울에서 부산은 1만2천원, 대전에서 부산은 2천원 이런식으로 계산이 끝난 결과를 데이터 베이스에 넣고 실제 톨게이트에서는 입차 톨게이트, 출차 톨게이트 값만 넣고 바로 요금이 나오게 만들 것입니다.

출차 톨게이트를 지날때마다 알고리즘으로 계산하는게 아닙니다. 물론 중간에 요금이 바뀔 때마다 요금이 바뀐 수치를 넣고 다시 알고리즘을 돌려 데이터 베이스를 갱신합니다.

이전 소스에 NullException이 나온다고 많이 하셨는데.. 이는 아마 소스를 복사하면서 불필요한 값이 들어가서 그렇습니다. 실제 바이너리에서는 눈에 보이지 않는 문자도 있습니다. (\r, \n 코드입니다.)

그것까지 다시 커버가 가능하게 수정을 했습니다.

먼저 패턴식으로 바꾸었는데, 각 데이터를 담당하는 Model 클래스와 계산을 담당하는 Controller 클래스로 나누었습니다.

Model 클래스는 Station(역 클래스)와 Subway(지하철 노선 클래스)를 만들었습니다.

package Model;
import java.util.ArrayList;

public class Station {
  //전역(복수가 될수 있다.환승역 예:동대문운동장)
  private final ArrayList<Station> prev;
  //다음역(복수가 될수 있다.환승역 예:동대문운동장)
  private final ArrayList<Station> next;
  //역코드(임의)
  private String code = null;
  //역이름
  private String name = null;

  //생성자
  public Station() {
    prev = new ArrayList<Station>();
    next = new ArrayList<Station>();
  }

  //이하 프로퍼티
  public void setCode(String code) {
    this.code = code;
  }

  public String getCode() {
    return this.code;
  }

  public void setName(String name) {
    this.name = name;
  }

  public String getName() {
    return this.name;
  }

  public Station getPrev(int index) {
    return this.prev.get(index);
  }

  public void addPrev(Station value) {
    if (!this.prev.contains(value)) {
      this.prev.add(value);
    }
  }

  public Station getNext(int index) {
    return this.next.get(index);
  }

  public void addNext(Station value) {
    if (!this.next.contains(value)) {
      this.next.add(value);
    }
  }

  public String toString() {
    return "[CODE]" + code + "[NAME]" + name;
  }

  public int getPrevCount() {
    return this.prev.size();
  }

  public int getNextCount() {
    return this.next.size();
  }
}

package Model;

import java.util.ArrayList;
import Common.SubwayException;

/**
 * 지하철 노선 탐색 알고리즘
 */
//역정보 리스트
public class Subway extends ArrayList<Station> implements Cloneable {

  private static final long serialVersionUID = 1L;

  /**
   * 생성자 리스트
   */
  public Subway() {

  }

  /**
   * 역추가(다형성)
   * 
   * @param code 역 코드
   * @param name 역 이름
   */
  public void addStation(String code, String name) throws SubwayException {
    Station s = new Station();
    s.setCode(code);
    s.setName(name);
    addStation(s);
  }

  @Override
  public final boolean add(Station station) {
    throw new RuntimeException("More not supported");
  }

  /**
   * 역추가(다형성)
   * 
   * @param station 역 클래스
   */
  public void addStation(Station station) throws SubwayException {
    // 역코드가 중복일시 에러를 내보낸다
    if (getStation(station.getCode()) != null) {
      throw new SubwayException("same code");
    }
    super.add(station);
  }

  /**
   * 코드로 역을 찾는다
   * 
   * @param code
   */
  public Station getStation(String code) {
    for (Station s : this) {
      if (s.getCode().equals(code)) {
        return s;
      }
    }
    return null;
  }

  public String toString() {
    String ret = "";
    for (Station s : this) {
      ret += s.toString() + "\r\n";
    }
    return ret;
  }

  // clone을 재정의한다.
  @Override
  public Subway clone() {
    try {
      return (Subway) super.clone();
    } catch (Throwable e) {
      return null;
    }
  }
}

그리고 Controller 클래스는 역과 지하철 노선을 생성하는 Builder와 계산을 하는 Controller로 만들었습니다.

package Controller;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;

import Common.SubwayException;
import Model.Station;
import Model.Subway;

public class SubwayBuilder {

  /**
   * singleton 패턴으로 데이터 무결성을 만든다.
   */
  private static SubwayBuilder singleton = null;

  public static SubwayBuilder getInstance() {
    if (SubwayBuilder.singleton == null) {
      SubwayBuilder.singleton = new SubwayBuilder();
    }
    return SubwayBuilder.singleton;
  }

  /**
   * builder안에 있는 subway클래스
   */
  private Subway subway;

  private SubwayBuilder() {
    this.subway = new Subway();
  }

  /**
   * build하면 클래스를 복제한다.
   */
  public Subway build() {
    return this.subway.clone();
  }

  /**
   * 역 링크정보 읽기
   */
  public SubwayBuilder readFile(File subwayFile, File linkFile) throws SubwayException, IOException {
    // 프로퍼티 역정보(역정보)취득
    readSubway(subwayFile);
    // 프로퍼티 링크정보(지하철 노선)취득
    readLink(linkFile);
    return this;
  }

  /**
   * 파일로 부터 역정보를 읽어드린다.
   */
  private void readSubway(File file) throws SubwayException, IOException {
    // 파일을 전부 읽어드린다.
    byte[] buffer = new byte[(int) file.length()];
    try (FileInputStream in = new FileInputStream(file)) {
      in.read(buffer, 0, buffer.length);
    }
    String data = new String(buffer);
    // 구분자 \n로 역정보를 전부 읽어드린다.(라인 하나에 역하나)
    String[] lineBuffer = data.split("\n");
    // 데이터가 하나도 없으면 에러
    if (lineBuffer.length <= 0) {
      new IOException("document style wrong");
    }
    // 역을 클래스화
    for (String line : lineBuffer) {
      // 구분자는 콤마[,]
      String[] buf = line.replace("\r", "").split(",");
      // 데이터 이상은 통과
      if (buf.length != 2) {
        continue;
      }
      // 파일 형식은 코드,역이름
      this.subway.addStation(buf[0], buf[1]);
    }
  }

  /**
   * 파일로 부터 역 링크를 읽어드린다.
   */
  private void readLink(File file) throws IOException {
    // 파일을 전부 읽어드린다.
    byte[] buffer = new byte[(int) file.length()];
    try (FileInputStream in = new FileInputStream(file)) {
      in.read(buffer, 0, buffer.length);
    }
    String data = new String(buffer);
    // 구분자 \n로 링크정보를 전부 읽어드린다.(라인 하나에 링크하나)
    String[] lineBuffer = data.split("\n");
    if (lineBuffer.length <= 0) {
      throw new IOException("document style wrong");
    }
    // 링크 만들기
    for (String line : lineBuffer) {
      // 구분자는 콤마[,]
      String[] buf = line.replace("\r", "").split(",");
      // 데이터 이상은 통과
      if (buf.length != 3) {
        continue;
      }
      // buf[1]의 다음역은 buf[2]
      if ("n".equals(buf[0])) {
        setNextStation(buf[1], buf[2]);
      }
      // buf[1]의 전역은 buf[2]
      else if ("p".equals(buf[0])) {
        setPrevStation(buf[1], buf[2]);
      }
    }
  }

  /**
   * 다음역 세팅
   * 
   * @param point 기준 역 정보
   * @param next  다음 역 정보
   */
  public SubwayBuilder setNextStation(Station point, Station next) {
    point.addNext(next);
    next.addPrev(point);
    return this;
  }

  /**
   * 다음역 세팅(다형성)
   * 
   * @param pointCode 역 코드
   * @param nextCode  역 코드
   */
  public SubwayBuilder setNextStation(String pointCode, String nextCode) {
    Station point = this.subway.getStation(pointCode);
    Station next = this.subway.getStation(nextCode);
    setNextStation(point, next);
    return this;
  }

  /**
   * 전역 세팅
   * 
   * @param point 기준 역 정보
   * @param prev  전역정보
   */
  public SubwayBuilder setPrevStation(Station point, Station prev) {
    point.addPrev(prev);
    prev.addNext(point);
    return this;
  }

  /**
   * 전역 세팅(다형성)
   * 
   * @param pointCode 전역 코드
   * @param prevCode  전역 코드
   */
  public SubwayBuilder setPrevStation(String pointCode, String prevCode) {
    Station point = this.subway.getStation(pointCode);
    Station prev = this.subway.getStation(prevCode);
    setPrevStation(point, prev);
    return this;
  }
}

package Controller;
import java.util.ArrayList;
import java.util.Stack;

import Common.SubwayException;
import Model.Station;
import Model.Subway;

public class SubwayController {
  
  private Subway subway;
  
  public SubwayController(Subway subway) {
    this.subway = subway;
  }
  /**
   * 역 탐색
   * 
   * @param start 출발 역코드
   * @param end   도착 역코드
   * @return 노선 출력
   */
  public String search(String start, String end) throws SubwayException {
    Station startStation = this.subway.getStation(start);
    Station endStation = this.subway.getStation(end);
    return search(startStation, endStation);
  }

  /**
   * 역 탐색 (다형성)
   * 
   * @param start 출발 역정보
   * @param end   도착 역정보
   * @return 노선 출력
   */
  public String search(Station start, Station end) throws SubwayException {
    //모든 탐색 정보
    ArrayList<ArrayList<Station>> list = new ArrayList<ArrayList<Station>>();
    //탐색용 버퍼
    Stack<Station> buffer = new Stack<Station>();
    //역코드로 역을 탐색할때 없으면 에러처리
    if (this.subway.getStation(start.getCode()) == null) {
      throw new SubwayException("Not Station");
    }
    //역코드로 역을 탐색할때 없으면 에러처리
    if (this.subway.getStation(end.getCode()) == null) {
      throw new SubwayException("Not Station");
    }
    //경로 탐색
    nodeExplorer(start, end, buffer, list);
    //출역
    String ret = "";
    int index = 0;
    int size = 999999;
    //노드가 가장 적은 역이 어떤건지 찾음(최단 탐색)
    for (int i = 0; i < list.size(); i++) {
      if (list.get(i).size() < size) {
        size = list.get(i).size();
        index = i;
      }
    }
    //모든 경로를 출력한다.
    for (ArrayList<Station> item : list) {
      ret += print(item);
    }
    ret += "\r\n\r\n";
    //최단 경로를 출력한다.
    ret += "Best root\r\n";
    ret += print(list.get(index));
    return ret;
  }

  private String print(ArrayList<Station> item) {
    StringBuffer sb = new StringBuffer();
    sb.append("Size : " + item.size() + "**");
    for (Station s : item) {
      if (sb.length() > 0) {
        sb.append("->");
      }
      sb.append(s.toString());
    }
    sb.append("\r\n");
    return sb.toString();
  }

  /**
   * 노드 탐색(재귀적으로 탐색한다.)
   * 
   * @param point  현재 탐색 역
   * @param end    종착역
   * @param buffer 버퍼
   * @param list   노드리스트
   *
   *               재귀의 구조 도봉에서 석계를 간다고 가정할 때 처음 도봉의 전역, 다음역으로 재귀를 호출 전역은 망월사 -> 회룡
   *               -> 의정부 북부까지 갔는데 해당 역이 종착역을 만나지 못하면 pop으로 다시 도봉까지 돌아옴 도봉역에서 방학->
   *               창동-> 노원 -> 상계 -> 당고개를 가지만 또 해당역이 종착을 못 만나고 pop으로 돌아옴.그러나 중간에
   *               노원에서 분기되었기 때문에 노원에서 재탐색을 실시. 쌍문-> 수유 쪽의 경로를 탐색하게 됨 그런 식으로 석계역을
   *               만날 때까지 모든 경로를 탐색함.
   */
  private boolean nodeExplorer(Station point, Station end, Stack<Station> buffer,
      ArrayList<ArrayList<Station>> list) {
    //탐색역과 종착역이 같으면 도착함
    if (point == end) {
      //탐색 노드 선언
      ArrayList<Station> root = new ArrayList<Station>();
      //노드 담기
      for (Station s : buffer) {
        root.add(s);
      }
      //마지막역 담기
      root.add(point);
      //리스트에 추가
      list.add(root);
      //종료
      return true;
    }
    //현재역이 없으면 재 탐색
    if (point == null) {
      return false;
    }
    //버퍼에 현재 역 담기
    buffer.push(point);
    //현재 역의 전역 개수만큼
    for (int i = 0; i < point.getPrevCount(); i++) {
      // 버퍼에 현재역이 있으면 돌아가기(지나간 역을 다시 지나가면 의미 없음)
      // 예)종각에서 시청을 갔는데 시청에서 다시 종각으로 돌아가면 의미 없음
      if (buffer.contains(point.getPrev(i))) {
        continue;
      }
      //없으면 전역으로 이동
      if (!nodeExplorer(point.getPrev(i), end, buffer, list)) {
        //재탐색이 되면 현재역은 경로가 아님
        if (buffer.size() > 0) {
          buffer.pop();
        }
      }
    }
    //현재 역의 다음역 개수만큼
    for (int i = 0; i < point.getNextCount(); i++) {
      // 버퍼에 현재역이 있으면 돌아가기(지나간 역을 다시 지나가면 의미없음)
      // 예)종각에서 시청을 갔는데 시청에서 다시 종각으로 돌아가면 의미 없음
      if (buffer.contains(point.getNext(i))) {
        continue;
      }
      if (!nodeExplorer(point.getNext(i), end, buffer, list)) {
        //재탐색이 되면 현재 역은 경로가 아님
        if (buffer.size() > 0) {
          buffer.pop();
        }
      }
    }
    //재탐색
    return false;
  }
}

그리고 공통 패키지에는 예외 처리 클래스와 실행 클래스를 만들었습니다.

package Common;

public class SubwayException extends Exception {
  private static final long serialVersionUID = 1L;
  /**
   * 예외처리
   * @param message
   */
  public SubwayException(String message){
    super(message);
  }
}

package Common;

import java.io.File;

import Controller.SubwayBuilder;
import Controller.SubwayController;
import Model.Subway;

public class Main {
  public static void main(String[] args) {
    try {
      String path = System.getProperty("user.dir");
      // 빌더를 생성한다.
      SubwayBuilder builder = SubwayBuilder.getInstance().readFile(new File(path + "/station.txt"), new File(path + "/link.txt"));
      // 지하철 클래스를 만든다.
      Subway subway = builder.build();
      
      // 검색을 위한 컨트롤러를 만든든다.
      SubwayController controller = new SubwayController(subway);
      // 의정부 북부에서 교대의 최단 노선을 구하여라
      String ret = controller.search("1", "91");
      // 결과출력
      System.out.println(ret);
    } catch (Throwable e) {
      e.printStackTrace();
    }
  }
}

그리고 초기 마스터 데이터를 위한 바이너리를 두개 추가합니다.

첨부 - link.txt

첨부 - station.txt

이제 준비가 되었으면 실행을 합니다 저는 의정부 북부에서 교대의 최단 노선을 계산했습니다.(참고로 옛날 노선도 입니다.)

이건 그냥 알고리즘만 사용하는 것이기에 정말 지하철 탐색 프로그램이라고 하면 디비부터 화면까지 깔끔하게 설계를 하고 하면 멋진 프로그램이 되겠네요.. 사용하시게 되면 출처만 남겨주세요.

첨부파일 - ExplorerSubway.zip

여기까지 Java에서 지하철 노드 탐색 (연결리스트, 트리 탐색 응용) 알고리즘에 대한 설명이었습니다.

궁금한 점이나 잘못된 점이 있으면 댓글 부탁드립니다.