CodeIQ：くねくね最短経路

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「くねくね最短経路」（CodeIQ）を参照してください。

問題の概要

標準入力から次のような入力が与えられます。
Sはスタート地点、gはゴール地点、Xは通れない場所、_は通れる場所、/は区切り文字です。次のように入力されます。
s_____/______/__X___/___X__/______/_____g
これは次のような地図として解釈されます。
s     
      
  X   
   X  
      
     g

決して直進することなく（1マス進んだら左右に曲がって）進んだ場合、ゴールにたどり着くまでの最短距離を出力してください。ゴールにたどり着けない場合はX（大文字のX）を出力してください。

上記のマップの場合、進み方は次のようになります。
s┓┏┓  
 ┗┛┗┓ 
  X ┗┓
   X┏┛
    ┗┓
     g

私のプログラム

Pythonで解答しています。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#!/usr/local/bin/python3
# -*- coding:utf-8 -*-
 
import fileinput
 
class Maze:
    def __init__(self):
        self.Map = [[0 for j in range(8)] for i in range(8)]    # 探索対象の地図
        self.Memo = [[-1 for j in range(8)] for i in range(8)]  # 訪問履歴（-1は未訪問）
        self.Start = [0,0]  # スタート地点座標
        self.Goal = [8,8]   # ゴール地点座標
        self.Direction = ((-1,0),(1,0),(0,-1),(0,1))    # 上下左右
        self.Queue = [] # 進行方向候補 1要素の構成：[[座標X,Y],(Directionのどれか),反転回数]
 
    # 入力値から地図を作成する
    # 地図は一回り大きく作成し、外周は全て到達不能として扱う
    def createMap(self, input):
        i=1
        j=1
        for c in input:
            if (c == 's') or (c == 'g') or (c == '_'):
                self.Map[i][j] = 1
 
                if c == 's':
                    self.Start = [i,j]
                elif c == "g":
                    self.Goal = [i,j]
 
                j+=1
 
            elif c == 'X':
                self.Map[i][j] = 0
                j+=1
            elif c == '/':
                i += 1
                j=1
 
    def printMap(self):
        print("----- Map -----")
        for row in self.Map:
            print(row)
        print("Start:" + str(self.Start))
        print("Goal :" + str(self.Goal))
 
    def printMemo(self):
        print("----- Memo -----")
        for row in self.Memo:
            print(list(map(lambda a:str.format("{0:2d}",a),row)))
 
    # 進行方向と反対向きを返す
    def reverseDirection(self, d):
        if d == (1,0):
            return (-1,0)
        elif d == (-1,0):
            return (1,0)
        elif d == (0,1):
            return (0,-1)
        elif d == (0,-1):
            return (0,1)
        return (0,0)
 
    # 「くねくね最短経路」（https://codeiq.jp/q/2428）の探索
    def searchBend(self):
        # キューにスタート地点を入れる
        self.Queue.append([self.Start, (0,0), 0])
 
        # スタート地点の訪問履歴をセット
        self.Memo[self.Start[0]][self.Start[1]] = 0
 
        # 次のサイクルの探索候補
        nextQueue = []
 
        # キューが空になるかゴールに達するまで探索する
        while len(self.Queue) != 0:
            cur, bd, revC = self.Queue.pop(0)   # 現在の座標と前回の進行方向、反転回数
            if cur == self.Goal:
                return True
 
            # 反転は2回まで
            if revC <= 2:
                for d in self.Direction:    # 上下左右にわかれているので4回ループ
                    #方向チェック（やってきた方向と同じ進行方向は処理しない）
                    if d == bd:
                        continue
 
                    # 探索対象の座標
                    x = cur[0] + d[0]
                    y = cur[1] + d[1]
 
                    # 座標が移動できないなら無視
                    if self.Map[x][y] == 0:
                        continue
 
                    # 訪問先に到達するための歩数
                    step = self.Memo[cur[0]][cur[1]] + 1
 
                    # 座標が最短到達候補ならキューに追加して、Memoを更新
                    if (d != self.reverseDirection(bd)) and (self.Memo[x][y] == -1):    # 進む場合は未訪問の場所だけ
                        nextQueue.append([[x,y], d, 0])
                        self.Memo[x][y] = step
                    else:   # 戻る方向
                        nextQueue.append([[x,y], d, revC+1])
                        self.Memo[x][y] = step
 
            # 続きがある場合、Queueを再設定
            if (len(nextQueue) != 0) and (len(self.Queue) == 0) :
                self.Queue = nextQueue
                nextQueue = []
 
        return False
 
    def getStep(self):
        return self.Memo[self.Goal[0]][self.Goal[1]]
 
if __name__ == "__main__":
    for line in fileinput.input():
        if not line.strip():
            continue
 
        line = line.strip()
 
        maze = Maze()
        maze.createMap(line)
#       maze.printMap()
        ret = maze.searchBend()
#       maze.printMemo()
        if(ret):
            print(str(maze.getStep()))
        else:
            print("X")

解説

幅優先探索をひねった問題です。
わざわざクラスを作っていますが、別にクラスを作らなくてもできます。確か、Pythonを勉強中でクラスを使ってみたかったからクラスにしたのだと思います。
やたらと丁寧にコメントが入っているのであまり説明の必要はない気がしますが解説します。 Queueとメモ、ループを使った典型的な幅優先探索のロジックを元に実装しています。

マップ

createMap()関数で入力値を2次元配列の地図にしています。メンバ変数Mapが地図です。ちょっと工夫しているのは一回り大きく領域をとって、最外周を全て到達不能としていることです。このようにすることで配列の範囲チェックをしなくて済むためロジックが簡単になります。

メモ

メモにはマップ上の地点に到達するためにかかった最短歩数を記録します。これはマップと同じサイズで用意して、マップの座標と一致させます。

進行方向リスト

メンバ定数Directionです。この地図は4方向に進めるのでそれぞれの方向をリスト化しループで処理できるようにします。

StartとGoal

それぞれスタート地点の座標を[y,x]で保持します。

searchBendPath()

経路探索を行う本体です。基本的にはqueueを使ってループで処理する幅優先探索のアルゴリズムです。調べれば説明はたくさん見つかるので基本的なロジックは簡単に説明して、この問題特有の部分を少し詳しく説明します。
まず、スタート地点をqueueにつみます。
ループでqueueを取り出し、そこから進むことのできる場所をチェックし、ゴールでなく進行可能な場所ならqueueにつみます。これをゴールに到達するか、queueがなくなる（ゴールに到達する経路がない）まで繰り返します。

今回の問題の場合、進行方向は前に進んだのと同じ方向以外になるので、そのチェックが必要です（83〜84行目）。

もう一つ気をつけなければいけないのは戻ることはOKと言うことです。
基本的には未到達の場所だけ進むのですが、戻る場合はすでに到達済みの場所を更新しなければなりません。基本的な幅優先探索ではあるマスに到達するために必要な歩数が少ない値で更新することが許されますが、戻る場合は歩数が大きくなるにもかかわらず更新できなければなりません。これを処理しているのが98〜103業目です。今回の場合、1歩進むごとに必要なコストは常に1なので戻ることを考えなければ未到達でない場所に初めてたどり着けばそれが最短経路になります(98行目のself.Memo[x][y] == -1)。戻る場合はこの条件をチェックしません。
そして、戻ることを許した場合、反転を繰り返してしまうことをケアしないと計算量が大変なことになります（80行目）。

雑感

この問題は見た瞬間に深さ優先探索でいけると思いましたが、最初、戻って良いことを考慮できておらず一度リジェクトされました。時間切れではなかったのでテストパターンと期待される結果を教えてもらえたのでわりとすぐに解決できましたが、それがなかったらかなり苦労したんじゃないかと思います。