※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 1326번 문제인 폴짝폴짝이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/1326
1326번: 폴짝폴짝
첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번
www.acmicpc.net
문제에서 주어진 상황은 각 배열의 칸을 노드로, 각 배열의 칸에서 이동할 수 있는 (그 칸에 적힌 수의 배수만큼 떨어져있는 다른) 칸의 관계를 방향이 있는 에지로 하는 그래프로 모델링할 수 있다.
위에서 설계한 모델 위에서 BFS를 이용하면 출발지점에서 도착지점까지의 최단거리를 빠르게 구해낼 수 있다.
도달할 수 없는 점은 -1을 출력해줘야 함에 유의하자.
아래는 제출한 소스코드이다.
728x90
'BOJ' 카테고리의 다른 글
| [BOJ 2527 // C++] 직사각형 (0) | 2023.02.22 |
|---|---|
| [BOJ 1105 // C++] 팔 (0) | 2023.02.22 |
| [BOJ 2531 // C++] 회전 초밥 (0) | 2023.02.22 |
| [BOJ 11637 // C++] 인기 투표 (0) | 2023.02.21 |
| [BOJ 9693 // C++] 시파르 (0) | 2023.02.21 |