프로그래머스 BFS/DFS 문제입니다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/1844
[나의 풀이]
def solution(maps):
from collections import deque
# answer = 0
# x,y,이동
queue = deque([[0,0,1]])
# n X m 크기
n = len(maps)
m = len(maps[0])
visited = [[False]*m for _ in range(n)]
visited[0][0] = True
# 상우하좌
dx = [-1,0,1,0]
dy = [0,1,0,-1]
answer_list = []
while queue:
x,y,answer = queue.popleft()
for i in range(4):
newX = x + dx[i]
newY = y + dy[i]
if newX >=0 and newX < n and newY >= 0 and newY < m:
if maps[newX][newY] == 1:
if not visited[newX][newY]:
queue.append([newX,newY,answer+1])
visited[newX][newY] = True
if x == n-1 and y == m-1:
answer_list.append(answer)
if len(answer_list) == 0:
return -1
return answer
자주 풀어왔던 BFS/DFS 활용 최단 루트 찾기 문제입니다. deque()의 popleft() 함수를 사용하여 BFS 구조로 해결하였습니다.🐻❄️🐻❄️🐻❄️
[다른 사람의 풀이]
from collections import deque
def solution(maps):
x_move = [1, 0, -1, 0]
y_move = [0, 1, 0, -1]
x_h, y_h = (len(maps[0]), len(maps))
queue = deque([(0, 0, 1)])
while queue:
x, y, d = queue.popleft()
for i in range(4):
nx = x + x_move[i]
ny = y + y_move[i]
if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
maps[ny][nx] = d + 1
if nx == x_h - 1 and ny == y_h - 1:
return d + 1
queue.append((nx, ny, d + 1))
return -1
비슷한 다른 풀이로서 visted 리스트를 만들지 않고 지나온 지점마다 +1해주어 다음 위치가 1이 아닌지역일 때 이동하는 방식이었습니다.🐷🐷🐷
감사합니다.