주어진 행렬에는 요소 위치를 분석하기 위한 4개의 개체가 있습니다. 왼쪽, 오른쪽, 아래쪽, 위쪽입니다.
너비 우선 탐색은 주어진 2차원 행렬의 두 요소 사이의 최단 거리를 찾는 것뿐입니다. 따라서 각 셀에는 다음과 같이 4개의 숫자로 표현할 수 있는 4개의 연산이 있습니다.
- '2'는 행렬의 셀이 소스임을 나타냅니다.
- '3'은 행렬의 셀이 대상임을 나타냅니다.
- '1'은 셀이 한 방향으로 더 이동할 수 있음을 나타냅니다.
- '0'은 행렬의 셀이 어떤 방향으로도 이동할 수 없음을 나타냅니다.
어도비 정당화를 기반으로 주어진 매트릭스에 대해 너비 우선 검색 작업을 수행할 수 있습니다.
이 문제를 해결하기 위한 접근 방식
BFS를 사용하여 전체 행렬을 탐색하고 모든 셀 사이의 최소 또는 최단 거리를 찾는 알고리즘은 다음과 같습니다.
- 먼저 행과 열을 입력합니다.
- 주어진 행과 열로 행렬을 초기화합니다.
- 정수 함수 shortestDist(int row, int col, int mat[][col])은 행, 열 및 행렬을 입력으로 사용하고 행렬 요소 간의 최단 거리를 반환합니다.
- 변수 소스 및 대상을 초기화하여 소스 및 대상 요소를 찾습니다.
- 요소가 '3'이면 대상으로 표시하고 요소가 '2'이면 소스 요소로 표시합니다.
- 이제 주어진 행렬에서 너비 우선 검색을 구현하기 위해 대기열 데이터 구조를 초기화합니다.
- 큐에 있는 행렬의 행과 열을 쌍으로 삽입합니다. 이제 셀로 이동하여 대상 셀인지 아닌지 확인하십시오. 대상 셀의 거리가 최소값이거나 현재 셀보다 작으면 거리를 업데이트합니다.
- 다시 다른 방향으로 이동하여 현재 셀에서 셀의 최소 거리를 찾습니다.
- 최소 거리를 출력으로 반환합니다.
예시
import queue
INF = 10000
class Node:
def __init__(self, i, j):
self.row_num = i
self.col_num = j
def findDistance(row, col, mat):
source_i = 0
source_j = 0
destination_i = 0
destination_j = 0
for i in range(0, row):
for j in range(0, col):
if mat[i][j] == 2 :
source_i = i
source_j = j
if mat[i][j] == 3 :
destination_i = i
destination_j = j
dist = []
for i in range(0, row):
sublist = []
for j in range(0, col):
sublist.append(INF)
dist.append(sublist)
# initialise queue to start BFS on matrix
q = queue.Queue()
source = Node(source_i, source_j)
q.put(source)
dist[source_i][source_j] = 0
# modified BFS by add constraint checks
while (not q.empty()):
# extract and remove the node from the front of queue
temp = q.get()
x = temp.row_num
y = temp.col_num
# If move towards left is allowed or it is the destnation cell
if y - 1 >= 0 and (mat[x][y - 1] == 1 or mat[x][y - 1] == 3) :
# if distance to reach the cell to the left is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x][y - 1] :
dist[x][y - 1] = dist[x][y] + 1
next = Node(x, y - 1)
q.put(next)
# If move towards right is allowed or it is the destination cell
if y + 1 < col and (mat[x][y + 1] == 1 or mat[x][y + 1] == 3) :
# if distance to reach the cell to the right is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x][y + 1] :
dist[x][y + 1] = dist[x][y] + 1
next = Node(x, y + 1)
q.put(next);
# If move towards up is allowed or it is the destination cell
if x - 1 >= 0 and (mat[x - 1][y] == 1 or mat[x-1][y] == 3) :
# if distance to reach the cell to the up is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x - 1][y] :
dist[x - 1][y] = dist[x][y] + 1
next = Node(x - 1, y)
q.put(next)
# If move towards down is allowed or it is the destination cell
if x + 1 < row and (mat[x + 1][y] == 1 or mat[x+1][y] == 3) :
# if distance to reach the cell to the down is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x + 1][y] :
dist[x + 1][y] = dist[x][y] + 1
next = Node(x + 1, y)
q.put(next)
return dist[destination_i][destination_j]
row = 5
col = 5
mat = [ [1, 0, 0, 2, 1],
[1, 0, 2, 1, 1],
[0, 1, 1, 1, 0],
[3, 2, 0, 0, 1],
[3, 1, 0, 0, 1] ]
answer = findDistance(row, col, mat);
if answer == INF :
print("No Path Found")
else:
print("The Shortest Distance between Source and Destination is:")
print(answer) 출력
The Shortest Distance between Source and Destination is:2