(D 3)5105迷宮距離-迷宮最短距離BFS/DFSを求める

80950 ワード

swExpertAcademy アルゴリズム概念アルゴリズム#アルゴリズム# テキストリンク

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIoJqqfYDFAWg#
迷宮

1.BFSを使用するプール（距離変数を使用）

の開始点を見つけ、

キューに始点を挿入し、

繰り返し

キューから

を取り出す.

到着点で終了

番、アクセスなし

および

距離1と

を増加

4方向は0<=に再投入する.

import sys
sys.stdin = open("input.txt")

from collections import deque


T = int(input())

def find_start() :
    for y in range(N) :
        for x in range(N) :
            if miro[y][x] == '2' :
                return x, y

def func(start_x, start_y) :
    queue = deque([(start_x, start_y, 0)]) # 시작x, y, 시작점과의거리
    visited = [[0] * N for _ in range(N)]

    move_x = [1,-1,0,0] # 오른쪽, 왼쪽, 위, 아래
    move_y = [0,0,-1,1]
    while queue : # 큐가 빌때 까지
        now_x, now_y, distance = queue.popleft()
        if miro[now_y][now_x]=='3' :
            return distance-1 # 도착지점은 길이에 포함 안되네..
        if miro[now_y][now_x] in ['0','2'] and visited[now_y][now_x] == 0 : # 길이고, 방문하지 않은 경우
            visited[now_y][now_x] = 1
            distance += 1
            for i in range(4) :
                next_x = now_x + move_x[i]
                next_y = now_y + move_y[i]
                if 0<=next_x<N and 0<=next_y<N :
                    queue.append((next_x, next_y, distance))



# BFS - 최소경로 / 실행시간 :실행 시간 : 0.15346s
for tc in range(1, T+1):


    N = int(input()) # 미로 크기
    miro = [input() for _ in range(N)]
    start_x, start_y = find_start()
    result = func(start_x, start_y)
    if result == None :
        result =0

    print("#{} {}".format(tc, result))

1～1回外：リストでBFSを実現

はなぜかDequeで実現したBFSより速い(なに???

import sys
sys.stdin = open("input.txt")


T = int(input())

def find_start() :
    for y in range(N) :
        for x in range(N) :
            if miro[y][x] == '2' :
                return x, y

def func(start_x, start_y) :
    ####################차이#####################
    queue = [(start_x, start_y, 0)] # 시작x, y, 시작점과의거리
    ############################################
    visited = [[0] * N for _ in range(N)]

    move_x = [1,-1,0,0] # 오른쪽, 왼쪽, 위, 아래
    move_y = [0,0,-1,1]
    while queue : # 큐가 빌때 까지
        now_x, now_y, distance = queue.pop(0)
        if miro[now_y][now_x]=='3' :
            return distance-1 # 도착지점은 길이에 포함 안되네..
        if miro[now_y][now_x] in ['0','2'] and visited[now_y][now_x] == 0 : # 길이고, 방문하지 않은 경우
            visited[now_y][now_x] = 1
            distance += 1
            for i in range(4) :
                next_x = now_x + move_x[i]
                next_y = now_y + move_y[i]
                if 0<=next_x<N and 0<=next_y<N :
                    queue.append((next_x, next_y, distance))

# BFS - 최소경로 list로 구현 / 실행시간 :실행 시간 : 0.12844s
for tc in range(1, T+1):


    N = int(input()) # 미로 크기
    miro = [input() for _ in range(N)]
    start_x, start_y = find_start()
    result = func(start_x, start_y)
    if result == None :
        result =0

    print("#{} {}".format(tc, result))

1-2号外:距離として「アクセス」を使用

アクセスを使用して街として

を使用

import sys
sys.stdin = open("input.txt")

from collections import deque


T = int(input())

def find_start() :
    for y in range(N) :
        for x in range(N) :
            if miro[y][x] == '2' :
                return x, y

####################차이#####################
def func(start_x, start_y) :
    queue = deque([(start_x, start_y)]) # 시작x, y, 시작점과의거리
    visited = [[0] * N for _ in range(N)]

    move_x = [1,-1,0,0] # 오른쪽, 왼쪽, 위, 아래
    move_y = [0,0,-1,1]
    while queue : # 큐가 빌때 까지
        now_x, now_y = queue.popleft()
        if miro[now_y][now_x]=='3' :
            return visited[now_y][now_x]-1 # 도착지점은 길이에 포함 안되네..

        for i in range(4) :
            next_x = now_x + move_x[i]
            next_y = now_y + move_y[i]
            if 0<=next_x<N and 0<=next_y<N and (miro[next_y][next_x] in ['0','3']) and visited[next_y][next_x] == 0:
                visited[next_y][next_x] = visited[now_y][now_x] +1
                queue.append((next_x, next_y))
#########################################


# BFS - 최소경로/ visited 거리로 이용 / 실행시간 :실행 시간 : 0.15346s
for tc in range(1, T+1):


    N = int(input()) # 미로 크기
    miro = [input() for _ in range(N)]
    start_x, start_y = find_start()
    result = func(start_x, start_y)
    if result == None :
        result =0

    print("#{} {}".format(tc, result))

1-3号外:長さを測定し、次のテーブルにジャンプして距離を取得するかどうかを確認します。

各タブのキューのサイズを取得

は、同じレベルのキュー

のみを含む.

ループ終了時に距離を増やし、キューのサイズを再求めます.

from collections import deque


T = int(input())

def find_start() :
    for y in range(N) :
        for x in range(N) :
            if miro[y][x] == '2' :
                return x, y

def func(start_x, start_y) :
    queue = deque() # 큐 생성
    queue.append([start_x, start_y]) # 시작x, y, 시작점과의거리
    visited = [[0] * N for _ in range(N)]

    move_x = [1,-1,0,0] # 오른쪽, 왼쪽, 위, 아래
    move_y = [0,0,-1,1]
    ###########################차이점############################
    distance =0
    while queue : # 큐가 빌때 까지
        size = len(queue)
        for i in range(size) :
            now_x, now_y = queue.popleft()
            if miro[now_y][now_x] == '3':
                return distance - 1  # 도착지점은 길이에 포함 안되네..

            elif miro[now_y][now_x] in ['0', '2'] and visited[now_y][now_x] == 0:  # 길이고, 방문하지 않은 경우
                visited[now_y][now_x] = 1

                for i in range(4):
                    next_x = now_x + move_x[i]
                    next_y = now_y + move_y[i]
                    if 0 <= next_x < N and 0 <= next_y < N:
                        queue.append((next_x, next_y))
        distance+=1
    ###############################################################


# BFS - 최소경로 / 실행시간 :실행 시간 : 0.15346s
for tc in range(1, T+1):


    N = int(input()) # 미로 크기
    miro = [input() for _ in range(N)]
    start_x, start_y = find_start()
    result = func(start_x, start_y)
    if result == None :
        result =0

    print("#{} {}".format(tc, result))

2.DFSを使用するプール

目的地に到着後、到着点をアクセスに置くことなく、様々な方法で距離

を探す.

最短距離

の結果:最短距離が安全になる可能性があります

未満:最短経路と中間経路が重なる場合は

import sys
sys.stdin = open("input.txt")

T = int(input())

def find_start() :
    for y in range(N) :
        for x in range(N) :
            if miro[y][x] == '2' :
                return x, y

move_x = [1,-1,0,0] # 오른쪽, 왼쪽, 위, 아래
move_y = [0,0,-1,1]
####################차이#####################
def func(now_x, now_y, distance) :
    global result
    if miro[now_y][now_x] == '3' : # 도착하면 지금까지 구한 거리랑 비교
        if (distance-1) < result :
            result = distance-1
        return

    if miro[now_y][now_x] in ['0', '2'] and visited[now_y][now_x] == 0:  # 길이고, 방문하지 않은 경우
        visited[now_y][now_x] = 1
        distance += 1
        for i in range(4):
            next_x = now_x + move_x[i]
            next_y = now_y + move_y[i]
            if 0 <= next_x < N and 0 <= next_y < N:
                func(next_x, next_y, distance)
#############################################

# DFS 로 모든 경로 구하고 최소값으로 구하기 / 실행 시간 : 0.12835s
for tc in range(1, T+1):
    N = int(input())  # 미로 크기
    miro = [input() for _ in range(N)]
    start_x, start_y = find_start()

    visited = [[0] * N for _ in range(N)]
    result = N ** 2
    func(start_x, start_y, 0)

    if result == N**2: # 초기값에서 변화가 없을 경우 도착 못한것
        result = 0
    
    print("#{} {}".format(tc, result))

2-1. DFSアプリケーションのフルナビゲーションを使用してすべてのパスを検索

すべてのパスを参照(DFSアプリケーション>>バックエンド追跡)

に到達到達点の経路は、以前に求めた到達経路よりも小さく、最小距離

と記憶する.

import sys

sys.stdin = open("input.txt")

T = int(input())


def find_start():
    for y in range(N):
        for x in range(N):
            if miro[y][x] == '2':
                return x, y


move_x = [1, -1, 0, 0]  # 오른쪽, 왼쪽, 위, 아래
move_y = [0, 0, -1, 1]


def func(now_x, now_y, distance):
    global result
    if miro[now_y][now_x] == '3':  # 도착하면 지금까지 구한 거리랑 비교
        if (distance - 1) < result:
            result = distance - 1
        return

    distance += 1
    for i in range(4):
        next_x = now_x + move_x[i]
        next_y = now_y + move_y[i]
        if 0 <= next_x < N and 0 <= next_y < N and miro[next_y][next_x] in ['0', '3'] and visited[next_y][next_x] == 0:  # 길이고, 방문하지 않은 경우:
            visited[next_y][next_x] = 1
            func(next_x, next_y, distance)
            ####################차이#####################
            visited[next_y][next_x] = 0
            ############################################



# 모든 경로 구하고 최소값으로 구하기 / 실행 시간 : 0.13294s
for tc in range(1, T + 1):
    N = int(input())  # 미로 크기
    miro = [input() for _ in range(N)]
    start_x, start_y = find_start()

    visited = [[0] * N for _ in range(N)]
    result = N ** 2
    func(start_x, start_y, 0)

    if result == N ** 2:  # 초기값에서 변화가 없을 경우 도착 못한것
        result = 0

    print("#{} {}".format(tc, result))

3.バックアップトレース（DFS+割り込み条件の追加）

DFSを行うが、先に求める最短距離の探索

は行わない.

の結果:最短距離が安全になる可能性があります

未満:最短経路と中間経路が重なる場合は

import sys

sys.stdin = open("input.txt")

T = int(input())


def find_start():
    for y in range(N):
        for x in range(N):
            if miro[y][x] == '2':
                return x, y

move_x = [1, -1, 0, 0]  # 오른쪽, 왼쪽, 위, 아래
move_y = [0, 0, -1, 1]

def func(now_x, now_y, distance):
    global result

    if miro[now_y][now_x] == '3':  # 도착하면 지금까지 구한 거리랑 비교
        if (distance - 1) < result:
            result = distance - 1
        return
    ####################차이#####################
    elif (distance-1) > result : # 거리가 result보다 커서 더이상 판단할 필요가 없는 경우 끝내기
        return
    ############################################

    if miro[now_y][now_x] in ['0', '2'] and visited[now_y][now_x] == 0:  # 길이고, 방문하지 않은 경우
        visited[now_y][now_x] = 1
        distance += 1
        for i in range(4):
            next_x = now_x + move_x[i]
            next_y = now_y + move_y[i]
            if 0 <= next_x < N and 0 <= next_y < N:
                func(next_x, next_y, distance)

# 백트래킹(DFS + 조건)로 모든 경로 구하고 최소값으로 구하기 / 실행 시간 : 0.12167s
for tc in range(1, T + 1):
    N = int(input())  # 미로 크기
    miro = [input() for _ in range(N)]
    start_x, start_y = find_start()

    visited = [[0] * N for _ in range(N)]
    result = N ** 2
    func(start_x, start_y, 0)

    if result == N ** 2:  # 초기값에서 변화가 없을 경우 도착 못한것
        result = 0

    print("#{} {}".format(tc, result))

バックエンド追跡使用率パスを3～1個参照

import sys

sys.stdin = open("input.txt")

T = int(input())


def find_start():
    for y in range(N):
        for x in range(N):
            if miro[y][x] == '2':
                return x, y


move_x = [1, -1, 0, 0]  # 오른쪽, 왼쪽, 위, 아래
move_y = [0, 0, -1, 1]


def func(now_x, now_y, distance):
    global result
    if miro[now_y][now_x] == '3':  # 도착하면 지금까지 구한 거리랑 비교
        if (distance - 1) < result:
            result = distance - 1
        return
    ####################차이#####################
    elif (distance-1) > result : # 중단 조건 추가
        return
    ############################################

    distance += 1
    for i in range(4):
        next_x = now_x + move_x[i]
        next_y = now_y + move_y[i]
        if 0 <= next_x < N and 0 <= next_y < N and miro[next_y][next_x] in ['0', '3'] and visited[next_y][next_x] == 0:  # 길이고, 방문하지 않은 경우:
            visited[next_y][next_x] = 1
            func(next_x, next_y, distance)
            visited[next_y][next_x] = 0



# 백트래킹 활용 경로탐색 / 실행 시간 : 0.12256s
for tc in range(1, T + 1):
    N = int(input())  # 미로 크기
    miro = [input() for _ in range(N)]
    start_x, start_y = find_start()

    visited = [[0] * N for _ in range(N)]
    result = N ** 2
    func(start_x, start_y, 0)

    if result == N ** 2:  # 초기값에서 변화가 없을 경우 도착 못한것
        result = 0

    print("#{} {}".format(tc, result))

注意事項

DFSコンセプトを使用して

の最短距離を実現する場合、Pythonの最大再帰深さはランタイムエラーを引き起こす可能性があります.そのため、BFSはもっと人気がある.

Reference

この問題について((D 3)5105迷宮距離-迷宮最短距離BFS/DFSを求める), 我々は、より多くの情報をここで見つけました https://velog.io/@swhan9404/D35105미로의거리

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

初探linuxサブシステムセットのledサブシステム(一)

Toy Problem 11 #