BFS 기본적인 문제 다시 한번 더 연습.!
출처 : https://programmers.co.kr/learn/courses/30/lessons/1844
알고리즘
간단한BFS 문제이다. 시작점 (0, 0)에서 시작하여 한 칸씩 직접 탐사하되,
(N, M)에 닿았을 경우 (닿지 않았을 수 있으므로) 닿았을때의 거리를 별도의 리스트에 저장시킨다.
별도의 리스트가 비어있다면, -1을 return 그렇지 않다면 최솟값을 return 시켜주자.
코드
from collections import deque
def bfs(x, y, maps):
queue = deque()
answer_list = set()
queue.append((0, 0))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= len(maps) or ny >= len(maps[0]):
continue
elif maps[nx][ny] == 0:
continue
elif maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1
if nx == len(maps)-1 and ny == len(maps[0])-1:
answer_list.add(maps[nx][ny])
queue.append((nx, ny))
return answer_list
def solution(maps):
answer = bfs(0, 0, maps)
if len(answer) == 0:
return -1
else:
return min(answer)
answer_list에 데이터를 넣는 과정에서 set을 활용하여 복잡도상의 이득을 취하였다.
'알고리즘 & PS' 카테고리의 다른 글
[Python] 프로그래머스 Lv 4 - 올바른 괄호의 개수 (0) | 2021.04.27 |
---|---|
[Python] 2018 Kakao Blind Recruitment [3차] n진수 게임 (0) | 2021.04.26 |
[Python] 프로그래머스 Lv 4 - 버스여행 (0) | 2021.04.25 |
[Python] 프로그래머스 Lv 3 - 자물쇠와 열쇠(2020 카카오 코테 기출) (0) | 2021.04.24 |
[Python] 프로그래머스 Lv 2 - 최대 용량이 정해진 FIFO 큐 클래스 (0) | 2021.04.24 |