Pythonでロボットが目標座標に到達できるか判定するプログラムの書き方

ロボットが2次元座標平面（直交座標系）の原点 (0, 0) にいるとします。ロボットが実行できる移動のリストが与えられ、各移動は N（北）、S（南）、W（西）、E（東） のいずれかです。このロボットが、目的地の座標 (x, y) に到達できるかどうかを判定するプログラムを作成します。

例えば、入力が moves = ['N','N','E','E','S']、目的地が (x, y) = (2, 1) の場合、出力は True になります。北に2回、東に2回、南に1回移動することで、最終的に (2, 1) に到達できるからです。

解決のアプローチ

この問題は、ロボットの移動を実際にシミュレーションすることで解けます。手順は以下の通りです。

• 現在座標を表す変数 temp_coord を [0, 0] で初期化する
• moves 内の各移動について以下を繰り返す：
  • 移動が "N" の場合 → temp_coord[1] に 1 を加算（y座標を+1）
  • 移動が "S" の場合 → temp_coord[1] から 1 を減算（y座標を-1）
  • 移動が "E" の場合 → temp_coord[0] に 1 を加算（x座標を+1）
  • 移動が "W" の場合 → temp_coord[0] から 1 を減算（x座標を-1）
• すべての移動を処理した後、temp_coord[0] が coord[0] と等しく、かつ temp_coord[1] が coord[1] と等しければ True を返し、そうでなければ False を返す

このアルゴリズムの計算量は、移動リストを1回走査するだけなので O(n)、使用する追加メモリは座標2つ分のみで O(1) と非常に効率的です。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution:
    def solve(self, moves, coord):
        temp_coord = [0, 0]
        for move in moves:
            if move == "N":
                temp_coord[1] += 1
            elif move == "S":
                temp_coord[1] -= 1
            elif move == "E":
                temp_coord[0] += 1
            elif move == "W":
                temp_coord[0] -= 1
        return temp_coord[0] == coord[0] and temp_coord[1] == coord[1]

ob = Solution()
moves = ['N', 'N', 'E', 'E', 'S']
coord = [2, 1]
print(ob.solve(moves, coord))

入力

['N','N','E','E','S'], [2,1]

出力

True

まとめ

このように、移動コマンドを1つずつ追跡して最終座標を計算し、目標座標と比較するシンプルなシミュレーションで問題を解決できます。座標ごとに移動の回数を数える方法（NとS、EとWの差を取る方法）でも同様の結果が得られますので、状況に応じて実装しやすい方法を選ぶとよいでしょう。