🧐 문제 설명
😍 나의 풀이
문제를 읽어보면 너비우선탐색 BFS로 풀이하면 쉽게 할 수 있겠다는 생각이 들었다. 깊이우선탐색 DFS로 푼다면 연산이 -1, +1, *2 로 나뉘어져 있기 때문에 도착 지점에 도달할 수 없는 경우에 무한 루프에 빠질 수 있기 때문에 사용하기 힘들 것 같았다.
그런데 문제를 풀이하다가 3가지 문제점을 만나게 되었다.
1. 메모리 초과 문제
처음에는 BFS로 만나는 모든 경로들을 차곡차곡 리스트에 저장하면서 도착 지점이 나올때까지 너비우선탐색을 했다. 그런데, 그러다보니 방문했던 곳을 다시 방문해도 리스트에 다시 저장하다보니 무한하게 메모리가 늘어나는 문제가 발생했다.
→ 요소를 False로 하는 visited 리스트를 만들어두고 방문한 곳이면 True로 방문처리를 하여 탐색의 경우를 줄였다.
2. Index Error 문제
조건에서, 지점의 범위가 0<=location<=100000 이었기 때문에 이 부분을 고려해야만 했다.
if (visited[location-1] == False) and (location-1<100000):방식으로 처음에 코드를 짰는데, 이 경우 and 앞에 있는 visited[location-1] == False 를 먼저 체크하게 되는데, 이렇게 되면 visited의 인덱스가 초과해버리면 인덱스 에러가 발생하는 문제가 생겼다.
→ if 조건식에 지점의 범위를 먼저 체크하고 방문 했는지 아닌지 체크했다. 또, -1 연산이 있기 때문에 지점이 0보다 작아지는 경우도 고려했다.
if (0 <= location - 1 <= 100000) and
(visited[location - 1] == False):3. BFS 문제이지만, 깊이를 고려해야 하는 문제
BFS 문제이지만 예를 들어, 5-10-9-18-17 으로 도착한다고 하면 최단 경로의 횟수인 4의 값(깊이)을 출력해야하므로 깊이를 count해야 했다. 이 깊이를 확인하려면 같은 깊이의 노드들은 모두 탐색이 된 후에 count가 +1 되어야 한다.
→ 처음부터 덱에 [지점, 깊이]의 형태로 리스트에 저장하고 깊이만 출력했다.
from collections import deque
def bfs(start, end, visited):
q = deque([[start, 0]]) # [초기 지점, 깊이 0] 큐 생성
visited[start] = True
while q:
this = q.popleft()
location = this[0]
d = this[1]
if location == end: # 현재 노드=도착점이 되면 도착 판단
break
else:
if (0 <= location - 1 <= 100000) and (visited[location - 1] == False):
visited[location - 1] = True # 방문 처리
q.append([location - 1, d + 1])
if (0 <= location + 1 <= 100000) and (visited[location + 1] == False):
visited[location + 1] = True
q.append([location + 1, d + 1])
if (0 <= location * 2 <= 100000) and (visited[location * 2] == False):
visited[location * 2] = True
q.append([location * 2, d + 1])
return d
start, end = map(int, input().split())
visited = [False] * 100001
print(bfs(start, end, visited))🥇 Today I Learn
간단해보이는 BFS 문제이지만, 생각보다 많은 함정?이 있어서 배운 게 상당히 많은 알고리즘 문제였다.
특히 BFS 문제이지만 깊이를 어떻게 체크해서 최단 경로를 구해줄 지 생각하는 것이 헷갈리는 부분이었다.
