❓ Question
📖 Before Start
BFS 탐색을 사용하여 1차원 배열을 순회하는 문제다.
이번 문제는 BFS를 활용하여 1차원 배열 내부를 순회하는 문제였다.
최근 2달 간의 휴식으로 감이 많이 무뎌졌기에, 스스로 많이 반성하는 시간을 가졌다.
✒️ Design Algorithm
그리디 알고리즘을 사용하여 최적의 결과를 유도하는게 맞다고 생각했다.
0부터 100,000 까지 존재하는 1차원 공간 내부에 점 N 과 K 가 있다.
수빈이가 위치한 N 좌표에서 동생이 위치한 좌표 K 까지 이동을 해야 하는데,
총 세 가지 방식 (N - 1, N + 1, N * 2) 으로 좌표 이동이 가능하다고 한다.
위 세 가지 방식은 공평하게 1초라는 시간이 소요되며, 가장 적은 시간을 투자하여
동생이 위치한 좌표로 이동하는 경우를 구해야 했는데... 결국 방법을 떠올리지 못했다.
💻 Making Own Code
✅ Correct Code
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
visited = [0] * 100001
def bfs(start):
queue = deque([start])
while queue:
current = queue.popleft()
if current == K:
return visited[K]
# 현재 좌표의 -1, +1, x2 만큼 위치한 좌표들을 대상으로 탐색.
for loc in [current - 1, current + 1, current * 2]:
# 해당 좌표가 유효 범위 안에 있으면서, 미방문된 상태인지 체크.
if 0 <= loc <= 100000 and not visited[loc]:
visited[loc] = visited[current] + 1
queue.append(loc)
print(bfs(N))그간 2차원 배열을 대상으로 그래프 탐색을 진행했는데, 1차원 배열 도 가능하다!
결국 이 문제는 방문 가능한 모든 좌표를 BFS 탐색으로 일일히 방문함으로서 해결이 가능했다.
처음에는 최적의 결과만을 찾으려다 보니 가설에 오류가 많았고, 결국 다른 분의 해설을 참고했다.
하지만 해설을 보니 내가 너무 어렵게만 문제를 바라보았다는 생각이 퍼뜩 들었다. 허탈 그 자체
이 문제에서 가장 놀라웠던 것은, 다음 좌표를 탐색하는 과정에서 사용된 for - in 문이었다.
2차원 배열에서는 방향에 따른 벡터를 만들어 이를 적용했는데, 여기서도 비슷한 원리를 사용했다.
# 현재 좌표의 -1, +1, x2 만큼 위치한 좌표들을 대상으로 탐색.
for loc in [current - 1, current + 1, current * 2]:
# 해당 좌표가 유효 범위 안에 있으면서, 미방문된 상태인지 체크.
if 0 <= loc <= 100000 and not visited[loc]:
visited[loc] = visited[current] + 1
queue.append(loc)수빈이가 이동 가능한 방식에 따라 현재 좌표를 기준으로 다음 좌표 값들을 구해 List 에 넣고,
이를 순차적으로 반복시킨 후 유효한 좌표인지, 아직 방문하지 않았는지를 체크하는 방식이었다.
이렇게 되면 visited 변수에는 좌표 별로 이동에 소요되는 최단 시간이 저장되고, 이 중에서
우리가 원하는 값인 K 좌표에 대한 값을 추출하여 결과로 출력시키면 끝난다.
이번 문제는 내 힘으로 푼 문제가 아니기 때문에, 관련된 문제를 여러 개 풀어보면서 유형을 익히려 한다.
2달 간 개발을 아예 놓았더니 정말 감이 많이 무뎌졌다. 다른 공부들도 오늘부터 재개를 해야겠다.
📖 Conclusion
📒 github Code link
