티스토리 뷰
반응형
📎 간략한 문제 정리
- 시작점 (0, 0)에서 도착점 (n-1, m-1)에 도착하기까지 최단거리를 구하고, 도착이 불가능할 경우 -1을 출력하는 메소드를 구현합니다.
📈 문제 분석
- 최단거리를 찾는 문제는 전형적인 BFS 문제로 BFS를 구현하며 도착점에 도착하면 그때까지의 depth를 출력하면 됩니다.
🙋♂️ 내가 처음 생각한 해결 방법
- 이 문제는 최단거리이기 때문에 BFS가 더 적합해보이지만 DFS로도 한번 같이 구현해보았습니다.
💻 풀이한 코드
# BFS
def solution_bfs(maps):
from collections import deque
n, m = len(maps), len(maps[0])
visited = [[-1 for _ in range(m)] for _ in range(n)]
visiting = deque([(0, 0)])
visited[0][0] = 1
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
while visiting:
x, y = visiting.popleft()
for i in range(4):
xx, yy = x + dx[i], y + dy[i]
if 0 <= xx < n and 0 <= yy < m and maps[xx][yy] == 1 and visited[xx][yy] == -1:
visited[xx][yy] = visited[x][y] + 1
visiting.append((xx, yy))
return visited[n-1][m-1]
# DFS
def solution_dfs(maps):
from sys import setrecursionlimit
setrecursionlimit(10**9)
n, m = len(maps), len(maps[0])
visited = [[10001 for _ in range(m)] for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
def dfs(x, y, depth):
visited[x][y] = depth
for i in range(4):
xx, yy = x + dx[i], y + dy[i]
if 0 <= xx < n and 0 <= yy < m and maps[xx][yy] == 1 and visited[xx][yy] > depth+1:
dfs(xx, yy, depth+1)
dfs(0, 0, 1)
if visited[n-1][m-1] == 10001:
return -1
return visited[n-1][m-1]
📝 해결 과정에서 만난 문제, 고민들
- BFS는 반복문을 통해 구현하고 DFS는 재귀를 통해 구현했습니다. 최단거리를 구하는 문제인만큼 당연히 BFS가 효율적이어서 정확성과 효율성 모두 통과했지만 DFS는 최단거리를 체크하기위해 모든 가능성을 탐색하므로 map의 크기가 커질수록 탐색의 경우가 많아져 정확성은 통과하여도 효율성은 통과하지 못했습니다. 특이한 점은 정확성 테스트 케이스 20번의 경우 오히려 DFS가 더 빨랐다는 점입니다. 0.01ms와 0.02ms이므로 오차 가능 범위이지만 무조건 BFS가 빠르지 않다는 점은 확인 가능했습니다. 메모리의 경우도 거의 차이가 없었습니다. 문제와는 상관없이 구현력을 높이기 위한 연습으로 두 방식으로 작성했습니다.
https://programmers.co.kr/learn/courses/30/lessons/1844?language=python3
반응형
'알고리즘 학습 > 프로그래머스' 카테고리의 다른 글
[Programmers] - 순위 (그래프) with Python (0) | 2021.04.22 |
---|---|
[Programmers] - 방문 길이 (Summer/Winter Coding(~2018)) with Python (0) | 2021.04.21 |
프로그래머스 - 올바른 괄호의 갯수 (level 4 연습문제) [Python] (0) | 2021.01.12 |
프로그래머스 - 이중우선순위큐 (Heap) [Python] (0) | 2021.01.12 |
프로그래머스 - 점프와 순간 이동 (Summer/Winter Coding(~2018)) [Python] (0) | 2021.01.10 |
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 토마토#백준알고리즘#Python
- 반복수열#백준알고리즘#Python
- 병든 나이트#BOJ#탐욕법#Python
- 배열합치기#분할정복#BOJ#Python
- Brackets#Stacks and Queues#Codility#Python
- N으로 표현#DP#Programmers#Python
- 백준 알고리즘#BackTracking
- 나무자르기#BOJ#이분탐색#Python
- 미로 탐색#백준알고리즘#Python
- 리모컨#완전탐색#BOJ#Python
- django
- 섬의개수#백준알고리즘#Python
- NumberofDiscIntersections#Codility#Sort#Python
- API#lazy#
- 종이자르기#분할정복#BOJ#Python
- 파이썬알고리즘인터뷰#4장
- 랜선자르기#이분탐색#BOJ#Python
- Triangle#Sorting#Codility#Python
- 암호코드#dp#BOJ#Python
- 쿼드트리#BOJ#분할정복#Python
- 터틀비치#리콘#xbox#controller
- 날짜 계산#BOJ#완전탐색#Python
- django#slicing
- Distinct#Codility#Python
- 공유기 설치#BOJ#이분탐색#Python
- PassingCars#Codility#Python
- 순열사이클#BOJ#Python
- 텀 프로젝트#백준알고리즘#Python
- Swift#Tuples#Range
- filter#isalnum#lower
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함