[백준/Baekjoon] 11060 점프 점프 C++/Python :: BFS

https://www.acmicpc.net/problem/11060

11060번: 점프 점프

---

1. Logic

기본적인 BFS문제이다. 처음 방문하는게 가장 최단거리기 때문에 vis배열을 통해 queue에 들어가는 갯수를 줄여주면서 BFS를 진행하면 된다.

---

2. Code

c++

#include<bits/stdc++.h>

using namespace std;

int n;

int arr[1001];
bool vis[1001];

int bfs() {
    queue<pair<int, int>> q;
    int ans = 0x3f3f3f3f;
    
    q.push({0, 0});
    vis[0] = true;
    
    while(!q.empty()) {
        int cur = q.front().first;
        int cnt = q.front().second;
        
        q.pop();
        
        if(cur == n-1) {
            return cnt;
        }
        
        for(int i = 1; i <= arr[cur]; i++) {
            int next = cur + i;
            
            if(vis[next]) continue;
            
            if(next < n) {
                q.push({next, cnt+1});
                vis[next] = true;
            }
        }
    }
    
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    cout << bfs();
}

Python

from collections import deque
import sys

def solve(arr):
    n = len(arr)
    vis = [False]*n
    q = deque()
    q.append((0, 0))
    vis[0] = True
    
    while q:
        cur, cnt = q.popleft()
        
        if cur == n-1:
            return cnt
        
        for i in range(1, arr[cur]+1):
            if cur+i >= n:
                continue
            if vis[cur+i]:
                continue
            q.append((cur+i, cnt+1))
            vis[cur+i] = True
    return -1


n = int(input())
arr = list(map(int, input().split()))

print(solve(arr))

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐