Ruby 서로소 집합으로 구현

class DisjointSet
    def initialize
        @parent = Hash.new { |hash, key| hash[key] = key }
    end

    def root_of(node)
        node_list = []
        while @parent[node] != node
            node_list << node
            node = @parent[node] 
        end

        #path compression       
        node_list.each {|e|
            @parent[e] = node;
        }
        node
    end

    def connect(node1, node2)
        @parent[root_of(node1)] = root_of(node2)
    end

    def connected?(node1, node2)
        root_of(node1) == root_of(node2)
    end
end

class Map   
    def map_data
        @map_data
    end

    def map_data=(rhs)
        @map_data = 
            case rhs
            when String
                rhs.split("\n")
            when Array
                rhs
            end         
    end

    def get_adjacents(y, x)
        [[y+1, x], [y-1, x], [y, x-1], [y, x+1]].find_all { |y,x| 
            y >= 0 && y < @y_size && x >= 0 && x < @x_size
        }
    end

    def passable?
        @y_size = @map_data.size
        @x_size = @map_data.first.length

        ds = DisjointSet.new
        st = []
        ed = []

        #[[0,0], [0, 1], ... , [0, @x_size-1], [1, 0] , ... , [@y_size-1, @x_size-1]
        coords = [*0...@y_size].product [*0...@x_size]  
        coords.each{|y, x| 
            case @map_data[y][x]
            when '<'     #start point 
                st = [y, x]
            when '>' #end point
                ed = [y, x]
            when '#' #wall - do nothing
                nil
            else
                get_adjacents(y, x).find_all{|y, x| @map_data[y][x] != '#' }.each { |ny, nx| 
                    ds.connect([y, x], [ny, nx] ) 
                }
            end
        }
        ds.connected?(st, ed)       
    end
end


m = Map.new
m.map_data="<     >"
puts m.passable?

m.map_data="########\n#<     #\n#  ##  #\n#  ##  #\n#     >#\n########"
puts m.passable?

m.map_data="#######\n#<    #\n##### #\n#     #\n# #####\n# #   #\n# # # #\n#   #>#\n#######"
puts m.passable?

m.map_data="<   #   >"
puts m.passable?

m.map_data="########\n#<     #\n#     ##\n#    #>#\n########"
puts m.passable?

m.map_data="#< #  #\n#  #  #\n#  # >#"
puts m.passable?

Python3입니다. 간단한 Recursion을 이용했습니다. 미로가 커지면 스택이 감당이 안될것 같긴 하네요 ㅜㅠ

def inspectMaze(mz, i, j):
    if ((i < 0) or (j < 0) or (i == len(mz)) or (j == len(mz[0])) or (mz[i][j] == '#') or (mz[i][j] == '<')): return False
    if mz[i][j] == '>': return True
    mz[i][j] = '<'
    return (inspectMaze(mz, i, j - 1) or inspectMaze(mz, i - 1, j) or inspectMaze(mz, i, j + 1) or inspectMaze(mz, i + 1, j)) 

def checkMaze(maze):
    mz = [list(x) for x in list(maze.split("\n"))]

    #find "<"
    i, j = 0, 0
    for mzl in mz:
        if "<" in mzl: 
            j = mzl.index("<")
            break
        i = i + 1

    return (inspectMaze(mz, i, j - 1) or inspectMaze(mz, i - 1, j) or inspectMaze(mz, i, j + 1) or inspectMaze(mz, i + 1, j)) 

for maze in ["<     >", 
"""########
#<     #
#  ##  #
#  ##  #
#     >#
########""", 
"""#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######""",
"<   #   >", 
"""########
#<     #
#     ##
#    #>#
########""", 
"""#< #  #
#  #  #
#  # >#"""]:
    print(checkMaze(maze))

간단한 BFS입니다.

from functools import reduce

data1 = "########\n#<     #\n#  ##  #\n#  ##  #\n#     >#\n########\n"
data2 = "########\n#<     #\n#     ##\n#    #>#\n########\n"

def build(sdata):
    tiles = dict(zip(' <#>', range(10)))
    mdata = [x for x in sdata.split('\n') if x]
    def convert(line):
        return [tiles[c] for c in line if c in tiles]
    return reduce(lambda x, y: x+y,
                  [convert(x) for x in mdata], []), len(mdata[0]), len(mdata)

def neighbors(i, w, h):
    offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    return [i + x + y * w for x, y in offsets\
              if 0 <= (i // w + y) < h and 0 <= (i % w + x) < w]

def do(data):
    smap, w, h = build(data)
    i = smap.index(1)
    queue = [i]
    while queue:
        i = queue.pop(0)
        if smap[i] == 3:
            return True
        smap[i] = 1
        queue += [x for x in neighbors(i, w, h) if smap[x] not in (1, 2)]
    return False

print(do(data1))
print(do(data2))

JAVA 좀 무식한 방법으로 짰습니다

package maze;
import java.util.Scanner;
public class Maze {

    public static void main(String[] args) {
        int L=100; //L : Limit of input lines

        Maze m=new Maze();
        Scanner in=new Scanner(System.in);
        String[] inputS=new String[L];
        int i,j,N,M=L; boolean d1,d2;
        for(i=0;i<L;i++){ // Inputting
            inputS[i]=in.nextLine();
            if(inputS[i].equals("")){ M=i; break;}
        }
        N=inputS[0].length();
        int[][] maze=new int[M][N];
        int[] goal=new int[2]; //goal: ending point
        int[] count=new int[1];

        m.input_to_maze(inputS, maze, goal);

        do{ // Process
            /*Print*/ // for(i=0;i<M;i++) for(j=0;j<N;j++) System.out.print(maze[i][j]+((j==N-1)?"\n":"")); System.out.println();
            count[0]=0;
            for(i=0;i<M;i++){
                for(j=0;j<N;j++) m.pass(maze, i, j, count); for(j=N-1;j>=0;j--) m.pass(maze, i, j, count);}
            for(i=M-1;i>=0;i--){
                for(j=0;j<N;j++) m.pass(maze, i, j, count); for(j=N-1;j>=0;j--) m.pass(maze, i, j, count);}
        }while(count[0]>0);

        System.out.println(((maze[goal[0]][goal[1]]==1)?"true":"false")); //Result
    }

    void input_to_maze(String[] inputS, int[][] maze, int[] goal){
        int i,j, M=maze.length, N=maze[0].length;
        for(i=0;i<M;i++)
            for(j=0;j<N;j++){
                switch(inputS[i].charAt(j)){
                case '#': maze[i][j]=2; break;
                case '<': maze[i][j]=1; break;
                case '>': goal[0]=i; goal[1]=j;
                default : maze[i][j]=0; break;
                }
            }
    }

    void pass(int[][] maze, int x, int y, int[] count){
        int M=maze.length, N=maze[0].length;
        if(maze[x][y]==0){
            if( (x>0&&maze[x-1][y]==1) || (x<M-1&&maze[x+1][y]==1) || (y>0&&maze[x][y-1]==1) || (y<N-1&&maze[x][y+1]==1) ){
                maze[x][y]=1; count[0]++;}
        }
    }

}

좀 무식한 방법으로 짰습니다;;

통과 가능한 미로의 예 3)에서,
(/*print*/부분 슬러쉬 두 개 풀었을 때의 출력)

#:2, 공백:0, 시작지점(<):1으로 둔 Int 배열을 만든 후,
오른쪽방향에서 왼쪽방향, 아랫방향에서 윗방향으로 한칸한칸씩
0이 있는 칸(공백)일 경우 상하좌우에 1이 있을 경우 1을 집어넣습니다
더 이상 1로 바꿀 수 있는 0칸이 없을 때까지 이를 반복합니다
도착지점(>)칸의 값이 1일 경우 true를, 0일 경우 false를 출력합니다

2222222
2100002
2222202
2000002
2022222
2020002
2020202
2000202
2222222

2222222
2111112
2222212
2111112
2122222
2121112
2121202
2111202
2222222

2222222
2111112
2222212
2111112
2122222
2121112
2121212
2111212
2222222

true

python 2.7

import unittest

class V:
    def __init__(self, row, y, x, value):
        self.row = row
        self.visit = False
        self.y = y
        self.x = x
        self.value = value

    def up(self):
        if self.y-1 < 0: return None
        return self.row[self.y-1][self.x]

    def down(self):
        if self.y+1 >= len(self.row): return None
        return self.row[self.y+1][self.x]

    def left(self):
        if self.x-1 < 0: return None
        return self.row[self.y][self.x-1]

    def right(self):
        if self.x+1 >= len(self.row[0]): return None
        return self.row[self.y][self.x+1]

    def __str__(self):
        return "(%s, %s):[%s]" % (self.y, self.x, self.value)


class Map:
    def __init__(self, data):
        self.row = []
        y = 0
        for line in data.split("\n"):
            line = line.strip()
            if not line: continue
            col = []
            for x, c in enumerate(line):
                v = V(self.row, y, x, c)
                col.append(v)
                if c == '<':
                    self.start = v
                elif c == '>':
                    self.end = v
            self.row.append(col)
            y += 1


class Search:
    def __init__(self, data):
        self.map = Map(data)
        self.found = False
        self.go(self.map.start)

    def go(self, v):
        if v == self.map.end:
            self.found = True
            return

        v.visit = True

        canGo = lambda v: v and v.value != "#" and not v.visit
        if canGo(v.up()):self.go(v.up())
        if canGo(v.right()):self.go(v.right())
        if canGo(v.left()):self.go(v.left())
        if canGo(v.down()):self.go(v.down())



class SearchTest(unittest.TestCase):
    def test1(self):
        self.assertTrue(Search("""
            <     >
        """).found)

        self.assertTrue(Search("""
            ########
            #<     #
            #  ##  #
            #  ##  #
            #     >#
            ########
        """).found)

        self.assertTrue(Search("""
            #######
            #<    #
            ##### #
            #     #
            # #####
            # #   #
            # # # #
            #   #>#
            #######
        """).found)

        self.assertFalse(Search("""
            <   #   >
        """).found)

        self.assertFalse(Search("""
            ########
            #<     #
            #     ##
            #    #>#
            ########
        """).found)

        self.assertFalse(Search("""
            #< #  #
            #  #  #
            #  # >#
        """).found)



if __name__ == "__main__":
    unittest.main()

    Sub Main()
        Dim n As Integer = Val(Console.ReadLine)
        Dim map(n - 1)() As String
        Dim stPoint As Point

        For i As Integer = 1 To n
            Dim line As String = Console.ReadLine, idx As Integer = i - 1

            map(idx) = Array.ConvertAll(line.ToArray,
                                          Function(c As Char)
                                              If c.ToString = "<" Then
                                                  stPoint = New Point(line.IndexOf("<"), idx)
                                              End If
                                              Return c.ToString
                                          End Function)
        Next

        Dim find As Boolean = False

        Dim q As New Queue
        q.Enqueue(stPoint)

        While q.Count > 0
            Dim pt As Point = q.Dequeue

            '// 출구
            If map(pt.X)(pt.Y) = ">" Then
                find = True
                Exit While
            End If

            If map(pt.X)(pt.Y) <> "#" Then
                map(pt.X)(pt.Y) = "#"

                If pt.X < map.Length - 1 Then q.Enqueue(New Point(pt.X + 1, pt.Y))
                If pt.X > 0 Then q.Enqueue(New Point(pt.X - 1, pt.Y))
                If pt.Y < map(0).Length - 1 Then q.Enqueue(New Point(pt.X, pt.Y + 1))
                If pt.Y > 0 Then q.Enqueue(New Point(pt.X, pt.Y - 1))
            End If
        End While

        Console.WriteLine("Result: " & find.ToString)

        Console.ReadLine()
    End Sub

BFS 알고리즘을 이용하였습니다.

'''
시작점을 먼저 찾고
시작점 주위의 공백을 'c'로 색칠하고 그 주위의 공백을 또 색칠하는 것을 반복.
도착점을 찾으면 True를 리턴
재귀함수로 구현했음.
'''


maze=[]
while True:
    s = raw_input()
    if s =='': break
    maze.append(list(s))
for y in range(len(maze)): # 시작점을 찾아서 x, y에 저장
    if maze[y].count('<') > 0 :
        x = maze[y].index('<')
        break

def find(x,y): #재귀함수
    if x<0 or y<0 or x>len(maze[0]) or y>=len(maze) : return False
    m = maze[y][x]
    if m == '>' : return True
    if m == ' ' or m =='<':
        maze[y][x] = 'c' # 한번 탐색을 했던 곳은 체크해서 다시 탐색하지 않도록 함
        return find(x-1,y)|find(x+1,y)|find(x,y-1)|find(x,y+1)
    else :
        return False

print find(x,y)

sample = '''#< #  #
#  #  #
#  # >#'''
class cursor():
    def __init__(self, co, endpoint):
        self.y = co[0]; self.x = co[1]
        self.ey = endpoint[0]; self.ex = endpoint[1]
        self.dic = []; self.history = []
    def chain(self, brd, co):
        y = co[0]; x = co[1]
        if (y,x) not in self.history:self.history.append((y,x))
        else:return
        for a, b in [(1,0),(-1,0),(0,1),(0,-1)]:
            try:
                if brd[y+a][x+b] == 0:
                    self.dic.append((y+a, x+b))
                    self.chain(brd, (y+a, x+b))
            except:continue
    def posibility(self):return (self.ey,self.ex) in self.dic

if __name__ == '__main__':
    m = sample.split('\n')
    li = []; se = {};
    i = 0
    for a in m:
        li.append([]); j = 0
        for b in a:
            if b == '#':li[i].append(1)
            if b == ' ':li[i].append(0)
            if b == '<':li[i].append(0); se['start'] = (i,j)
            if b == '>':li[i].append(0); se['end'] = (i,j)
            j += 1
        i += 1
    cu = cursor(se['start'],se['end'])
    cu.chain(li,(cu.y,cu.x))
    print(cu.posibility())

재귀함수입니다. 파이썬 3.5.1

C#으로 작성했습니다. Depth First Search로 구현하려고 최대한 노력했습니다.

        public class Point
        {
            public int X { get; set; }
            public int Y { get; set; }
            public Point(int x, int y)
            {
                X = x; Y = y;
            }
        }

        public bool MazeThrough(string input)
        {
            var splits = input.Split("\n");
            var starting = FindingPoint(splits, "<");
            if (starting.X == -1 || starting.Y == -1) return false;
            return PointOpen(splits, starting.X, starting.Y);
        }

        public Point FindingPoint(string[] splits, string sign)
        {
            for (int i = 0; i < splits.Count(); i++)
                if (splits[i].Contains(sign)) return new Point(i, splits[i].IndexOf("<"));
            return new Point(-1, -1);
        }

        public bool PointOpen(string[] splits, int x, int y)
        {
            var line = splits[x];
            var output = string.Empty;
            if (line[y].ToString() == ">") return true;
            if (line[y].ToString() == "#") return false;
            if (line[y].ToString() == "X") return false;
            for (int i = 0; i < line.Length; i++) output += i == y ? "X" : line[i].ToString();
            splits[x] = output;
            var left = y - 1 >= 0 && PointOpen(splits, x, y - 1);
            var right = y + 1 < splits[0].Length && PointOpen(splits, x, y + 1);
            var up = x - 1 >= 0 && PointOpen(splits, x - 1, y);
            var down = x + 1 < splits.Count() && PointOpen(splits, x + 1, y);
            if (up || down || left || right) return true;
            return false;
        }

Ruby

BFS

require 'matrix'
check = ->maze=gets("\n\n") do
  m = Matrix[*maze.split("\n").map(&:chars)]
  q = [m.index("<")]
  nexts = ->x,y { m.send(:[]=, x, y, "#")
                 [[x+1,y], [x-1,y], [x,y-1], [x,y+1]].
                   select {|x,y| x>=0 && y>=0 && " >"[m[x,y] || 2]} }
  ((x,y=q.shift; m[x,y]==">" ? (break true) : q+=nexts[x,y]) until !q[0]) || false
end

Test

maze1 = "<     >\n"
maze2 = "########\n#<     #\n#  ##  #\n#  ##  #\n#     >#\n########\n"
maze3 = "#######\n#<    #\n##### #\n#     #\n# #####\n" +
        "# #   #\n# # # #\n#   #>#\n#######\n"
maze4 = "<   #   >\n\n"
maze5 = "########\n#<     #\n#     ##\n#    #>#\n########\n"
maze6 = "#< #  #\n#  #  #\n#  # >#\n"

expect( [maze1, maze2, maze3].all? &check ).to eq true
expect( [maze4, maze5, maze6].all? &check ).to eq false

Output

puts check.call
#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######

true

Delphi 2010 BFS

type
  TArrayInt2d = array of array of Integer;

function BFS(var Map: TArrayInt2d; pStart, pEnd: TPoint; sizeX, sizeY: Integer): string;
var
  i, pos, cnt, nSize, xPos, yPos: Integer; // 맵의 크기와 카운트 변수
  x, Y, L: array of Integer; // 좌표와 길이를 담을 배열
  s: string;
  // 큐에 좌표 정보와 길이를 삽입하는 함수
  procedure enqueue(_x, _y, _l: Integer);
  begin
    x[cnt] := _x;
    Y[cnt] := _y;
    L[cnt] := _l;
    Inc(cnt);
  end;

begin
  pos := 0;
  cnt := 0;
  nSize := sizeX * sizeY;
  SetLength(x, nSize);
  SetLength(Y, nSize);
  SetLength(L, nSize);

  // 시작점의 좌표 정보와 길이를 큐에 삽입한다
  enqueue(pStart.x, pStart.Y, 1);
  x[pos] := pStart.x;
  Y[pos] := pStart.Y;
  // 더 이상 방문할 지점이 없거나, 도착 지점에 도착하면 루프를 탈출한다
  result := 'Result : Fail'; // 결과값 저장
  while (pos < nSize) do
  begin
    xPos := x[pos];
    yPos := Y[pos];
    if (xPos = pEnd.x) and (yPos = pEnd.Y) then // 결과위치
    begin
      result := format('Result = %d', [L[pos]]);
      s := '';
      for i := 0 to pos do
        s := s + format('%3d,', [x[i]]);
      result := result + #13#10 + 'X Value: ' + s;
      s := '';
      for i := 0 to pos do
        s := s + format('%3d,', [Y[i]]);
      result := result + #13#10 + 'Y Value: ' + s;
      s := '';
      for i := 0 to pos do
        s := s + format('%3d,', [L[i]]);
      result := result + #13#10 + 'L Value: ' + s;
      break;
    end;

    if (xPos >= sizeX - 1) and (yPos >= sizeY - 1) then
      break;
    // 두 번 방문하게 하면 안되므로, 이미 지나갔다는 표시를 해둔다
    Map[yPos, xPos] := 0;
    // 위로 갈 수 있다면, 위 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (yPos > 0) and (Map[yPos - 1, xPos] = 1) then
      enqueue(xPos, yPos - 1, L[pos] + 1);
    // 아래로 갈 수 있다면, 아래 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (yPos < sizeY - 1) and (Map[yPos + 1, xPos] = 1) then
      enqueue(xPos, yPos + 1, L[pos] + 1);
    // 왼쪽으로 갈 수 있다면, 왼쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (xPos > 0) and (Map[yPos, xPos - 1] = 1) then
      enqueue(xPos - 1, yPos, L[pos] + 1);
    // 오른쪽로 갈 수 있다면, 오른쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (xPos < sizeX - 1) and (Map[yPos, xPos + 1] = 1) then
      enqueue(xPos + 1, yPos, L[pos] + 1);

    // 큐의 다음 순서의 지점을 방문한다
    Inc(pos);
  end;

end;

procedure TForm4.btnBFS미로찾기Click(Sender: TObject);
var
  sData: string;
  C: Char;
  i, j, nSizeX, nSizeY: Integer;
  Map: TArrayInt2d;
  pStart, pEnd: TPoint;
begin
    nSizeY := 9;
    nSizeX := 7;
    sData := //
    '#######' + //
    '#<    #' + //
    '##### #' + //
    '#     #' + //
    '# #####' + //
    '# #   #' + //
    '# # # #' + //
    '#   #>#' + //
    '#######';

  {nSizeY := 6;
  nSizeX := 6;
  sData := //
    '111111' + //
    '001001' + //
    '111011' + //
    '100010' + //
    '111010' + //
    '001111';
    }

  SetLength(Map, nSizeY, nSizeX);
  pStart := Point(0, 0);
  pEnd := Point(nSizeY-1, nSizeX-1);
  for i := 0 to nSizeY - 1 do
    for j := 0 to nSizeX - 1 do
    begin
      C := sData[nSizeX * i + j + 1];
      if (C = '#') or (C = '0') then
        Map[i, j] := 0
      else
      begin
        Map[i, j] := 1;
        if C = '<' then
        begin
          pStart.x := j;
          pStart.Y := i;
        end;
        if C = '>' then
        begin
          pEnd.x := j;
          pEnd.Y := i;
        end;
      end;
    end;

  Memo1.Lines.Text := BFS(Map, pStart, pEnd, nSizeX, nSizeY); // BFS 시작!
end;

Python3로 작성하였습니다. 출구를 찾아가는 과정을 눈으로 볼수 있도록 하였습니다.

원치 않으시면 DEBUG 변수를 False로 바꿔주시면 됩니다.

#-*-coding:utf-8-*-
DEBUG = True
checkPattern = [(0, -1), (-1, 0), (1, 0), (0, 1)]
checkedFlag = "o"

def checkNode(datas, x, y):
    datas[y][x] = checkedFlag
    for pattern in checkPattern:
        coord = (x + pattern[0], y + pattern[1])
        if (0 <= coord[1] < len(datas)) and (0 <= coord[0] < len(datas[coord[1]])):
            data = datas[coord[1]][coord[0]]
            #### DEBUG START
            if DEBUG:
                print("")
                datas[y][x] = "*"
                datas[coord[1]][coord[0]] = "?"
                for line in datas:
                    print("".join(line))
                datas[y][x] = checkedFlag
                datas[coord[1]][coord[0]] = checkedFlag
            #### END OF DEBUG
            if data != checkedFlag:                
                if data == ">": 
                    print("Found '>' at", coord)
                    return True
                elif data == " ":
                    # recursive search
                    if checkNode(datas, coord[0], coord[1]):
                        return True
    return False

def isPossible(data):
    # 문자열 형태인 data를 리스트로 변환
    datas = [list(line) for line in data.split("\n")]    
    # 시작지점 "<"의 위치를 찾는다.
    sX, sY = 0, 0
    for y in range(len(datas)):
        if "<" in datas[y]:
            sX, sY = datas[y].index("<"), y
    # 찾기시작          
    if not checkNode(datas, sX, sY):
        print("Not found.")

테스트

#-------------------#
# Test
#-------------------#
data1="""<     >"""

data2="""########
#<     #
#  ##  #
#  ##  #
#     >#
########"""

data3="""#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######"""

data4="""<   #   >"""

data5 = """########
#<     #
#     ##
#    #>#
########"""

data6 = """#< #  #
#  #  #
#  # >#"""

isPossible(data1)
isPossible(data2)
isPossible(data3)
isPossible(data4)
isPossible(data5)
isPossible(data6)

실행결과

Found '>' at (6, 0)
Found '>' at (6, 4)
Found '>' at (5, 7)
Not found.
Not found.
Not found.

#include<stdio.h>
#include<stdlib.h>
#define SIZE 20

char queue[20];
int top = 0;
int width = 7;
int height = 3;

void push(char value);
int ALLpop();
struct Coor {
    int x;
    int y;
}start, end;
void BFS(Coor c, char** arr, int val);
void findStartEnd (char** arr);
bool verdict(char** arr);
int** temp;
void main() 
{
    char** input = (char**) malloc (sizeof(char*)*height);
    for(int i = 0; i< height  ;i++)
        input[i] = (char*) malloc (sizeof(char)*width);
    temp = (int**) malloc (sizeof(int*)*height);
    for(int i = 0; i< height  ;i++)
        temp[i] = (int*) malloc (sizeof(int)*width);

    for(int i = 0; i< height  ;i++) 
        for(int j = 0; j<width  ;j++) 
            temp[i][j] = 0;

    printf("가로 사이즈 : ");
    scanf("%d", &width);
    printf("세로 사이즈 : ");
    scanf("%d", &height);

    for(int i = 0; i<height ;i++) {
        scanf("%s", input[i]);
    }

    findStartEnd (input);
    BFS(start, input, 0);
    printf("\n\n%d\n", verdict(input));

}
void findStartEnd (char** arr) {
    for(int i = 0; i< height  ;i++) {
        for(int j = 0; j<width  ;j++)  {
            if(arr[i][j] == '<'){
                start.x = j;
                start.y = i;
                temp[i][j] = -1;
            }
            else if(arr[i][j] == '>'){
                end.x = j;
                end.y = i;
            }
        }
    }
}
bool verdict(char** arr) {
    for(int i = 0; i< height  ;i++) {
        for(int j = 0; j<width  ;j++)  {
            if(arr[i][j] == '>'){
                if(temp[i][j]!=0)
                    return true;
            }

        }
    }
    return false;
}
void BFS(Coor c, char** arr, int val) {

    if(c.y+1 < height && arr[c.y+1][c.x] !='#' && temp[c.y+1][c.x] == 0) {
        Coor cur;
        cur.y = c.y+1;
        cur.x = c.x;
        temp[cur.y][cur.x] = val + 1;
        BFS(cur, arr, temp[cur.y][cur.x]);
    }
    if(c.y > 0 && arr[c.y-1][c.x] !='#' && temp[c.y-1][c.x] == 0) {
        Coor cur;
        cur.y = c.y-1;
        cur.x = c.x;
        temp[cur.y][cur.x] = val + 1;
        BFS(cur, arr, temp[cur.y][cur.x]);
    }
    if(c.x+1 < width && arr[c.y][c.x+1] !='#' && temp[c.y][c.x+1] == 0) {
        Coor cur;
        cur.y = c.y;
        cur.x = c.x+1;
        temp[cur.y][cur.x] = val + 1;
        BFS(cur, arr,temp[cur.y][cur.x]);
    }
    if(c.x > 0 && arr[c.y][c.x-1] !='#' && temp[c.y][c.x-1] == 0) {
        Coor cur;
        cur.y = c.y;
        cur.x = c.x-1;
        temp[cur.y][cur.x] = val + 1;
        BFS(cur, arr,temp[cur.y][cur.x]);
    }
}

Haskell로 작성 하였습니다.

import Data.List
import Control.Monad

data1 = "<     >"

data2 =
    "########\n\
    \#<     #\n\
    \#  ##  #\n\
    \#  ##  #\n\
    \#     >#\n\
    \########"

data3 =
    "#######\n\
    \#<    #\n\
    \##### #\n\
    \#     #\n\
    \# #####\n\
    \# #   #\n\
    \# # # #\n\
    \#   #>#\n\
    \#######"

data4 = "<   #   >"

data5 =
    "########\n\
    \#<     #\n\
    \#     ##\n\
    \#    #>#\n\
    \########"

data6 =
    "#< #  #\n\
    \#  #  #\n\
    \#  # >#"

checkPatterns = [(0, -1), (-1, 0), (1, 0), (0, 1)]

findStartPoint datas num
    | index /= Nothing = Just (n, num)
    | length datas <= num = Nothing
    | otherwise = findStartPoint datas (num + 1)
    where
        index = elemIndex '<' (datas !! num)
        Just n = index

mergeNode [] = Nothing
mergeNode (x:xs) 
    | x == Nothing = mergeNode xs
    | otherwise = x

findEndPoint datas (x,y) checkedList =
    mergeNode (
        fmap
            (\(pX, pY) -> 
                let
                    (nX, nY) = (x+pX, y+pY)
                    character = (datas !! nY) !! nX
                in
                    if nY >=0 && nY < length datas && nX >= 0 && nX < length (datas !! nY) && not (elem (nX, nY) checkedList)
                    then case character of
                        '>' -> Just (nX, nY)
                        ' ' -> findEndPoint datas (nX, nY) ((x,y):checkedList)
                        otherwise -> Nothing
                    else Nothing)
            checkPatterns
        )

checkTheMaze =
    fmap
        (\mazeData -> do
            let maze = lines mazeData
            startPoint <- findStartPoint maze 0
            findEndPoint maze startPoint [])
        [data1, data2, data3, data4, data5, data6]

실행결과

Prelude> checkTheMaze

[Just (6,0),Just (6,4),Just (5,7),Nothing,Nothing,Nothing]

const maze1 = `#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######`

const maze2 = `#< #  #
#  #  #
#  # >#`

function parseMaze(s) {
  return s.split("\n").map(line => line.split(""))
}

function dfs(start, end, neighbors, equal) {
  let visited = [];
  let stack = [start];

  while (stack.length) {
    let current = stack.pop();
    if (equal(current, end)) return true;
    visited.push(current);
    stack.push(...neighbors(current).filter(pos => !visited.find(v => equal(pos, v))))
  }
  return false;
}

function valid(m) {
  return dfs(find("<"), find(">"), neighbors, equal);

  function neighbors([i,j]) {
    return [[i-1, j],[i+1, j],[i, j-1],[i,j+1]]
      .filter(validIndex)
      .filter(([i,j]) => m[i][j] !== '#');
  }

  function validIndex([i,j]) {
    return i >= 0 && i < m.length && j >= 0 && j < m[i].length;
  }

  function equal(a, b) {
    return a[0] == b[0] && a[1] == b[1];
  }

  function find(s) {
    for (let i=0; i<m.length; i++) {
      let index = m[i].indexOf(s);
      if (index !== -1) return [i, index];
    }
    throw "no such element"
  }
}

console.log(valid(parseMaze(maze1)));
console.log(valid(parseMaze(maze2)));

test="""
#######
#<    #
##### #
#     #
# #####
# # # #
# # # #
#   #>#
#######"""
cnt=0
start=[]
finish=[]
point_x=[]
point_y=[]
def start_p(stt):
    start.append(stt)
def finish_p(stt):
    finish.append(stt)
#큐에 거리를 집어넣는다
def enqueue(x,y):
    global cnt
    point_x.append(x)
    point_y.append(y)
    cnt+=1

#2차원 배열로  맵을 변환
def map2arr(test):
    cnt_col=0
    k=0
    cnt_row=0
    txt=[]
    for i in range(len(test)):
        if test[i] != "\n":
            cnt_row +=1
            txt.append(test[i])
        else :
            cnt_col+=1
            cnt_row=0
    txt="".join(txt)
    print(txt)
    start_p(txt.find('<'))
    finish_p(txt.find('>'))
    list(txt)
    test_road=[[0 for i in range(cnt_row)] for j in range(cnt_col)]
    print("cnt_col : ",cnt_col,"cnt_row : ",cnt_row)
    for i in range(cnt_col):
        for j in range(cnt_row):
            test_road[i][j]=txt[k]
            k+=1
    #2차원 배열로 맵의 정보를 옮김==> test_road    
    return test_road
def find_road(mapping):
    pos=0
    col=len(mapping)
    row=len(mapping[0])
    print("col : ",col,"row : ",row)
    #시작지점 저장
    sx=(start[0]%row)
    sy=int(start[0]/row)
    print("start : ",sx,sy)
    enqueue(sx,sy)
    #end point
    fx=(finish[0]%row)
    fy=int(finish[0]/row)
    print("finish :",fx,fy)

    while pos<cnt and point_x[pos] != row-1 and point_y[pos] != col-1:
        mapping[point_y[pos]][point_x[pos]]=0
        #올라가는방
        if mapping[point_y[pos]-1][point_x[pos]]==" " or mapping[point_y[pos]-1][point_x[pos]]==">":
            enqueue(point_x[pos], point_y[pos] - 1)

        #down
        if mapping[point_y[pos]+1][point_x[pos]]==" " or mapping[point_y[pos]+1][point_x[pos]]==">":
            enqueue(point_x[pos], point_y[pos] + 1)

        #left
        if mapping[point_y[pos]][point_x[pos]-1]==" " or mapping[point_y[pos]][point_x[pos]-1]==">":
            enqueue(point_x[pos]-1, point_y[pos])

        #right
        if mapping[point_y[pos]][point_x[pos]+1]==" " or mapping[point_y[pos]][point_x[pos]+1]==">":
            enqueue(point_x[pos] + 1, point_y[pos])
        pos+=1
    repeat=0
    for i in range(len(point_x)):
        if point_x[i]==fx and point_y[i]==fy:
            print("True",point_x[i],point_y[i])
            repeat=1
    if repeat==0:
        print("False")




mapping=map2arr(test)
find_road(mapping)

javascript

var check = function(maze) {
    var map = maze.split("\n").map($ => $.split(""));
    var flatmap = map.reduce((a, b) => a.concat(b), []);

    var [row, col] = [map.length, map[0].length];
    var [startrow, startcol] = [parseInt(flatmap.indexOf("<") / col), flatmap.indexOf("<") % col];

    var queue = [];
    var visited = Array.from(Array(row), v => Array.from(Array(col), () => 0));

    enqueue(queue, [startrow, startcol], map, visited);

    while (queue.length > 0) {
        var [row, col] = queue.shift();
        if (map[row][col] === ">") return true;

        enqueue(queue, [row - 1, col], map, visited);
        enqueue(queue, [row + 1, col], map, visited);
        enqueue(queue, [row, col + 1], map, visited);
        enqueue(queue, [row, col - 1], map, visited);
    }
    return false;
};

var enqueue = function(queue, [row, col], map, visited) {
    if (map[row] && map[row][col] && map[row][col] !== "#" && visited[row][col] !== 1) {
        queue.push([row, col]);
        visited[row][col] = 1;
    }
};

var maze1 =
`<     >`;

var maze2 =
`########
#<     #
#  ##  #
#  ##  #
#     >#
########`;

var maze3 =
`#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######`;

var maze4 =
`<   #   >`;

var maze5 =
`########
#<     #
#     ##
#    #>#
########`;

var maze6 =
`#< #  #
#  #  #
#  # >#`;

console.log(check(maze1));
console.log(check(maze2));
console.log(check(maze3));

console.log(check(maze4));
console.log(check(maze5));
console.log(check(maze6));

[Python 3.6]

import queue

def isPass(mazeStr):
    lineArr = mazeStr.strip().split("\n")
    mazeArr = []
    visitArr = []
    strAxis = ()
    for x, line in enumerate(lineArr):
        varArr = []
        for y, var in enumerate(line):
            if var == '<': strAxis = (x, y)
            varArr.append(var)
        mazeArr.append(varArr)
        visitArr.append([0 for i in range(y)])

    que = queue.Queue()
    que.put(strAxis)

    while not que.empty():
        curAxis = que.get()
        if mazeArr[curAxis[0]][curAxis[1]] == '>': return True
        if visitArr[curAxis[0]][curAxis[1]]: continue
        visitArr[curAxis[0]][curAxis[1]] = 1
        if curAxis[0] - 1 > 0: que.put((curAxis[0] - 1, curAxis[1]))
        if curAxis[0] + 1 < len(visitArr): que.put((curAxis[0] + 1, curAxis[1]))
        if curAxis[1] - 1 > 0: que.put((curAxis[0], curAxis[1] - 1))
        if curAxis[1] + 1 < len(visitArr[0]): que.put((curAxis[0], curAxis[1] + 1))

    return False

mazeStr = """
#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######
"""
print(isPass(mazeStr))

import numpy as np


class Maze:
    def __init__(self, inp_str):
        self.arr = np.array([list(l) for l in inp_str.split('\n')])
        self.X, self.Y = len(self.arr), len(self.arr[0])

        for i in range(self.X):
            for j in range(self.Y):
                if self.arr[i, j] == '<': self.startpos = (i, j)
                elif self.arr[i, j] == '>': self.endpos = (i, j)

    # BFS
    def escapable(self):
        Q = [self.startpos]
        while Q:
            u = Q.pop(0)
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                v = (u[0] + dx, u[1] + dy)
                if v == self.endpos:
                    return True
                elif 0 <= v[0] < self.X and 0 <= v[1] < self.Y and self.arr[v] == ' ':
                    self.arr[v] = '.'
                    Q.append(v)

        return False

C#: DFS

using System.Linq;
using static System.Console;

class Maze
{
    static bool DFS(char[][] maze, int x, int y)
    {
        if (x < 0 || x >= maze.Length || 
            y < 0 || y >= maze[0].Length ||
            maze[x][y] == '#')
        {
            return false;
        }
        if (maze[x][y] == '>')
            return true;

        maze[x][y] = '#';
        return DFS(maze, x - 1, y) ||
            DFS(maze, x + 1, y) ||
            DFS(maze, x, y - 1) ||
            DFS(maze, x, y + 1);
    }

    static void Main(string[] args)
    {        
        string[] rawData = new string[] {
            "<     >",
            "########\n#<     #\n#  ##  #\n#  ##  #\n#     >#\n########",
            "#######\n#<    #\n##### #\n#     #\n# #####\n# #   #\n# # # #\n#   #>#\n#######",
            "<   #   >",
            "########\n#<     #\n#     ##\n#    #>#\n########",
            "#< #  #\n#  #  #\n#  # >#"
        };

        foreach (string data in rawData)
        {
            string[] rows = data.Split('\n');
            char[][] maze = new char[rows.Length][];
            for (int i = 0; i < rows.Length; i++)
            {
                maze[i] = rows[i].ToCharArray();
            }

            for (int i = 0; i < rows.Length; i++)
            { 
                if (rows[i].Contains('<'))
                {
                    WriteLine(DFS(maze, i, rows[i].IndexOf('<')));
                    break;
                }
            }
        }
    }
}

파이썬 3.6

"""
아이디어>
 1) 미로 데이터의 시작점('<')을 찾습니다.
 2) 시작점부터 현재 위치에서 이동 가능한 방향을 찾아 목적지('>')에 당도할때까지 이동합니다.
 3) 목적지가 있는 라인(data[g])까지 가면 목적지 위치 접근 가능 여부를 확인하여, 접근이 가능하면 탐색을 계속하고, 접근이 불가능할 경우('false) 탐색을 종료합니다.
 4) 이동 중 목적지에 도착하면('true') 탐색을 종료합니다. 
"""

def inputdata():
    n = int(input(''))
    data = [input('') for i in range(n)]
    return data

def check(g,h,tmp): # 현재 위치에서 갈 수 있는 방향을 찾습니다.
    if tmp != 'left' and data[g][h+1] != '#':
        return 'right'
    elif tmp != 'up' and data[g+1][h] != '#':
        return 'down'
    elif tmp != 'down' and data[g-1][h] != '#':
        return 'up'
    elif tmp != 'right' and data[g][h-1] != '#':
        return 'left'
    else:
        return 0

def maze(data):
    t,h,tmp = 0,1,''
    if len(data) == 1: # 미로가 한 줄짜리인 경우 중간에 장애물이 있는지만 체크합니다.
        for i in data[0]:
            if i == '<':
                t += 1
            elif i == ' ':
                pass
            elif i == '#':
                t -= 1
            elif i == '>' and t == 1:
                print('true')
                return
            else:
                print('false')
                return                

    elif len(data) > 1:
        for g,road in enumerate(data):
            if '<' in road:
                while True:
                    if data[g][h] == '>':
                        print('true')
                        return
                    elif tmp != 'left' and check(g,h,tmp) == 'right':
                        tmp = check(g,h,tmp)
                        h += 1
                    elif tmp != 'up' and check(g,h,tmp) == 'down':
                        tmp = check(g,h,tmp)
                        g += 1
                    elif tmp != 'down' and check(g,h,tmp) == 'up':
                        tmp = check(g,h,tmp)
                        g -= 1
                    elif tmp != 'right' and check(g,h,tmp) == 'left':
                        tmp = check(g,h,tmp)
                        h -= 1
                    else: # 모든 길에 대한 탐색을 마치기 전에 막다른 길을 만나면 이전 단계로 돌아가 다른 방법으로 탐색을 계속합니다.
                        if tmp == 'down':
                            g -= 1
                            tmp = 'up'
                        elif tmp == 'right':
                            h -= 1
                            tmp = 'left'
                        elif tmp == 'left':
                            h += 1
                            tmp = 'right'
                        elif tmp == 'up':
                            g += 1
                            tmp = 'down'
                    if g == len(data)-1:
                        break
                    if '>' in data[g]:
                        tmp = ''
                        if not check(g,data[g].index('>'),tmp):
                            break
        print('false')

if __name__ == "__main__":
    data = inputdata()
    for i in data:
        print(''.join(i))
    miro(data)

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

class Point{

    int row = 0;
    int vertical = 0;
    char value = ' ';

    public Point(int row, int vertical, char value){
        this.row = row;
        this.vertical = vertical;
        this.value = value;
    }

}

public class Maze {

    static char[][] maze = null;

    public static boolean bfs(int row, int vertical){

        Queue<Point> queue = new LinkedList<>();

        queue.offer(new Point(row, vertical, '<'));

        while(!queue.isEmpty()){

            Point point = queue.poll();

            if(point.value == '>'){
                return true;
            }
            if(point.row > 0 && maze[point.row-1][point.vertical] != '#' && maze[point.row-1][point.vertical] != '0'){ //위 탐색
                queue.offer(new Point(point.row-1, point.vertical, maze[point.row-1][point.vertical]));
                maze[point.row-1][point.vertical] = '0';
            }
            if(point.row+1 < maze.length && maze[point.row+1][point.vertical] != '#' && maze[point.row+1][point.vertical] != '0'){ //아래 탐색
                queue.offer(new Point(point.row+1, point.vertical, maze[point.row+1][point.vertical]));
                maze[point.row+1][point.vertical] = '0';
            }
            if(point.vertical > 0 && maze[point.row][point.vertical-1] != '#' && maze[point.row][point.vertical-1] != '0'){ // 왼쪽 탐색
                queue.offer(new Point(point.row, point.vertical-1, maze[point.row][point.vertical-1]));
                maze[point.row][point.vertical-1] = '0';
            }
            if(point.vertical+1 < maze[0].length && maze[point.row][point.vertical+1] != '#' && maze[point.row][point.vertical+1] != '0'){ // 오른쪽 탐색
                queue.offer(new Point(point.row, point.vertical+1, maze[point.row][point.vertical+1]));
                maze[point.row][point.vertical+1] = '0';
            }
        }

        return false;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc;
        try {
            sc = new Scanner(new File("C:\\Users\\present\\Desktop\\test\\maze.txt"));
            List<String> mazeRow = new ArrayList<>();

            while(sc.hasNext()){
                mazeRow.add(sc.nextLine());
            }

            maze = new char[mazeRow.size()][mazeRow.get(0).length()];

            for(int i=0; i < mazeRow.size(); i++){
                for(int j=0; j < mazeRow.get(i).length(); j++)
                    maze[i][j] = mazeRow.get(i).charAt(j);
            }

            int startRow = 0;
            int startVertical = 0;

            start : for(int i=0; i< maze.length; i++){
                for(int j=0; j< maze[i].length; j++){
                    if(maze[i][j] == '<'){
                        startRow = i;
                        startVertical = j;
                        break start;
                    }
                }
            }

            System.out.println(bfs(startRow, startVertical));

        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

    }

}

    import scala.collection.mutable.Queue

    def mazePath(maze:Array[Array[Char]]):Boolean = {
        var start = (0, 0)
        var end = (0, 0)
        println(maze.length, maze(0).length)

        for(i <- 0 until maze.length; j <- 0 until maze(i).length){
            if(maze(i)(j) == '<'){
                start = (i, j)
            }
            if(maze(i)(j) == '>'){
                end = (i, j)
            }
        }
        println(s"start: ${start} end: ${end}")

        val q = Queue(start)
        var bool = false
        val direction = List((0, 1), (1, 0), (-1, 0), (0, -1))
        while(!q.isEmpty && !bool){
            maze.map(_.toList).toList.foreach{v => println(v.mkString(" "))}
            val (a, b) = q.dequeue
            if(maze(a)(b) == '>') bool = true
            maze(a)(b) = '-'
            for((x, y) <- direction){
                if(a + x >=0 && a + x < maze.length && b + y >=0 && b + y < maze(0).length && maze(a + x)(b + y) != '-' && maze(a + x)(b + y) != '#' && !q.contains((a + x, b + y))){
                    q.enqueue((a + x, b + y))
                }
            }

        }
        bool

    }
    println(mazePath(
        Array(
        "########".toCharArray,
        "#<    >#".toCharArray,
        "#  ##  #".toCharArray,
        "#  ##  #".toCharArray,
        "#      #".toCharArray,
        "########".toCharArray)
        ))
    println(mazePath(
        Array(
        "#######".toCharArray,
        "#<    #".toCharArray,
        "##### #".toCharArray,
        "#     #".toCharArray,
        "# #####".toCharArray,
        "# #   #".toCharArray,
        "# # # #".toCharArray,
        "#   #>#".toCharArray,
        "#######".toCharArray)
        ))

def tree_trim(tree):
    for i,j in tree.items():
        if isinstance(j,list):
            for k in j:
                if k in tree and isinstance(tree[k],int):
                    tree[i] = tree[k]
                    break
    return tree

def maze_roadtree(maze):
    s = (' ','<','>')
    tree = {}
    tnum = lambda x,y: x*len(maze[0])+y
    for i in range(len(maze)):
        for j in range(len(maze[i])):
            if maze[i][j] in s:
                if maze[i][j] == '<': start = tnum(i,j)
                elif maze[i][j] == '>': end = tnum(i,j)

                if len(tree) == 0: tree[tnum(i,j)] = tnum(i,j)
                else:
                    tree.setdefault(tnum(i,j),[])
                    if i-1 >= 0 and maze[i-1][j] in s: tree[tnum(i,j)].append(tnum(i-1,j))
                    if j-1 >= 0 and maze[i][j-1] in s: tree[tnum(i,j)].append(tnum(i,j-1))
                    if i+1 < len(maze) and maze[i+1][j] in s: tree[tnum(i,j)].append(tnum(i+1,j))
                    if j+1 < len(maze[0]) and maze[i][j+1] in s: tree[tnum(i,j)].append(tnum(i,j+1))
                    if tree[tnum(i,j)] == []: tree[tnum(i,j)] = tnum(i,j)
            tree = tree_trim(tree)
    return tree, start, end


miro = '''\
########
#<     #
#  ##  #
#  ##  #
#     >#
########'''
maze = miro.split('\n')

tree,s,e = maze_roadtree(maze)
print(tree[s]==tree[e])

import queue

class Vertex:
    def __init__(self, id, x, y):
        self.adj = []
        self.id = id
        self.x = x
        self.y = y
        self.visit = False
        self.distance = 0

    def is_exist_adj(self, v):
        for av in self.adj:
            if v.x == av.x and v.y == av.y:
                return True
        return False

    def add_adj(self, v):
        self.adj.append(v)


class MazeGraph:
    def __init__(self, limitx, limity):
        self.verts = []
        self.limitx = limitx
        self.limity = limity

    def clear(self):
        del self.verts
        self.verts = []

    def find(self, v):
        for vert in self.verts:
            if v.x == vert.x and v.y == vert.y:
                return True
        return False

    def getVert(self, x, y):
        for vert in self.verts:
            if vert.x == x and vert.y == y:
                return vert
        return None

    def add(self, v):
        if True == self.find(v):
            return False
        self.verts.append(v)

    def get_near_coord(self, x, y, limitx, limity, dir):
        nx = ny = -1
        if 'West' == dir:
            if x > 1:
                nx = x - 1
                ny = y
        elif 'East' == dir:
            if x < limitx - 1:
                nx = x + 1
                ny = y
        elif 'South' == dir:
            if y < limity - 1:
                nx = x
                ny = y + 1
        elif 'North' == dir:
            if y > 1:
                nx = x
                ny = y - 1
        return nx, ny

    def link(self, x, y):
        v = self.getVert(x, y)
        if None == v:
            print('No vertex %d, %d' %(x, y))
            return False
        for dir in ['North', 'East', 'South', 'West']:
            nx, ny = self.get_near_coord(v.x, v.y, self.limitx, self.limity, dir)
            #print('linking: {}:{},{} -> DIR {:5s} : {},{}'.format(
            #    v.id, v.x, v.y, dir, nx, ny))
            if -1 == nx or -1 == ny:
                continue    # no need to link (not exist)
            nvert = self.getVert(nx, ny)
            if None == nvert:
                continue
            if False == nvert.is_exist_adj(v):
                nvert.add_adj(v)
            if False == v.is_exist_adj(nvert):
                v.add_adj(nvert)
        return True

    def dfs(self, start_x, start_y):
        vert = self.getVert(start_x, start_y)
        traqueue = queue.Queue()
        vert.visit = True
        traqueue.put(vert)

        while not traqueue.empty():
            v = traqueue.get()
            print('{},{}'.format(v.x, v.y))
            for adv in v.adj:
                if False == adv.visit:
                    adv.visit = True
                    traqueue.put(adv)

    def is_reachable(self, start_x, start_y, id):
        vert = self.getVert(start_x, start_y)
        if None == vert:
            print('No start {}, {}'.format(start_x, start_y))
        traqueue = queue.Queue()
        vert.visit = True
        traqueue.put(vert)
        reachable = False
        while not traqueue.empty():
            v = traqueue.get()
            if id == v.id:
                print('FOUND: {}:{},{}'.format(v.id, v.x, v.y))
                reachable = True
            #print('{},{}'.format(v.x, v.y))
            for adv in v.adj:
                if False == adv.visit:
                    adv.visit = True
                    traqueue.put(adv)
        return reachable

    def print_info(self):
        for v in self.verts:
            print('{}:{},{}'.format(v.id, v.x, v.y))
            for av in v.adj:
                print('\t{}:{},{}'.format(av.id, av.x, av.y))
            print()




mazes = [
"""#< #  #
#  #  #
#  # >#""", 
"""<   #   >""", 
"""<     >""",
"""########
#<     #
#  ##  #
#  ##  #
#     >#
########""",
"""#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######"""
]

def check_reachable(startx, starty, maze_lines):
    limitx = len(maze_lines[0])
    limity = len(maze_lines)
    maze   = MazeGraph(limitx, limity)

    for y in range(limity):
        for x in range(limitx):
            if '#' == maze_lines[y][x]:
                continue
            maze.add(Vertex(maze_lines[y][x], x, y))

    for y in range(limity):
        for x in range(limitx):
            if '#' == maze_lines[y][x]:
                continue
            maze.link(x, y)

    print(maze.is_reachable(startx, starty, '>'))

def get_start_coord(maze):
    for y in range(len(maze)):
        for x in range(len(maze[0])):
            if '<' == maze[y][x]:
                return x, y
    return -1, -1

def print_maze(maze):
    for y in range(len(maze)):
        for x in range(len(maze[0])):
            print(maze[y][x], end =' ')
        print()

for maze in mazes:
    maze_lines = maze.split('\n')
    print_maze(maze_lines)
    x, y = get_start_coord(maze_lines)
    if -1 == x or -1 == y:
        continue
    print('start coordinate', x, y, sep = ',')
    check_reachable(x, y, maze_lines)
    print()

# 미로의 입력값을 넣어 주는 곳
maze = """#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######"""

# 미로의 입력값을 배열 형태로 바꿔주는 함수
mid_step = maze.split("\n")
width = len(mid_step[0])
hight = len(mid_step)
box = []
for row in mid_step:
    for char in row:
        if char =='<':
            char = True
        box.append(char)
cal_box = np.array(box).reshape(hight,width)

# 마지막 출구의 위치 저장
for h in range(hight):
    for w in range(width):
        if cal_box[h][w] == '>':
            ch_pnt=[h,w]

# 미로의 한 점에서 한 점의 주변에 True 값이 있으면 값을 True 변환해주는 함수
def check(box):
    for h in range(hight):
        for w in range(width):
            if cal_box[h][w] != '#':
                # 크기가 작더라도 작동하도록 만들어 주는 예외처리 문장
                try:
                    n1 = (cal_box[h-1][w] == 'True') 
                    n2 = (cal_box[h+1][w] == 'True')
                    n3 = (cal_box[h][w-1] == 'True')
                    n4 = (cal_box[h][w+1] == 'True')
                    if any([n1,n2,n3,n4]):
                        cal_box[h][w] = 'True'
                except:
                    pass

# 함수의 최대 실행 횟수 설정 및 출구가 "True"값을 가지면 자동으로 종료
def main(box):
    for cnt in range(width*hight):
        if cal_box[ch_pnt[0]][ch_pnt[1]] == 'True':
            break
        check(box)

    if cal_box[ch_pnt[0]][ch_pnt[1]] == 'True':
        print("True")
    elif cal_box[ch_pnt[0]][ch_pnt[1]] == '>':
        print("False")

main(cal_box)

알고리즘
1. '<'에서 갈 수 있는 모든 방향으로 한걸음 전진해서 '<'로 바꾼다.
기존의 '<'은 '#'으로 바꾼다.
왔던 길로 되돌아가지 못하게 하기 위함.
'<'에서 사방이 '#'으로 막혀있다면 그 '<'만 '#'으로 바뀌게 된다.
2. 이 작업을 계속 반복한다.
3. '<'와 인접한 곳에 '>'이 있다면 탐색을 종료하고 True를 반환한다.
4. '<'가 하나도 없다면 False를 반환한다.
어떤 경로로 가더라도 도착지점에 도달할 수 없다는 뜻이다.

참고 : '<'와 '>'사이의 최단경로를 알고 싶다면 탐색한 경로를 역으로 추적하면 된다.

def StrToArray(a):
    a = list(a)
    p = a.count('\n') + 1                #행수
    q = (len(a) - a.count('\n')) // p    #열수
    L = [[0]*q for i in range(p)]

    k = 0
    for i in range(len(a)):
        if a[i] == '\n':
            continue
        else:
            L[k//q][k%q] = a[i]
            k += 1
    return L

def ArrayToStr(L):
    T = []
    p = len(L)
    q = len(L[0])
    Q = [[0]*q for i in range(p)]
    for i in range(p):
        for j in range(q):
            Q[i][j] = L[i][j]

    for i in range(len(Q)-1):
        Q[i].append('\n')
    for i in range(len(Q)):
        T += Q[i]
    return ''.join(T)



def oneStep(L):
    k = 0   #사방이 막혀있는지 확인하는 변수. 진행할때마다 값이 오름.
    for i in range(len(L)):
        for j in range(len(L[0])):
            if L[i][j] == '<':
                for m in -1, 1:
                    try:
                        if i+m < 0:
                            raise NotImplementedError
                        if L[i+m][j] == '>':
                            return 1
                        else:
                             try:
                                if L[i+m][j] != '#':
                                    if i+m < 0:
                                        raise NotImplementedError
                                    else:
                                        L[i+m][j] = 't'
                                        k += 1
                             except:
                                 pass
                    except:
                        pass
                for m in -1, 1:
                    try:
                        if j+m < 0:
                            raise NotImplementedError
                        if L[i][j+m] == '>':
                            return 1
                        else:
                            try:
                                if L[i][j+m] != '#':
                                    if j+m < 0:
                                        raise NotImplementedError
                                    else:
                                        L[i][j+m] = 't'
                                        k += 1
                            except:                            
                                pass
                    except:
                        pass

                L[i][j] = '#'


    for i in range(len(L)):
        for j in range(len(L[0])):
            try:                
                if L[i][j] == 't':
                    L[i][j] = '<'
            except:
                pass
    if k == 0:  #진행할 곳이 더이상 없다면
        return -1
    else:
        return 0

def displaySteps(s):
    L=StrToArray(s)
    test = 0
    while test != 1:
        test = oneStep(L)
        print(ArrayToStr(L))
        print('')
        if test == -1:
            return False
    return True


def isPassable(s):
    L=StrToArray(s)
    test = 0
    while test != 1:
        test = oneStep(L)
        if test == -1:
            return False
    return True


s="""#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######"""


print(displaySteps(s))

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;

struct Pos {
    int x;
    int y;
};

bool findPath(vector<string> maze, int w, int h, Pos* pStart)
{
    vector<vector<vector<Pos>*> > posOwn;
    vector<Pos> block;
    Pos wrong = { -1,-1 };
    block.push_back(wrong);
    for (int i = 0; i < h; i++) {
        posOwn.push_back(* new vector<vector<Pos>*>);
        for (int j = 0; j < w; j++) {
            if (maze[i][j] == ' ') {
                posOwn[i].push_back(nullptr);
            }
            else
            {
                posOwn[i].push_back(&block);
            }
        }
    }

    queue<vector<Pos> > routes;
    vector<Pos> sp;
    sp.push_back(*pStart);
    routes.push(sp);
    while (!routes.empty())
    {
        vector<Pos> *cPath = &routes.front();
        Pos ls = cPath->back();
        if (ls.y > 0 && maze[ls.y - 1][ls.x] == '>') {
            return true;
        }
        if (ls.y > 0 && maze[ls.y-1][ls.x] == ' ' && posOwn[ls.y-1][ls.x] == nullptr) {
            vector<Pos>* up = new vector<Pos>;
            up->assign(cPath->begin(), cPath->end());
            up->push_back(* new Pos{ up->back().x , up->back().y - 1 });
            posOwn[ls.y - 1][ls.x] = up;
            routes.push(*up);
        }
        if (ls.x > 0 && maze[ls.y][ls.x - 1] == '>') {
            return true;
        }
        if (ls.x > 0 && maze[ls.y][ls.x - 1] == ' ' && posOwn[ls.y][ls.x - 1] == nullptr) {
            vector<Pos>* left = new vector<Pos>;
            left->assign(cPath->begin(), cPath->end());
            left->push_back(*new Pos{ left->back().x -1 , left->back().y});
            posOwn[ls.y][ls.x -1] = left;
            routes.push(*left);
        }
        if (ls.y < h-1 && maze[ls.y + 1][ls.x] == '>') {
            return true;
        }
        if (ls.y < h - 1 && maze[ls.y + 1][ls.x] == ' ' && posOwn[ls.y + 1][ls.x] == nullptr) {
            vector<Pos>* down = new vector<Pos>;
            down->assign(cPath->begin(), cPath->end());
            down->push_back(*new Pos{ down->back().x , down->back().y + 1 });
            posOwn[ls.y + 1][ls.x] = down;
            routes.push(*down);
        }
        if (ls.x < w-1 && maze[ls.y][ls.x + 1] == '>') {
            return true;
        }
        if (ls.x < w-1 && maze[ls.y][ls.x + 1] == ' ' && posOwn[ls.y][ls.x + 1] == nullptr) {
            vector<Pos>* right = new vector<Pos>;
            right->assign(cPath->begin(), cPath->end());
            right->push_back(*new Pos{ right->back().x + 1 , right->back().y });
            posOwn[ls.y][ls.x + 1] = right;
            routes.push(*right);
        }
        routes.pop();
    }
    return false;
}

bool testMaze(vector<string> maze, int x, int y)
{
    Pos start = { 0,0 };
    Pos end = { 0,0 };
    for (int i = 0; i < y; i++) {
        for (int j = 0; j < maze[i].size(); j++) {
            if (maze[i][j] == '<') {
                start.x = j;
                start.y = i;
            }
        }
    }
    return findPath(maze,x,y,&start);
}

#입력이 끝나는 부분이 표시되지 않았기 때문에, 다른 분 코드를 보고 ' '를 끝으로 만들었습니다.


end=None
y, x = 0, 0
IN = [list(input())]
while(IN[-1] != [' ']):
    IN.append(list(input()))

IN = IN[:-1]
nowlist = [[i, IN[i].index('<')] for i in range(len(IN)) if '<' in IN[i]]

i=0
while end == None and len(nowlist) != 0:
    for i in nowlist:
        for j in [[i[0]+1, i[1]], [i[0], i[1]+1], [i[0]-1, i[1]], [i[0], i[1]-1]]:
            try:
                if j[0] < 0 or j[1] < 0:
                    continue
                if IN[j[0]][j[1]] == ' ':
                    IN[j[0]][j[1]] = '0'
                    nowlist.append([j[0], j[1]])
                elif IN[j[0]][j[1]] == '>':
                    end = True
                    break
            except:
                pass
        nowlist.remove(i)

if end == True:
    print('true')
else:
    print('false')

Javascript(ES6)...

`텍스트 형태의 미로를 2차원 배열로 저장, <(입구) 를 찾은다음, 입구 주변의 상하좌우 칸을 살펴서 공백이면 재귀호출하고 >(출구)면 true 반환하고 막혀있으면 false 반환, 모든 반환 값을 ||(or) 연산자로 묶음. 출구(true 값)가 있다면 전체 결과는 true, 없다면 false 가 됨`;

class Maze {
    constructor(maze) {
        this.str_maze = maze;
        this.arr_maze = this._to_arr();
        this.is_exitable
    }

    // 텍스트 형태의 미로를 2차원 배열로 전환
    _to_arr() {
        let result = [];
        for(let v of this.str_maze.split('\n')) {
            result.push([...v]);
        }
        return result;
    }

    // 입구를 찾는 함수, 입구의 위치를 [row, column] 형태로 반환
    _find_entrance() {
        for(let r = 0, c = 0; r < this.arr_maze.length; r++) {
            c = this.arr_maze[r].indexOf('<');
            if(c > -1) { return [r, c]; }
        }
        return [0, 0];
    }

    // 미로가 탈출이 가능한지 판단 함수, 주어진 위치 [row, column]의 상하좌우를 살펴 재귀호출 혹은 결과반환
    _can_exit([r, c]) {

        // 주어진 [r, c] 의 상하좌우 셀 안 내용을 담음, 만일 범위가 벗어났다면 'X'
        let cells = [];
        cells[0] = (r - 1 == -1) ? 'X' : this.arr_maze[r - 1][c];
        cells[1] = (c + 1 == this.arr_maze[r].length) ? 'X' : this.arr_maze[r][c + 1];
        cells[2] = (r + 1 == this.arr_maze.length) ? 'X' : this.arr_maze[r + 1][c];
        cells[3] = (c - 1 == -1) ? 'X' : this.arr_maze[r][c - 1];

        // 현재 [r, c] 위치의 셀 내용이 공백일 경우 다른 문자로 채움(다시 재귀호출 당하지 않기 위함)
        this.arr_maze[r][c] = '.';

        // cells 배열 안에 출구(>) 가 있다면 true, 다른 문자가 있다면 false, 공백이라면 재귀호출
        if(cells.indexOf('>') > -1) { return true; }
        return (cells[0] == ' ') ? this._can_exit([r - 1, c]) : false ||
               (cells[1] == ' ') ? this._can_exit([r, c + 1]) : false ||
               (cells[2] == ' ') ? this._can_exit([r + 1, c]) : false ||
               (cells[3] == ' ') ? this._can_exit([r, c - 1]) : false;
    }

    // 미로와 탈출 가능한지 여부 출력
    print_maze() {
        console.log(this.str_maze);
        console.log(this._can_exit(this._find_entrance()));
        console.log();
    }
}

let mazes = [
`<     >`,
`########
#<     #
#  ##  #
#  ##  #
#     >#
########`,
`#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######`,
`<   #   >`,
`########
#<     #
#     ##
#    #>#
########`,
`#< #  #
#  #  #
#  # >#`, 
];

new Maze(mazes[0]).print_maze();
new Maze(mazes[1]).print_maze();
new Maze(mazes[2]).print_maze();
new Maze(mazes[3]).print_maze();
new Maze(mazes[4]).print_maze();
new Maze(mazes[5]).print_maze();

Python 3...

조금 다른 방식...

class Maze:
    def __init__(self, maze):
        self.maze = maze
        self.arr_maze = self.__str_to_arr()

    # 텍스트 형태의 미로를 리스트로 변환
    def __str_to_arr(self):
        arr = []
        for s in self.maze.split('\n'):
            arr.append([*s])

        return arr

    # 입구'<' 를 찾음, 입구들의 위,오른쪽,아래,왼쪽 칸을 살핌, 출구'>' 가 있으면 return True 리턴, 현재 위치를 '.' 으로 변경, 주위 빈 공간을 다시 입구로 변환, 재귀호출
    def __can_exit(self, m):

        # 모든 입구를 찾아 리스트에 위치를 담음
        entrance = [(r, c) for r, row in enumerate(m) for c, col in enumerate(row) if col == '<']

        # 입구 주변 칸 위치와 내용 set 저장
        neighbors = set()
        for r, c in entrance:
            if r - 1 != -1:
                neighbors.add((r - 1, c, m[r - 1][c]))
            if r + 1 != len(m):      
                neighbors.add((r + 1, c, m[r + 1][c]))
            if c - 1 != -1:
                neighbors.add((r, c - 1, m[r][c - 1]))
            if c + 1 != len(m[0]):
                neighbors.add((r, c + 1, m[r][c + 1]))
        neighbors = list(neighbors)

        # 주변 칸에 출구'>' 가 있으면 return True, 주변 칸에 빈공간' ' 이 없다면 return False
        chars = [x[2] for x in neighbors]
        if '>' in chars:
            return True
        if ' ' not in chars:
            return False

        # 현재 위치를 '.' 으로 변경
        for r, c in entrance:
            m[r][c] = '.'

        # 주변 빈 공간을 다시 입구로 변환
        for r, c, v in [n for n in neighbors if n[2] == ' ']:
            m[r][c] = '<' 

        # 재귀호출
        return self.__can_exit(m)

    # 테스트
    def print_maze(self):
        print(self.maze)
        print(self.__can_exit(self.arr_maze))
        print()

mazes = [
    '<     >',
    '########\n#<     #\n#  ##  #\n#  ##  #\n#     >#\n########',
    '#######\n#<    #\n##### #\n#     #\n# #####\n# #   #\n# # # #\n#   #>#\n#######',
    '<   #   >',
    '########\n#<     #\n#     ##\n#    #>#\n########',
    '#< #  #\n#  #  #\n#  # >#',
]
Maze(mazes[0]).print_maze()
Maze(mazes[1]).print_maze()
Maze(mazes[2]).print_maze()
Maze(mazes[3]).print_maze()
Maze(mazes[4]).print_maze()
Maze(mazes[5]).print_maze()

from copy import deepcopy

map_ ='''########
#<     #
#  ##  #
#  ##  #
#     >#
########
'''

map_list_1 = [list(i) for i in map_.split('\n')]

def start_point(li) : # 시작점 검색
    col = 0
    for lines in li :
        if '<' in lines :
            return [lines.index('<'), col]
        col += 1
    return False

def search_(li) :
    queue = [li+[start_point(li)]]
    while len(queue) != 0 :
        head = queue.pop(0)
        for cond in [(-1, 0, head[-1][0]), (1, 0, len(head[0])-1-head[-1][0]), (0, -1, head[-1][1]), (0, 1, len(head)-3-head[-1][1])] :  # 순서대로 dx, dy, 방향, 좌표가 데이터 범위 내 있을 조건
            head_1 = deepcopy(head)
            if cond[2] > 0 and head_1[head_1[-1][1]+cond[1]][head_1[-1][0]+cond[0]] == ('>') : # 목표지점까지 도착할 수 있으면 True를 반환
                return True
            if cond[2] > 0 and head_1[head_1[-1][1]+cond[1]][head_1[-1][0]+cond[0]] == (' ') : # 좌표가 데이터 범위 내에 있으면서 탐색 가능한 경우
                head_1[head_1[-1][1]][head_1[-1][0]] = '#' # 방문한 좌표 '#'로 대체
                head_1[-1][0], head_1[-1][1] = head_1[-1][0]+cond[0], head_1[-1][1]+cond[1] #좌표 갱신
                queue.append(head_1) # queue의 마지막에 추가
    return False # 목표지점까지 도달한 경우가 없으면 False 반환
print(search_(map_list_1))

bfs로 풀었습니다.

결과

True

inp1="<     >"
inp2="""########
#<     #
#  ##  #
#  ##  #
#     >#
########"""
inp3="""#######
#<    #
##### #
#     #
# #####
# #   #
# # # #
#   #>#
#######"""
inp4="<   #   >"
inp5="""########
#<     #
#     ##
#    #>#
########"""
inp6="""#< #  #
#  #  #
#  # >#"""
lst1=[list(ln) for ln in inp1.split("\n")]
lst2=[list(ln) for ln in inp2.split("\n")]
lst3=[list(ln) for ln in inp3.split("\n")]
lst4=[list(ln) for ln in inp4.split("\n")]
lst5=[list(ln) for ln in inp5.split("\n")]
lst6=[list(ln) for ln in inp6.split("\n")]

maxmc,nt=0,0 #maxmc->최대 움직일 수 있는 횟수(=공백의 개수), nt->움직임을 시도한 횟수(oneway일 경우 움직인 횟수)
def mazepossible(lst):
    global nt,maxmc
    for i in range(len(lst)): #리스트에서 공백의 개수를 찾아 maxmc를 구한다
        for j in range(len(lst[0])):
            if lst[i][j]==" ":
                maxmc+=1
    while nt<=maxmc: #움직임을 시도한 횟수(또는 움직인 횟수)가 최대 움직일 수 있는 횟수보다 작은 동안
        for i in range(len(lst)):
            for j in range(len(lst[0])):
                if lst[i][j]=="<":
                    y,x=i,j #"<"문자의 위치 값 y,x를 일단 찾는다(while루프를 돌게 되면 여러 개일 수도 있음)
        for dy,dx in [(-1,0),(1,0),(0,1),(0,-1)]: #상하좌우 이동
            if 0<=y+dy<len(lst) and 0<=x+dx<len(lst[0]) and lst[y+dy][x+dx]==" ": #해당 좌표(현재 "<"인 곳)에서 dy,dx를 더했을 때, 좌표가 미로의 범위 안에 있고, 그 값이 공백일 경우
                lst[y+dy][x+dx]="<" #공백인 곳을 "<"로 바꾸고
                lst[y][x]="#" #"<"였던 곳은 "#"으로 바꾼다
            if 0<=y+dy<len(lst) and 0<=x+dx<len(lst[0]) and lst[y+dy][x+dx]==">": #해당 좌표(현재 "<"인 곳)에서 dy,dx를 더했을 때, 좌표가 미로의 범위 안에 있고, 그 값이 ">"일 경우
                return True #탈출 가능하므로 True
        nt+=1
        if nt>maxmc: #움직임을 시도한 횟수가 최대 움직인 횟수를 넘어버리면 그 미로는 탈출이 불가능하므로 False
            return False

결과

print(mazepossible(lst1)) #True
print(mazepossible(lst2)) #True
print(mazepossible(lst3)) #True
print(mazepossible(lst4)) #False
print(mazepossible(lst5)) #False
print(mazepossible(lst6)) #False

Ruby 서로소 집합으로 구현

class DisjointSet def initialize @parent = Hash.new { |hash, key| hash[key] = key } end

def root_of(node)
    node_list = []
    while @parent[node] != node
        node_list << node
        node = @parent[node] 
    end

    #path compression       
    node_list.each {|e|
        @parent[e] = node;
    }
    node
end

def connect(node1, node2)
    @parent[root_of(node1)] = root_of(node2)
end

def connected?(node1, node2)
    root_of(node1) == root_of(node2)
end

end

class Map
def map_data @map_data end

def map_data=(rhs)
    @map_data = 
        case rhs
        when String
            rhs.split("\n")
        when Array
            rhs
        end         
end

def get_adjacents(y, x)
    [[y+1, x], [y-1, x], [y, x-1], [y, x+1]].find_all { |y,x| 
        y >= 0 && y < @y_size && x >= 0 && x < @x_size
    }
end

def passable?
    @y_size = @map_data.size
    @x_size = @map_data.first.length

    ds = DisjointSet.new
    st = []
    ed = []

    #[[0,0], [0, 1], ... , [0, @x_size-1], [1, 0] , ... , [@y_size-1, @x_size-1]
    coords = [*0...@y_size].product [*0...@x_size]  
    coords.each{|y, x| 
        case @map_data[y][x]
        when '<'     #start point 
            st = [y, x]
        when '>' #end point
            ed = [y, x]
        when '#' #wall - do nothing
            nil
        else
            get_adjacents(y, x).find_all{|y, x| @map_data[y][x] != '#' }.each { |ny, nx| 
                ds.connect([y, x], [ny, nx] ) 
            }
        end
    }
    ds.connected?(st, ed)       
end

end

m = Map.new m.map_data="< >" puts m.passable?

m.map_data="########\n#< #\n# ## #\n# ## #\n# >#\n########" puts m.passable?

m.map_data="#######\n#< #\n##### #\n# #\n# #####\n# # #\n# # # #\n# #>#\n#######" puts m.passable?

m.map_data="< # >" puts m.passable?

m.map_data="########\n#< #\n# ##\n# #>#\n########" puts m.passable?

m.map_data="#< # #\n# # #\n# # >#" puts m.passable?

# 016 미로 통과 검사

strings = []

while True:
    string = input()
    if string == '':
        break
    else:
        strings.append([ x for x in string])

max_x = len(strings[0])
max_y = len(strings)

# direction : 0=left, 1=up, 2=right, 3=down
direction = [ [-1, 0], [0, -1], [1, 0], [0, 1] ]


def print_result():
    for y in range(max_y):
        print(''.join(strings[y]))


def find_path(x, y):
    global strings, direction
    temp_string = strings[y][x]

    for dx, dy in direction:
        next_x, next_y = x+dx, y+dy
        if next_x in range(max_x) and next_y in range(max_y):
            if strings[next_y][next_x] == '>':
                strings[y][x] = '.'
                print_result()
                exit('true')
            elif strings[next_y][next_x] == ' ':
                strings[y][x] = '.'
                find_path(next_x, next_y)
    strings[y][x] = temp_string             # Invalid path

    return


for y in range(max_y):
    for x in range(max_x):
        if strings[y][x] == '<':        # 시작 위치 탐색
            for dx, dy in direction:    # 시작 위치에서 공백있는 부분 탐색
                next_x, next_y = x + dx, y + dy
                if next_x in range(max_x) and next_y in range(max_y):
                    if strings[next_y][next_x] == ' ':
                        find_path(next_x, next_y)

exit('false')

direct = [(-1,0),(0,1),(1,0),(0,-1)]
def find_path(r,c,d,maze):
    for i in range(3):
        tr, tc = r + direct[(d + i)%4][0], c + direct[(d + i)%4][1]
        if 0<=tr<len(maze) and 0<=tc<len(maze[0]):
            if maze[tr][tc]=='>':
                return True
            elif maze[tr][tc]==' ':
                return find_path(tr, tc, (d + i)%4 + 3, maze)
    return False

# inp = """########
# #<     #
# #  ##  #
# #  ##  #
# #     >#
# ########"""

# inp = """#######
# #<    #
# ##### #
# #     #
# # #####
# # #   #
# # # # #
# #   #>#
# #######"""

inp = """########
#<     #
#     ##
#    #>#
########"""

#inp = """<   #   >"""

maze = inp.split('\n')
start = []
sr = -1
for line in maze:
    sr += 1
    sc = -1
    for l in line:
        sc += 1
        print('%-2s' %l, end='')
        if l=='<':
            start.append(sr)
            start.append(sc)
    print()

result = False
for i in range(4):
    tr, tc = start[0]+direct[i][0], start[1]+direct[i][1]
    if 0<=tr<len(maze) and 0<=tc<len(maze[0]) and maze[tr][tc]==' ':
        if find_path(tr, tc, i + 3, maze):
            result=True
            break

print('>>', result)

list_list_map_lines=list()
while True:
    list_map_line=list(input())
    if len(list_map_line)==0:
        break
    list_list_map_lines.append(list_map_line)

for y in range(len(list_list_map_lines)):
    for x in range(len(list_list_map_lines[y])):
        print(list_list_map_lines[y][x],end='')
    print()

print()
break_check='false'
for y in range(len(list_list_map_lines)):
    for x in range(len(list_list_map_lines[y])):
        if list_list_map_lines[y][x]=='<':
            if (y-1)<=(len(list_list_map_lines[y])-1)and list_list_map_lines[y-1][x]==' ':
                list_list_map_lines[y-1][x]='?'
                break_check='true'
                break
            elif (x+1)<=(len(list_list_map_lines[y])-1)and list_list_map_lines[y][x+1]==' ':
                list_list_map_lines[y][x+1]='?'
                break_check='true'
                break
            elif (y+1)<=(len(list_list_map_lines)-1):
                list_list_map_lines[y+1][x]='?'
                break_check='true'
                break
        if break_check=='true':
            break
print()

lines=len(list_list_map_lines)
break_check='false'
for y in range(len(list_list_map_lines)):
    for x in range(len(list_list_map_lines[y])):
        yy=y
        xx=x
        if list_list_map_lines[yy][xx]=='<' and list_list_map_lines[yy-1][xx]=='?':
            count_1=0
            yy-=2
            while count_1<100:
                while True:
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    yy-=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                yy+=1
                xx+=1
                while True:
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    xx+=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                yy+=1
                xx-=1
                while True:
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    yy+=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                yy-=1
                xx-=1
                while True:
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    xx-=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                yy-=1
                xx+=1

                count_1+=1
            else:
                print('false')
                break_check='true'

        elif list_list_map_lines[yy][xx]=='<' and list_list_map_lines[yy][xx+1]=='?':
            count_2=0
            xx+=2
            while count_2<100:
                while True and (lines!=1 or lines==1):
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    xx+=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                if lines!=1:
                    yy+=1
                    xx-=1
                while True and lines!=1:
                        if list_list_map_lines[yy][xx]==' ':
                            list_list_map_lines[yy][xx]='?'
                        else:
                            break
                        yy+=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                if lines!=1:
                    yy-=1
                    xx-=1
                while True and lines!=1:
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    xx-=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                if lines!=1:
                    yy-=1
                    xx+=1
                while True and lines!=1:
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    yy-=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                if lines!=1:
                    yy+=1
                    xx+=1

                count_2+=1
            else:
                print('false')
                break_check='true'

        elif list_list_map_lines[yy][xx]=='<' and list_list_map_lines[yy+1][xx]=='?':
            count_3=0
            yy+=2
            while count_3<100:
                while True:
                        if list_list_map_lines[yy][xx]==' ':
                            list_list_map_lines[yy][xx]='?'
                        else:
                            break
                        yy+=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                yy-=1
                xx+=1
                while True:
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    xx+=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                yy-=1
                xx-=1
                while True:
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    yy-=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                yy+=1
                xx-=1
                while True:
                    if list_list_map_lines[yy][xx]==' ':
                        list_list_map_lines[yy][xx]='?'
                    else:
                        break
                    xx-=1
                if list_list_map_lines[yy][xx]=='>':
                    print('true')
                    break_check='true'
                    break

                yy+=1
                xx-=1

                count_3+=1
            else:
                print('false')
                break_check='true'              

        if break_check=='true':
            break

    if break_check=='true':
        break

for y in range(len(list_list_map_lines)):
    for x in range(len(list_list_map_lines[y])):
        print(list_list_map_lines[y][x],end='')
    print()