코딩 챌린지 1일차 : 1326번 폴짝폴짝(S2)

1. 문제 탐색하기

N 징검다리의 개수
list[N] 징검다리
a, b 시작점, 목적지 (풀이에서는 리스트 index와의 일치를 위해 각각 -1 해줌)

• 예제 입력 1, 이해를 돕기 위해 depth 2까지 그림

시작점에 n이 쓰여있을 때,
... -2n, -n, n, 2n ... 만큼 점프하는 모든 경우를 고려
각 도착 위치에 m이 쓰여 있을 때,
다시 ... -2m, -m, m, 2m ... 만큼 점프하는 모든 경우를 고려
위치 == b를 만족할 때까지 계속 tree를 탐색

tree의 depth가 점프 횟수 (구하고자 하는 것)
가장 적은 depth를 가진 해를 구해야 하므로 BFS 사용

2. 코드 설계하기

1. input 받기
2. queue, visited, depth 변수 생성
3. BFS로 tree 탐색 : while문 사용
   • root = a
   • 종료 조건 : cur == b (해 O) 또는 queue가 비어 있음 (해 X)
   • 해가 아니면 queue에 추가

3. 시도 회차 수정 사항

1회차) 개구리가 앞으로만 갈 수 있다고 생각하고 반쪽짜리 프로그램 구현
반례가 도저히 나오지 않아 질문 게시판을 참고함

2회차) for문의 시작 조건만 변경하여 성공!
(cur + n칸 -> 0과 가장 가까운 이동 가능 위치)

4. 정답 코드

from collections import deque
import sys
input = sys.stdin.readline

# input
N = int(input())
stones = list(map(int, input().split()))
a, b = map(int, input().split())
a -= 1                      # index와 징검다리 번호 일치시킴
b -= 1

# 변수 설정
queue = deque([a])
depth = [0] * N
visited = [False] * N
visited[a] = True

# BFS
while queue:
    cur = queue.popleft()
    # index가 0 이상 N 미만인 동안 탐색
    for i in range (cur - (cur // stones[cur]) * stones[cur], N, stones[cur]):
        # 해가 아닐 때 큐에 추가
        if not visited[i]:
            queue.append(i)
            depth[i] = depth[cur] + 1
            visited[i] = True
        # 해일 때 depth 출력
        if i == b:
            print(depth[i])
            break
    else: continue          # 이중 반복문 탈출을 위함
    break
else: print(-1)

DFS/BFS 문제라고 알려주지 않았다면 한참 고민했을 것 같다. DFS만 선호하던 내가 BFS와 친해지고 deque 라이브러리도 써보는 계기가 되는 문제였다. 오랜만에 키보드 잡으니까 재밌네 :D

5. 해설지 참고 후

• visited와 depth를 각각 만들 필요 없이 초기값이 -1인 하나의 정수 리스트로도 해결이 가능한 문제였음
• break문 대신 함수의 return을 사용하면 코드 흐름이 더 매끄러울 것 같음.
• if i == b문은 if not visited문 내에 있어야 함. BFS의 특성상 이미 visited된 해가 가장 먼저 나올 수 없어서 오답은 아니었던 것. (첫번째 이미지의 노란색 노드 참고)

멘토님과 알고리즘의 상당 부분이 비슷해서 맞게 풀었다는 생각에 뿌듯했다.
아직 템플릿 쓰는 것은 어려워서 익일 해설지를 많이 참고해야겠다.