최단 경로 탐색 – A* 알고리즘

최단 경로 탐색 알고리즘 중 A*(A Star, 에이 스타) 알고리즘에 대해 실제 예시를 통해 풀어가면서 설명하겠습니다. A* 알고리즘은 시작 노드만을 지정해 다른 모든 노드에 대한 최단 경로를 파악하는 다익스트라 알고리즘과 다르게 시작 노드와 목적지 노드를 분명하게 지정해 이 두 노드 간의 최단 경로를 파악할 수 있습니다.

A* 알고리즘은 휴리스틱 추정값을 통해 알고리즘을 개선할 수 있는데요. 이러한 휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 얼마나 빨리 최단 경로를 파악할 수 있느냐가 결정됩니다.

A*에 대한 서론은 최대한 배제하고 하나의 명확한 예를 통해 풀어나가며 설명하도록 하겠습니다. 다음과 같은 예를 통해 먼저 살펴보겠습니다.

위의 예는 시작점인 0번 노드에서 목적지인 6번 노드로 가는 최단 경로를 A* 알고리즘으로 분석하고자 하는 것인데요. 각 노드 사이에 연결된 링크에 붙은 숫자는 노드 사이를 이동하는데 소요되는 비용(경비, Cost)입니다. 위의 경우 거리값입니다. 즉, 노드 사이의 거리가 길수록 비용이 늘어나므로 비용값으로써 합리적입니다.

A* 알고리즘을 통한 위의 문제 해결을 위해 가장 먼저 수행하는 첫 과정은 다음과 같습니다.

위의 그림에서 보면 저장소로 O와 C가 있는데요. O는 열린 목록(Open List), C는 닫힌 목록(Close List)인데요. 열린 목록인 O 저장소에는 최단 경로를 분석하기 위한 상태값들이 계속 갱신되며, C 저장소는 처리가 완료된 노드를 담아 두기 위한 목적으로 사용됩니다.  이러한 O와 C의 저장소를 기반으로 0번 노드에서 6번 노드까지의 최단 경로를 산출해 보도록 하겠습니다.

먼저 출발 노드인 0을 닫힌 목록인 C 목록에 집어 넣습니다. 그리고 이 0번 노드와 연결된 노드는 1번과 3번 노드를 열린 목록인 O 저장소에 추가합니다. 추가할 때 F, G, H, Parent Node값도 함게 추가해야 하는데요. 먼저 F = G + H입니다. G는 시작 노드에서 해당 노드까지의 실제 소요 경비값이고, H는 휴리스틱 추정값으로 해당 노드에서 최종 목적지까지 도달하는데 소요될 것이라고 추정되는 값입니다. Parent Node는 해당 노드에 도달하기 직전에 거치는 노드 번호입니다. 먼저 1번 노드에 대한 F, G, H, Parent Node를 살펴 보겠습니다. 출발점인 0번 노드로부터 시작했으므로,  1번 노드의 Parent Node는 0번 노드입니다. 그리고 G 값은 0번 노드에서 1번 노드까지의 거리 비용값인 5.6입니다. H 값을 추정하기 위한 기준이 필요한데요. 이 추정값에 대한 기준을  1번 노드에서 목적지인 6번 노드까지의 직선 거리로 하기로 정하고 측정을 하니(줄자로 재든, 좌표가 있다면 피타고라스 정리를 통해 두 좌표 사이의 거리를 계산하든 하여 얻을 수 있음)  12로 산출되므로 H는 12가 됩니다. F = G + H이므로 5.6 + 12인 17.6이 됩니다. 3번에 대한 F, G, H, Parent Node 역시 이와 동일하게 결정할 수 있습니다. 여기서 다음 단계로 진행합니다.


O 리스트 중 F 값이 가장 작은 노드는 3번인데요. 이 노드 3번을 C 리스트에 추가하고 3번 노드와 연결된 0, 2, 5 중 닫힌 목록에 존재하지 않는 2, 5번 노드에 대해 열린 목록에 추가합니다. 2, 5에 대한 F, G, H, Parent Node를 계산해 기록합니다. 먼저 2번 노드에 대해 계산해 보면.. 2번 노드에 대한 G 값은 바로 직전 노드에 소요되는 비용(6.8)에 3번 노드에서 2번 노드까지 도달하기 위한 비용인 5.6을 합한 값인 12.4가 됩니다. 그리고 H 값은 2번 노드에서 목적지은 6번까지에 대한 거리값인 7이 됩니다. 5번 노드에 대한 것도 이와 동일하게 계산합니다. 다음으로 진행합니다.

열린 목록(O 저장소) 중 F 값이 가장 작은(최소인) 1번 노드를 닫힌 목록에 추가합니다. 그리고 이 1번 노드와 연결된 2, 4번 노드 중 닫힌 목록(C 저장소)에 존재하지 않는 것에 대해 다시 F, G, H, Parent Node를 계산합니다. 이 상태에서 4번 노드는 열린 목록에 없었던 것이기에 그냥 F, G, H, Parent Node를 이미 앞서 설명했던 방식으로 계산해 추가하면 그만이지만 2번 노드는 전 단계에서 이미 추가되어 있었는데요. 이렇게 전 단계에서 추가된 G 값이 새롭게 계산된 G 값보다 크다면 새롭게 계산된 F, G, H, Parent Node 값으로 변경해 줘야 하며 위의 그림이 이러한 변경을 나타내고 있습니다. 다음 단계로 진행합니다.

열린 목록 중 F가 최소인 노드는 2번 노드이고, 이 2번 노드를 닫힌 목록에 추가합니다. 그리고 2번 노드와 연결된 1, 3, 5, 6번 노드 중 닫힌 목록에 존재하지 않는 5, 6번 노드에 대한 F, G, H Parent Node 값을 계산합니다. 5번 노드의 경우 새로운 G 값이 기존 값보다 크므로 변경하지 않고 6번 노드에 대한 값들만을 계산해 추가합니다. 다음 단계로 진행합니다.

열린 목록 중 F가 최소인 노드는 6번 노드인데요. 이 6번 노드를 닫힌 목록에 추가합니다. 그런데 이 6번 노드는 최종 목적지 노드이므로 A* 알고리즘은 종료됩니다.

여기까지 만들어진 닫힌 목록(C 저장소)를 토대로 0번 노드에서 6번 노드까지의 최단 경로를 파악할 수 있습니다. 6번 노드의 Parent Node는 2번 이고, 2번 노드의 Parent Node는 1번이며, 1번 노드의 Parent Node는 0번이므로 최단 경로는 6번 노드←2번 노드←1번 노드←0번 노드가 됩니다.

한번 적용된 CSS3 애니메이션(@keyframes)을 다시 적용하기

DOM 요소에 CSS3의 animation-name을 지정해 애니메이션을 지정해 플레이하고 난 뒤, 다시 이 DOM 요소에 animation-name을 지정하면 애니메이션이 플레이 되지 않는다. 이에 대한 CSS와 JS 코드는 다음과 같다. 먼저 CSS 입니다.


다음은 js입니다.


id가 dom_id인 DOM 객체에 blank 클래스를 처음 지정할때는 애니메이션이 발생하지만, 두번째부터는 애니메이션이 발생하지 않는다. 이럴 때는 23번과 24번 코드 사이에 아래의 코드를 추가한다.

domCounting.offsetWidth;

이건 Bug일까.. 아니면 의도된 것일까..

div 안의 img에 Inner Shadow 적용하기

아래와 같은 DOM 계층이 있다고 하자.

위의 div에 아래와 같은 스타일을 적용해 안쪽 그림자(Inner Shadow) 효과를 넣고자 한다면..

div {
    box-shadow: rgba(0, 0, 0, 0.5) 3px 3px 10px inset;
}

div 요소의 자식인 img에 부모인 그림자 효과가 표시되어야 할 것이라고 기대했지만, 부모인 div의 그림자가 자식인 img에 가려져 아래와 같은 결과만을 볼 수 있다.

그렇다면 자식인 img에 의해 가려진 부모의 그림자를 들어내기 위해서 어떻게 해야할까? 부모의 그림자 역시 DOM 계층적으로 보면 또 하나의 공개되지 않은 DOM 요소이다. 이 그림자 DOM 요소가 img에 가려지므로 이 img의 z-index의 값과 z-index 속성값이 영향을 받도록 하기 위해 position 속성을 relative나 absolute로 지정하면 되는데, 아래와 같다.

img {
    position: relative;
    z-index: -1;
}

이제 그 결과를 보면, div 요소에 안쪽 그림자 효과가 반영되어, 좀더 입체적으로 이미지가 표현되는 것을 확인할 수 있다.

JavaScript의 Class 정의 정리

모던한(?).. 즉 현대적인 Javascript에서는 클래스를 정의하기 위한 class 키워드를 제공하기는 하지만, 현재의 IE에서 아직도 지원하지 않아 나름대로의 class 정의 방식을 사용하고 있습니다. 웹 기반의 GIS 엔진인 FingerEyes-Xr도 이러한 class 정의 방식으로 개발 되었습니다. 수백여개의 클래스를 이 방식으로 정의해 왔음에도 새로운 클래스를 정의할라치면 기존에 만들어진 소스를 Copy 해서 Paste 해 고치는 것이 세련미 떨어져.. 직접 키보드로 한땀 한땀 입력하고자 정리해 봅니다.

먼저 클래스 정의하는 최소한의 구문입니다.

MyClass = Xr.Class({
    /* name: "MyClass", */ // optional

    construct: function () { /* 생성자 */ }
});

private 변수를 추가하는 구문입니다. 반드시 생성자 안에서 밑줄(_)로 시작해서 정의합니다.

MyClass = Xr.Class({
    construct: function () {
        this._privateVariable = 0;
    }
});

맴버 함수를 추가하는 구문입니다. private는 밑줄로 시작하고, public은 밑줄이 아닌 영문 소문자로 시작합니다.

MyClass = Xr.Class({
    construct: function () {},

    methods: {
        _privateFunction: function() { },
        publicFunction: function() { },
    }
});

클래스 차원에서 접근할 수 있는 static 변수 정의입니다. 아래와 같다면, MyClass.STATIC_VARIABLE의 값은 0이 됩니다.

MyClass = Xr.Class({
    statics: {
        STATIC_VARIABLE: 0
    },

    construct: function () {}
});

[ToDo] 상속, 인터페이스에 대한 내용은 추후 필요하면 그때 정리할 것

Java의 기본 log 기능 정리

log4j 등과 같은 로그를 위한 좋은 라이브러리가 있으나 Java에서 제공하는 기본 Log 기능에 대해 정리합니다. 먼저 가장 간단한 예는 아래와 같습니다. log에 대한 수준(Level)을 지정해 메세지를 콘솔에 표시하는 경우입니다.

package tst_Log_console;

import java.util.logging.Level;
import java.util.logging.Logger;

public class MainEntry {
    private final static Logger LOG = Logger.getGlobal();
	
    public static void main(String[] args) {
        LOG.setLevel(Level.INFO);
		
        LOG.severe("severe Log");
        LOG.warning("warning Log");
        LOG.info("info Log");
    }
}

Log의 수준은 높은 순서로 SEVERE, WARNING, INFO입니다. 각각이 의미하는 바는 심각함, 경고, 정보입니다. setLevel 함수를 통해 표시할 레벨의 수준을 조정할 수 있습니다. 위 코드에 대한 실행 결과는 다음과 같습니다.

4월 09, 2018 5:58:41 오후 tst_Log_console.MainEntry main
심각: severe Log
4월 09, 2018 5:58:41 오후 tst_Log_console.MainEntry main
경고: warning Log
4월 09, 2018 5:58:41 오후 tst_Log_console.MainEntry main
정보: info Log

위처럼 로그의 내용은 이미 정해져 있는데요. 만약 자신만의 로그 형식을 원한다면 먼저 Formatter 클래스를 상속받아 다음과 같은 클래스를 정의해야 합니다.

package tst_Log_console;

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.logging.Formatter;
import java.util.logging.Handler;
import java.util.logging.LogRecord;

public class CustomLogFormatter extends Formatter {
    public String getHead(Handler h) {
        return "START LOG\n";
    }
	
    public String format(LogRecord rec) {
        StringBuffer buf = new StringBuffer(1000);

        buf.append(calcDate(rec.getMillis()));
        
        buf.append(" [");
        buf.append(rec.getLevel());
        buf.append("] ");
        
        buf.append("[");
        buf.append(rec.getSourceMethodName());
        buf.append("] ");
        
        buf.append(rec.getMessage());
        buf.append("\n");
        
        return buf.toString();
    }

    public String getTail(Handler h) {
    	return "END LOG\n";
    }
    
    private String calcDate(long millisecs) {
        SimpleDateFormat date_format = new SimpleDateFormat("yyyy-MM-dd HH:mm");
        Date resultdate = new Date(millisecs);
        return date_format.format(resultdate);
    }
}

그리고 이 클래스를 다음의 예처럼 활용할 수 있습니다.

package tst_Log_console;

import java.util.logging.ConsoleHandler;
import java.util.logging.Handler;
import java.util.logging.Level;
import java.util.logging.Logger;

public class MainEntry2 {
    private final static Logger LOG = Logger.getGlobal();
	
    public static void main(String[] args) {
        //=============================================
        // 기본 로그 제거
        //------------
        Logger rootLogger = Logger.getLogger("");
        Handler[] handlers = rootLogger.getHandlers();
        if (handlers[0] instanceof ConsoleHandler) {
            rootLogger.removeHandler(handlers[0]);
        }
        //=============================================
		
        LOG.setLevel(Level.INFO);
		
        Handler handler = new ConsoleHandler();
        CustomLogFormatter formatter = new CustomLogFormatter();
        handler.setFormatter(formatter);
        LOG.addHandler(handler);
		
        LOG.severe("severe Log");
        LOG.warning("warning Log");
        LOG.info("info Log");
    }
}

위의 클래스에서 getHead 함수는 로그 기록을 시작할때 한번만 호출되어 로그로써 표시되는 문자열을 반환합니다. 그리고 format은 개발자가 로그를 표시하기 원할때마다 메세지의 형식을 정의하기 위해 호출되는 함수입니다. 그리고 getTail은 프로그램이 종료될때 호출되는 로그 메세지로 표시할 문자열을 반환합니다. (그러나 현재 시점에서 이 getTail은 로그를 콘솔로 표시할 때 호출되지 않는 문제가 있음) 코드를 좀더 살펴보면, 12-20번 코드는 기본적으로 지정된 로그(콘솔창에 이미 정의된 형식으로 내요을 출력함)를 제거합니다. 그리고 24-27번 코드처럼 앞서 정의한 Formatter에 대한 상속 클래스를 생성해 지정합니다. 실행해 보면 다음과 같습니다.

START LOG
2018-04-09 18:06 [SEVERE] [main] severe Log
2018-04-09 18:06 [WARNING] [main] warning Log
2018-04-09 18:06 [INFO] [main] info Log

위의 경우처럼 로그를 화면이 아닌 파일로 저장하고 싶을 때가 있습니다. 이 경우 아래의 코드와 같이 하면 됩니다.

package tst_Log_console;

import java.io.IOException;
import java.util.logging.ConsoleHandler;
import java.util.logging.FileHandler;
import java.util.logging.Handler;
import java.util.logging.Level;
import java.util.logging.Logger;

public class MainEntry3 {
    private final static Logger LOG = Logger.getGlobal();
	
    public static void main(String[] args) throws SecurityException, IOException {
        //=============================================
        // 기본 로그 제거
        //------------
        Logger rootLogger = Logger.getLogger("");
        Handler[] handlers = rootLogger.getHandlers();
        if (handlers[0] instanceof ConsoleHandler) {
            rootLogger.removeHandler(handlers[0]);
        }
        //=============================================
		
        LOG.setLevel(Level.INFO);
		
        Handler handler = new FileHandler("message.log", true);
        
        CustomLogFormatter formatter = new CustomLogFormatter();
        handler.setFormatter(formatter);
        LOG.addHandler(handler);
		
        LOG.severe("severe Log");
        LOG.warning("warning Log");
        LOG.info("info Log");
    }
}

달라지는 내용은 26번 코드에서 ConsoleHandler 대신 FileHandler로 변경되었다는 것입니다. 이 FileHandler 생성자는 첫번째 인자에 사용할 파일명을, 그리고 두번째 인자에 파일 기록시 APPEND 모드인지의 여부를 지정합니다.