https://www.acmicpc.net/problem/12851
공부 날짜 : 2023.02.07
정답 참조 여부 : X
1차원 직선상에서 현재 위치와 목적 위치가 주어지고 현재위치에서 +1, -1 *2의 위치로 이동 가능할 때 목적위치까지 도달하는 최단거리와, 최단거리의 개수를 구하는 문제이다.
보자마자 BFS가 떠올랐다.
BFS의 정확한 개념을 모르긴 했지만, 가중치가 없는 노드상에서 최단거리를 구하는 알고리즘이라고 들었다. 면접대비해서 BFS를 정확하게 설명할 수 있어야겠지만 그건 추후 공부하도록 하겠다.
현재 위치에서 이동가능한 위치를 모두 추가하고 이동한 위치에서 다시 이동가능한 위치를 반복하여 탐색하면 구할수 있을거라 생각했다.
하지만 BFS를 구현하는데 아직 익숙하지 않아 메모리 초과가 발생했는데, 바로 방문한 노드를 체크하지 않은 것이였다.
또 방문노드를 체크할 때, 방문이후(pop했을 때)가 아닌 방문예정(append)일때 추가해주는 바람에 틀렸습니다가 나왔다.
겪은 문제 모두 아직 BFS를 구현하는데 익숙하지 않아 생긴 문제라 생각하고 비슷한 문제를 많이 풀어봐야겠다.
소스코드
import sys
input = sys.stdin.readline
from collections import deque
#############################################
n, k = map(int, input().split())
# 시작점과 거리를 초기값으로 저장
visit = deque()
visit.append((n, 0))
# 방문 여부를 판단하는 배열
visited = [False for _ in range(100001)]
visited[n] = True
# 정답이 저장될 두 변수
ans_dis = 100001
ans_count = 0
# 다음 탐색한 장소가 있을 때 순환
while visit:
x, dis = visit.popleft()
# 현재 위치 방문 처리
visited[x] = True
# 최단거리 이상의 거리는 탐색할 필요 없으므로 반복 중단
if ans_dis < dis:
break
# 목적지 탐색시 거리와 개수 +1
if x == k:
ans_dis = dis
ans_count += 1
if ans_dis == dis:
continue
# 현재 장소에서 이동가능하고, 이전에 방문하지 않은 모든 칸 추가
if 0 <= x+1 <= 100000 and not visited[x+1]:
visit.append((x+1, dis+1))
if 0 <= x-1 <= 100000 and not visited[x-1]:
visit.append((x-1, dis+1))
if x < k and 0 <= x*2 <= 100000 and not visited[x*2]:
visit.append((x*2, dis+1))
print(ans_dis)
print(ans_count)
