프로그래머스 게임 맵 최단거리 BFS 질문

작성일 2024.02.11댓글 1건

게시물 수정 , 삭제는 로그인 필요

from collections import deque

def solution(maps):

n = len(maps)

m = len(maps[0])

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우 이동

queue = deque([(0, 0, 1)]) # 시작 위치와 이동 횟수(1)를 큐에 추가

maps[0][0] = 0 # 시작 위치를 방문했음을 표시

while queue:

x, y, dist = queue.popleft()

# 상대 팀 진영에 도착한 경우 최단 거리 반환

if x == n - 1 and y == m - 1:

return dist

# 상하좌우 이동 확인

for dx, dy in dirs:

nx = x + dx

ny = y + dy

# 이동 가능한 위치인지 확인

if 0 <= nx < n and 0 <= ny < m

and maps[nx][ny] == 1:

queue.append((nx, ny, dist + 1)) # 이동 가능한 위치를 큐에 추가

maps[nx][ny] = 0 # 방문했음을 표시

# 상대 팀 진영에 도착할 수 없는 경우 -1 반환

return -1

코드 답을 보니 이런식으로 풀었는데, 여기서 궁금한게 최단 거리는 어떻게 산정하는 건가요?..
계속 봐도 해설을 못하겠어서 질문 남깁니다 감사합니다.

익명 작성일 -

... 계속 봐도 해설을 못하겠어서 질문 남깁니다 감사합니다. [답변] 최단 거리 산정은 큐에서 요소를 꺼낼 때마다 이동 가능한 모든 방향으로의 위치를...

... 하기 때문에 효율성이 떨어집니다. bfs로 방법을 바꾸셔야 합니다. bfs는 답을 찾는 순간, 최단 코스를 보장하기 때문에 dfs보다 빠릅니다.

... 질문하신 내용 자세히 읽어 보고 복-붙, 매크로 답변이... - 각종 열차 부품이나 맵 모드도 다운로드... - 목표점까지 최단거리로 레일을 연결해야 하는 게임입니다....

... 히스토리 최단거리의 러쉬루트와 본진을 우회하는... 가한 맵. MBC게임 공식맵 중 보기드문 전략형 맵으로... 전 지식인을 자잘한 질문하는 용도로만 쓰기 때문에 매일...

... 그래서 질문 올립니다... 자세하고 정확하게 적어주셔야 내공... (이게임은 파티플이 생명)을 즐기려면 그냥 퀘스트를 수행하면 되고, 빠른 렙업을 원할땐 최단거리 퀘스트...

... 질문이 좀 부족하다면 파일을 보내드릴 수도... 고려한 최단거리를 검색하는 알고리즘인데요. 저도... 있다면(게임이 아닌 실제 경로라면 트리데이터일...

... 질문이 너무 많아서.. 1. 프로그래밍 언어를 배우기... 프로그래밍 언어도 여러개가 있잖아영 그중 게임이나... DFS, BFS, 최단 거리 관련 그래프 알고리즘, 퇴각검색법...

... 클라는 프레임 이동거리(100px 이라고 가정) 인 100px로... ( 본디 A* 라는 것이 최단경로를 뽑아내는 것이라서... 라는 질문이 나오기 마련이죠 보통 게임서버에선 이동에...

... 제가 게임을 하고 잇어욜 ㅇ_ ㅇ 씨디 겜 이구요 [EB 드래곤볼 제트 2] <<일케 써잇어욜 ㅇ_ㅇ 긍데 질문점... 턴마다 최단거리로 손오공을 쫓게되는거지요 첫 재배맨을...

허접이라고 놀리지 마시구요;;^^ 몇가지 질문하겠습니다 1.... 혹은 게임이 시작된 초반라운드부터 끝라운드까지... 기본적인 경우로는 양팀간 스타트 후 최단거리를 기동하여...