DFS로 미로 탈출하기

최단거리 알고리즘을 공부하면서 예전해 만들었었던 미로 찾기를 다시한번 해봤다.

초년생때 이런문제가 어려웠는데 다시해보니 크게 어렵지는 않은것 같다.

DTO

---

package dto;

/**
 * Maze 블록의 정보를 보관하는 DTO
 * 
 * @author rokki
 *
 */
public class MazeBlock {
	private int x; // x 좌표
	private int y; // y 좌표
	private int count; // 카운트
	
	public MazeBlock(int x, int y, int count) {
		this.x = x;
		this.y = y;
		this.count = count;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

	public int getCount() {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}
}

package dto;

/**
 * 거리와 맵을 저장하고 있는 클래스
 * 
 * @author rokki
 *
 */
public class ResultDto {
	private int resultCount;		// 경로 카운트
	private char[][] result;		// 최단 거리 맵
	
	public ResultDto(int resultCount, char[][] result) {
		this.resultCount = resultCount;
		this.result = result;
	}

	public int getResultCount() {
		return resultCount;
	}

	public void setResultCount(int resultCount) {
		this.resultCount = resultCount;
	}

	public char[][] getResult() {
		return result;
	}

	public void setResult(char[][] result) {
		this.result = result;
	}

}

 

Service

---

package service;

import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.charset.Charset;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;

import dto.MazeBlock;
import dto.ResultDto;
import serviceI.MazeService;

/**
 * 맵 경로를 찾는 서비스
 *
 * @author wedul
 *
 */
public class MazeServiceImpl implements MazeService {
	
	private char map[][];
	private boolean visited[][];
	private int maxX;
	private int maxY;
	private int currCount;
	private List<ResultDto> result = new ArrayList<>();

	@Override
	public void setMap(String path) throws IOException {
		List<String> mapList = readFile(path);
		this.maxY = mapList.size();
		this.maxX = mapList.get(0).length();
		this.map = new char[maxX][maxY];
		this.visited = new boolean[maxX][maxY];
		
		readFile(path).forEach((data) -> {
			for (int i = 0; i < data.length(); i++) {
				map[i][currCount] = data.charAt(i);
				visited[i][currCount] = false;
			}
			currCount++;
		});
	}

	@Override
	public void printMap() {
		for (int i = 0; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				System.out.print(map[j][i]);
			}
		}
	}
	
	public void printMap(char[][] paramMap) {
		for (int i = 0; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				System.out.print(paramMap[j][i]);
			}
		}
	}

	@Override
	public void findRoute() {
		// dfs 진행 (재귀)
		move(new MazeBlock(0, 1, 0));
	}
	
	/**
	 * map 나가기
	 * 
	 * @param dto
	 */
	private void move(MazeBlock dto) {
		int x = dto.getX();
		int y = dto.getY();
		visited[x][y] = true;
		int count = dto.getCount() + 1;
		
		// 위로 이동
		if (enableGo(new MazeBlock(x , y - 1, count))) {
			move(new MazeBlock(x, y - 1, count));
		}
		
		// 오른쪽으로 이동
		if (enableGo(new MazeBlock(x + 1, y, count))) {
			move(new MazeBlock(x + 1, y, count));
		}
		
		// 아래로 이동
		if (enableGo(new MazeBlock(x, y + 1, count))) {
			move(new MazeBlock(x, y + 1, count));
		}
		
		// 왼쪽으로 이동
		if (enableGo(new MazeBlock(x - 1, y, count))) {
			move(new MazeBlock(x - 1, y, count));
		}
		
		visited[x][y] = false;
	}
	
	/**
	 * 더 나아갈 수 있는지 확인
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	private boolean enableGo(MazeBlock dto) {
		int x = dto.getX();
		int y = dto.getY();
		
		// 경로 이탈 확인
		if (x < 0 || y < 0 || x > maxX || y > maxY) {
			return false;
		} 
		
		// 종점에 도착할 시 출려
		if (map[x][y] == 'G') {
			setResult(dto.getCount());
		}
		
		return map[x][y] == ' ' && !visited[x][y];
	}
	
	/**
	 * 경로들을 저장
	 * 
	 * @param count
	 */
	private void setResult(int count) {
		// map 복제
		char[][] cloneMap = new char[maxX][maxY];
		
		for (int i = 0 ; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				cloneMap[j][i] = map[j][i];
			}
		}
		
		for (int i = 0 ; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				if (visited[j][i]) {
					cloneMap[j][i] = '*';
				}
			}
		}
		
		result.add(new ResultDto(count, cloneMap));
	}
	
	@Override
	public void printResult() {
		ResultDto shortResult = result.get(0); // 최단경로 객체
		
		for (ResultDto dto : result) {
			System.out.println("GOAL===================" + dto.getResultCount());
			if (shortResult.getResultCount() > dto.getResultCount()) {
				shortResult = dto;
			}
		}
		
		System.out.println();
		System.out.println("short length : " + shortResult.getResultCount());
		printMap(shortResult.getResult());
	}
	
	/**
	 * nio를 사용하여 파일 읽기
	 * 
	 * @throws IOException 
	 */
	private List<String> readFile(String path) throws IOException {
		List<String> datas = new ArrayList<>();
		FileChannel fileChannel = FileChannel.open(Paths.get(path), StandardOpenOption.READ);
		 
        ByteBuffer buffer = ByteBuffer.allocate(1024);

        Charset charset = Charset.defaultCharset();
        String data = "";
 
        int byteCount;
 
        while (true) {
            byteCount = fileChannel.read(buffer);
 
            if (byteCount == -1)
                break;
 
            buffer.flip();
            data += charset.decode(buffer).toString();
            buffer.clear();
        }
 
        fileChannel.close();
        
        Stream<String> stream = Arrays.stream(data.split("\\n"));
        stream.forEach((eachData) -> {
        	datas.add(eachData);
        });
        
        return datas;
	}

}


package serviceI;

import java.io.IOException;

public interface MazeService {
	
	/**
	 * 파일에서 Map을 읽어 출력
	 * 
	 * @param path
	 * @throws IOException
	 */
	void setMap(String path) throws IOException;
	
	/**
	 * 맵 출력
	 */
	void printMap();
	
	/**
	 * 최단거리 찾기
	 */
	void findRoute();
	
	/**
	 * 최단거리 결과 출력
	 */
	void printResult();

}

package main;

public class Main {
	public static void main(String[] args) {
		MazeService service = new MazeServiceImpl();
		try {
			service.setMap("Map/maze.txt");
			service.findRoute();
			service.printResult();
		} catch (Exception e) {
			System.out.println("Fail Find Map");
		}
	}
}

 

결과

---

GOAL===================33 
GOAL===================31 
GOAL===================41 
GOAL===================39 
GOAL===================27 
GOAL===================25 
GOAL===================35 
GOAL===================33 
GOAL===================25 
GOAL===================23 
GOAL===================25 
GOAL===================23 

short length : 23 
################### 
********                     # 
#######*##### ## ## 
#      ******                 # 
## ##### ###*###### 
 # #  ## # #*# #  # 
   #                ******G 
###################