1. 알고리즘 개요
(우선법과 좌선법은 방향만 다르고 같은원리의 알고리즘이다) 미로찾기 알고리즘 중 하나인 우선법(좌선법)은 어떤 미로를 빠져나갈 때 오른쪽 벽을 따라 계속 가다보면 언젠가는 출구에 도착한다는 원리이다. 이 때 오른쪽(왼쪽)은 탐색자의 기준으로 한다. 쉽게 말해서 우선법은 미로에서 갈림길을 만났을 때 우선적으로 오른쪽(왼쪽)으로 가는 방법인데, 오른손을 벽에 대고 계속 가다보면 언젠간 미로를 빠져나갈 수 있다.
Right Hand on Wall (우선법)
(1) 몸을 오른쪽으로 돌린다
(2) 만약 앞에 벽이 있다면, 벽이 없을 때 까지 몸을 왼쪽으로 돌린다.
(3) 앞으로 1칸 가고 아직 미로 안에 있다면 (1)으로 돌아간다.
2. Micro Mouse
Micro Mouse는 유명한 미로찾기 태스크 중 하나이다. 미로에 생쥐로봇을 놓고 1번째 시도에서는 길을 익히게 한 뒤, 두번 째 시도부터는 기억한 길에 대한 정보를 기반으로 최단경로를 탐색하여 가장 빨리 목적지까지 도달한다. 아래의 영상을 보면 Micro Mouse에 대해서 알 수 있을 것이다.
3. 유사 코드와 시뮬레이션
1) 유사코드 : 유사코드는 아래와 같다. 위에서 말한대로 아직 미로 안에 있다면 오른쪽으로 몸을 돌리고, 만약 앞에 벽이 있다면 벽이 없을 때 까지 왼쪽으로 몸을 돌린다. 벽이 없을 때 까지 몸을 돌렸기 때문에 앞에는 벽이 없고, 앞으로 움직이고 한번의 스텝을 끝낸다.
while(still_in_maze){
turn_right();
while(wall_ahead){
turn_left();
}
go_ahead();
}
2) 시뮬레이션 : 위 알고리즘을 이용하여 빨간색 로봇이 아래 미로를 빠져나간다고 가정한다. 미로 맵은 이재규님의 알고리즘 강의 우선법 편에서 참고했다. 빨간색 로봇이 가장 왼쪽 위의 1번 이미지에서 시작하여 위 알고리즘대로 움직이며 12번까지 움직인다. 이 알고리즘이 동작하는 이유는 벽을 만났을 때 회전하면서 자연스레 U턴을 돌게되고, 그러면 몸의 방향이 반대로 변하고 반대편 벽을 짚게 되기 때문이다.
3. 소스코드
Java와 우선법으로 구현한 Micro Mouse 애플리케이션이다. 자바 Swing을 이용하여 뷰를 작성하였고, 미로는 위의 이미지와 동일한 미로를 사용하였다. 코드에 대한 자세한 설명은 아래에 첨부되어있고, 도큐먼테이션도 함수 단위로 작성하였으니 확인할 수 있다.
1) Main : 실행을 위한 메인 클래스이다. 맵을 입력받아 뷰를 생성하고 미로 탐색을 시작한다.
import mazeApp.view.View;
/**
* @author : Hyunwoong
* @when : 2020-01-21 오전 3:58
* @homepage : https://github.com/gusdnd852
*/
public class Main {
private static final int[][] map = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
/**
* 메인함수 : 미로 탐색을 시작합니다.
* */
public static void main(String[] args) {
new View(map, 17, 17, 180);
}
}
2) View : 미로와 마이크로 마우스를 뷰에 그리고, 우선법 객체를 생성하여 우선법으로 미로 경로를 탑색한다.
package mazeApp.view;
import mazeApp.model.Maze;
import mazeApp.model.Mouse;
import mazeApp.control.RightHand;
import javax.swing.*;
import java.awt.*;
/**
* @author : Hyunwoong
* @when : 2020-01-21 오전 3:58
* @homepage : https://github.com/gusdnd852
*/
public class View extends JFrame {
private JPanel[][] panels;
private Maze maze;
private Mouse mouse;
/**
* 뷰의 생성자
*
* @param map 2차원 맵
* @param row 마이크로 마우스의 초기 행 위치
* @param col 마이크로 마우스의 초기 열 위치
* @param speed 이동 스피드
* */
public View(int[][] map, int row, int col, int speed) {
maze = new Maze(map);
mouse = new Mouse(row, col);
panels = new JPanel[maze.getRow()][maze.getCol()];
this.drawView();
RightHand rightHand = new RightHand(panels, mouse, row, col);
rightHand.start(speed);
}
/**
* 뷰를 그립니다.
* */
private void drawView() {
this.getContentPane().setBackground(Color.DARK_GRAY);
this.setSize(640, 640);
this.setLayout(new FlowLayout());
this.drawMaze(maze.getRow(), maze.getCol());
this.drawMouse(mouse);
this.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
this.setVisible(true);
}
/**
* 미로를 그립니다.
*
* @param row 미로의 총 행 개수
* @param col 미로의 총 열 개수
* */
private void drawMaze(int row, int col) {
this.setBackground(Color.DARK_GRAY);
this.setLayout(new GridLayout(maze.getRow(), maze.getCol()));
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
Color color = maze.getMap()[i][j] == 1 ?
Color.DARK_GRAY : Color.WHITE;
JPanel block = new JPanel();
block.setBackground(color);
panels[i][j] = block;
this.add(panels[i][j]);
}
}
}
/**
* 마이크로 마우스를 초기위치에 그립니다.
*
* @param mouse 마이크로 마우스
* */
private void drawMouse(Mouse mouse) {
panels[mouse.getRow()][mouse.getCol()]
.add(mouse.getMouse());
}
}
3) Maze : 미로객체이다. 2차원 배열로 이루어진 맵과 행의 수, 열의 수를 포함하고 있다.
package mazeApp.model;
/**
* @author : Hyunwoong
* @when : 2020-01-21 오전 3:58
* @homepage : https://github.com/gusdnd852
*/
public class Maze {
private int[][] map;
private int col, row;
/**
* 미로 객체 생성자
*
* @param map 2차원 맵
*/
public Maze(int[][] map) {
this.map = map;
this.col = map.length;
this.row = map.length;
}
/**
* @return 2차원 맵 반환
*/
public int[][] getMap() {
return map;
}
/**
* @return 미로의 열 개수 반환
*/
public int getCol() {
return col;
}
/**
* @return 미로의 행 개수 반환
*/
public int getRow() {
return row;
}
}
4) Mouse : 마이크로 마우스 객체이다. 회전할 수 있고, 자신의 위치(행, 열)을 포함하고 있다.
package mazeApp.model;
import javax.swing.*;
import java.awt.*;
import java.util.Arrays;
import java.util.List;
/**
* @author : Hyunwoong
* @when : 2020-01-21 오전 3:58
* @homepage : https://github.com/gusdnd852
*/
public class Mouse {
private int row, col;
private String state = "▲";
private JLabel label = new JLabel(state);
/**
* 마이크로 마우스 생성자
*
* @param row 초기 행 위치
* @param col 초기 열 위치
* */
public Mouse(int row, int col) {
this.row = row;
this.col = col;
this.label.setOpaque(true);
this.label.setFont(new Font("Default", Font.PLAIN, 16));
this.label.setBackground(Color.RED);
this.label.setForeground(Color.WHITE);
}
/**
* @return 현재 마이크로마우스의 행 위치
* */
public int getRow() {
return row;
}
/**
* @return 현재 마이크로마우스 열 위치
* */
public int getCol() {
return col;
}
/**
* @return 마우스의 방향을 그리는 JLabel을 반환합니다.
* */
public JLabel getMouse() {
return label;
}
/**
* 마이크로 마우스를 해당 위치에 세팅합니다.
*
* @param row 세팅할 행 위치
* @param col 세팅할 열 위치
* */
public void setCoordinate(int row, int col){
this.row = row;
this.col = col;
}
/**
* 왼쪽으로 몸을 회전합니다.
* */
public void turnLeft() {
if (state.equals("▲")) state = "◀";
else if (state.equals("▼")) state = "▶";
else if (state.equals("◀")) state = "▼";
else if (state.equals("▶")) state = "▲";
this.updateState();
}
/**
* 오른쪽으로 몸을 회전합니다.
* */
public void turnRight() {
if (state.equals("▲")) state = "▶";
else if (state.equals("▼")) state = "◀";
else if (state.equals("◀")) state = "▲";
else if (state.equals("▶")) state = "▼";
this.updateState();
}
/**
* 위치를 한칸 앞으로 옮깁니다.
* 현재 마이크로 마우스의 위치에 따라 조정합니다.
* */
public void modifyPositionForGoAhead() {
if (state.equals("▲")) row -= 1;
else if (state.equals("▼")) row += 1;
else if (state.equals("◀")) col -= 1;
else if (state.equals("▶")) col += 1;
}
/**
* 마이크로 마우스보다 한 칸 앞 좌표를 반환합니다
* 현재 마이크로 마우스의 위치에 따라 방향이 설정됩니다.
* */
public List<Integer> seeAhead() {
if (state.equals("▲")) return Arrays.asList(row - 1, col);
else if (state.equals("▼")) return Arrays.asList(row + 1, col);
else if (state.equals("◀")) return Arrays.asList(row, col - 1);
else if (state.equals("▶")) return Arrays.asList(row, col + 1);
else throw new IllegalStateException("illegal state");
}
/**
* 상태를 업테이트 합니다.
* */
private void updateState() {
label.setText(this.state);
}
}
5) RightHand : 우선법 알고리즘의 구현체이다. 최단경로 탐색을 위해 모든 이동경로를 history에 저장한다.
package mazeApp.control;
import mazeApp.model.Mouse;
import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author : Hyunwoong
* @when : 2020-01-21 오전 3:58
* @homepage : https://github.com/gusdnd852
*/
public class RightHand {
private List<List<Integer>> history = new ArrayList<>();
private JPanel[][] panels;
private Mouse mouse;
private int initRow, initCol;
/**
* 우선법 알고리즘 생성자
* @param panels JPanel을 담고 있는 홀더
* @param mouse 마우스 객체
* @param row 시작 행 위치
* @param col 시작 열 위치
* */
public RightHand(JPanel[][] panels, Mouse mouse, int row, int col) {
this.panels = panels;
this.mouse = mouse;
this.initRow = row;
this.initCol = col;
}
/**
* 마우스가 아직 미로를 해결하지 못했는지 여부를 반환합니다.
*
* @return 미로에 아직 남아있는지 여부
* */
private boolean stillInMaze() {
return !(mouse.getRow() == 1 && mouse.getCol() == 0);
}
/**
* 마우스 앞에 벽이 있는지 여부를 반환합니다.
*
* @return 앞에 벽이 있는지 여부
* */
private boolean wallAhead() {
List<Integer> ahead = mouse.seeAhead();
int aheadRow = ahead.get(0);
int aheadCol = ahead.get(1);
return panels[aheadRow][aheadCol]
.getBackground()
.equals(Color.DARK_GRAY);
}
/**
* 마우스를 왼쪽으로 회전시킵니다.
* */
private void turnLeft() {
mouse.turnLeft();
}
/**
* 마우스를 오른쪽으로 회전시킵니다.
* */
private void turnRight() {
mouse.turnRight();
}
/**
* 마우스의 관접에서 앞으로 한칸 움직입니다.
* */
private void goAhead() {
history.add(Arrays.asList(mouse.getRow(), mouse.getCol()));
panels[mouse.getRow()][mouse.getCol()].remove(0);
panels[mouse.getRow()][mouse.getCol()].updateUI();
mouse.modifyPositionForGoAhead();
panels[mouse.getRow()][mouse.getCol()].add(mouse.getMouse());
panels[mouse.getRow()][mouse.getCol()].updateUI();
}
/**
* 눈으로 확인하기 위해 일정시간 딜레이를 주면서 움직입니다.
*
* @param action 수행할 액션
* @param speed 딜레이 시간
* */
private void act(Runnable action, int speed) {
try {
Thread.sleep(speed);
action.run();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
/**
* 우선법 알고리즘
*
* @param speed 딜레이 시간
* */
private void rightHandSearch(int speed) {
while (stillInMaze()) {
act(this::turnRight, speed);
while (wallAhead()) {
act(this::turnLeft, speed);
}
act(this::goAhead, speed);
}
mouse.getMouse().setText("FIN");
}
/**
* 우선법으로 경로를 먼저 탐색하고
* 이후에 중복경로를 제거하여 최단경로로 움직입니다.
*
* @param speed 딜레이 시간
* */
public void start(int speed) {
this.rightHandSearch(speed);
Shortest shortest = new Shortest(panels, mouse, initRow, initCol, history);
shortest.shortestSearch(speed);
}
}
6) Shortest : 최단경로 탐색 알고리즘이다. 중복된 경로를 찾아내어 제거하여 최단경로를 만들어내고, 그 경로를 따라 미로를 탈출한다.
package mazeApp.control;
import mazeApp.model.Mouse;
import javax.swing.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
/**
* @author : Hyunwoong
* @when : 2020-01-21 오전 3:58
* @homepage : https://github.com/gusdnd852
*/
public class Shortest {
private List<List<Integer>> history;
private int initRow, initCol;
private JPanel[][] panels;
private Mouse mouse;
/**
* 최소경로 알고리즘의 생성자
*
* @param panels JPanel을 담고 있는 홀더
* @param mouse 마우스 객체
* @param row 시작 행 위치 (리셋)
* @param col 시작 열 위치 (리셋)
* @param history 현재까지 이동한 경로
*/
public Shortest(JPanel[][] panels, Mouse mouse, int row, int col, List<List<Integer>> history) {
this.panels = panels;
this.initRow = row;
this.initCol = col;
this.mouse = mouse;
this.history = history;
}
/**
* 마이크로 마우스의 위치를 초기화합니다.
*/
private void mouseReset() {
panels[mouse.getRow()][mouse.getCol()].remove(0);
panels[mouse.getRow()][mouse.getCol()].updateUI();
mouse = new Mouse(initRow, initCol);
panels[initRow][initCol].add(mouse.getMouse());
}
/**
* @param row 움직일 위치의 행
* @param col 움직일 위치의 열
*/
private void moveMouse(int row, int col) {
mouse.getMouse().setText(" S ");
panels[mouse.getRow()][mouse.getCol()].remove(0);
panels[mouse.getRow()][mouse.getCol()].updateUI();
mouse.setCoordinate(row, col);
panels[mouse.getRow()][mouse.getCol()].add(mouse.getMouse());
panels[mouse.getRow()][mouse.getCol()].updateUI();
}
/**
* 중복 경로를 찾아서 반환하는 메소드
*
* @return 중복경로가 저장된 리스트
*/
private List<Integer> findDuplicatePath() {
int sizeOfHistory = history.size();
List<Integer> listForRemove = new ArrayList<>();
for (int i = 0; i < sizeOfHistory; i++) {
for (int j = i + 1; j < sizeOfHistory; j++) {
if (history.get(i).equals(history.get(j))) {
for (int k = i; k < j; k++) {
listForRemove.add(k);
}
}
}
}
listForRemove = new ArrayList<>(new HashSet<>(listForRemove));
return listForRemove;
}
/**
* 기존 경로에서 중복경로를 제거하여 최단경로를 만듭니다.
*
* @param duplicatedPath 중복 경로 리스트
* @return 최단경로가 저장된 리스트
*/
private List<List<Integer>> makeShortestPath(List<Integer> duplicatedPath) {
List<List<Integer>> shortestPath = new ArrayList<>();
for (int i = 0; i < history.size(); i++) {
if (!duplicatedPath.contains(i)) {
shortestPath.add(history.get(i));
}
}
return shortestPath;
}
/**
* 중복경로를 찾고, 최단경로를 만들어서 최단경로로 미로를 빠져나갑니다.
*
* @param speed 딜레이 시간
*/
public void shortestSearch(int speed) {
this.mouseReset();
List<Integer> duplicatedPath = findDuplicatePath();
List<List<Integer>> shortestPath = makeShortestPath(duplicatedPath);
for (List<Integer> coordinate : shortestPath) {
int row = coordinate.get(0);
int col = coordinate.get(1);
try {
Thread.sleep(speed);
moveMouse(row, col);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
mouse.getMouse().setText("FIN");
}
}
모든 소스코드는 여기에서 확인할 수 있습니다.
gusdnd852/MicroMouse
Maze Search Application implemented with Java Swing - gusdnd852/MicroMouse
github.com
4. Demo
알고리즘이 잘 작동하는 것을 확인할 수 있다.
5. 우선법의 문제점
이렇게 확실하게 경로를 찾아주는 듯한 우선법에도 단점이 있다. 만일 아래의 그림처럼 순환하는 경로 (뱅뱅 도는 경로)를 발견하게 된다면 미로에서 탈출하지 못하게 된다. 때문에 이런 문제를 해결하려면 BFS, DFS, Dijikstra, A* 등의 더욱 고차원적인 경로 탐색 알고리즘을 사용해야만 한다.
6. Reference
'알고리즘' 카테고리의 다른 글
| 재귀 (3) - 하노이 탑 (Tower of Hanoi) (0) | 2020.02.04 |
|---|---|
| 재귀 (2) - 피보나치 수열 (Fibonacci Series) (0) | 2020.02.04 |
| 재귀 (1) - 개요 (0) | 2020.02.04 |
| 소수 (2) - 에라토스테네스의 체 (Sieve of Eratosthenes) (0) | 2020.01.10 |
| 소수 (1) - 소수 판별하기 (0) | 2020.01.08 |
| 유클리드 호제법 (Euclidean Algorithm) (0) | 2020.01.07 |
| 어 라 루스 (A La Russe) (0) | 2020.01.03 |