1. Move
* 현재 위치가 유효한지 체크
> 유효하지 않다면, 이전 위치로 돌아간다
* 현재 위치가 도착점인지 체크
> 도착점이라면, 현재까지의 경로가 미로찾기의 해
* 현재 위치를 경로로 표시함
* 동서남북으로 이동해 봄(순서는 관계없음 - 다만 맵에 따라 순서가 해 찾는 속도에 영향을 끼칠 수 있음)
* 동쪽으로 가 봄(Move 재귀)
* 동쪽으로 가는 데 실패했다면, 서쪽으로 가 봄(Move 재귀)
* 서쪽으로 가는 것도 실패했다면, 남쪽으로 가 봄(Move 재귀)
* 남쪽으로 가는 것도 실패했다면, 북쪽으로 가 봄(Move 재귀)
* 네 방향 모두 실패했다면, 현재 위치를 경로에서 제거하고(길로 변경하고) 이전 위치로 돌아간다
2. 현재 위치 유효성 체크
* 현재 위치가 미로 내인지, 벽이 아닌지, 갔던 길이 아닌지 체크
> Yes 라면 유효함 / No 라면 유효하지 않음
미로의 시작점 부터 Move 를 시작하면, 미로찾기의 해를 얻을 수 있다.
시작점에서 출발 후 시작점으로 다시 돌아왔고 네 방향 모두 가는 것이 실패했다면 미로찾기의 해가 없는 것이다.
갈 수 있는 길이 있으면 무작정 계속 이동해보기 때문에 그래프의 깊이 탐색과 유사한 부분이 있다.
소스는 아래와 같다. 길기 때문에 접어 두었으며, 링크를 통해 코드 하이라이트된 소스를 참고할 수 있다.
소스 보기
=begin
Backtracking 을 이용하여 미로 탈출
현실감은 고려하지 않았음
(현실이라면 현재 위치가 아니라 진행 전에 진행 위치에 대해 갈 수 있는지 체크해야 함)
=end
class Location
attr_accessor :row, :col
end
class Maze
attr_accessor :map_matrix, :height, :width
File.open(file_path, "r") do |file|
while line = file.gets
line.chomp!
line_len = line.length
if -1 == maze_width
maze_width = line_len
else
if line_len != maze_width
puts "Maze data is not square!!!"
return nil
end
end
maze_height += 1
end
file.rewind
maze.init_map(maze_height, maze_width)
(0...maze_height).each do |i|
line = file.gets
line.chomp!
line_arr = line.split(//)
(0...maze_width).each do |j|
maze.map_matrix[i][j] = line_arr[j]
start_loc.row, start_loc.col = i, j if Maze::START == maze.map_matrix[i][j]
end
end
end
maze.start = start_loc
maze
end
end
class MazeExplorer
def initialize(maze)
@maze = maze
end
def solve_maze
if move(@maze.start)
@maze.map_matrix[@maze.start.row][@maze.start.col] = Maze::START
@maze.print_maze
else
puts("No Way to Exit!!")
end
end
def move(curr)
return nil if !check_valid(curr)
return true if Maze::GOAL == @maze.map_matrix[curr.row][curr.col]
@maze.map_matrix[curr.row][curr.col] = Maze::WALK
Maze::DIRECTION.each do |dir|
new_loc = Location.new
new_loc.row, new_loc.col = curr.row, curr.col
case dir
when :NORTH
new_loc.row = curr.row - 1
when :WEST
new_loc.col = curr.col - 1
when :EAST
new_loc.col = curr.col + 1
when :SOUTH
new_loc.row = curr.row + 1
end
return true if move(new_loc)
end
# move to new Direction : ALL nil // do backtracking
@maze.map_matrix[curr.row][curr.col] = Maze::ROAD
