[백준] 점프 점프 11060

 

1. 문제 링크

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

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

10
1 2 0 1 3 2 1 5 4 2

정답 : 5

2. 코드

let N = Int(readLine()!)!
let maze = readLine()!.split(separator: " ").map{ Int($0)! } // 1xN 미로 만들기
var visited = Array(repeating: false, count: N)

if N == 1{		// 1x1일시 0을 출력
    print(0)
}else{
    print(bfs())	// 탐색후 출력값 반환
}

func bfs() -> Int {
    var queue = [(0,0)]		// 미로의 가장 왼쪽에서 시작
    visited[0] = true
    while !queue.isEmpty{		
        let current = queue.removeFirst()
        let idx = current.0	// 세팅되어 있는 maze 값을 찾기 위한 idx 계속 증가되어야 함 -> 오른쪽으로 점프해야 하기 때문
        let count = current.1	// 점프 횟수 측정

        for i in 0...maze[idx]{	// 미로 안에 0의 값이 들어있을 수 있기 때문에 0부터 maze[idx] 포함한 점프하기
            if N-1 == i+idx{	// i+idx는 계속 증가하다 N-1을 만나게 된다면 가장 오른쪽에 도달했다는 뜻
                return count + 1// 마지막 증가하기
            }
            if !visited[i+idx] && i+idx < N{// 방문하지 않았고, 인덱스가 배열 범위 안에 해당하면
                if maze[i+idx] == 0{// 미로 안에 0이 있다면 무시하고 넘기기 0은 오른쪽으로 나아갈 수 없음
                    continue
                }else{
                    visited[i+idx] = true	// 방문처리
                    queue.append((i+idx,count+1))// 큐에 증가한 인덱스, 점프 증가 횟수 넣기
                }
            }
            
        }
    }	
    return -1		// 20번 줄에서 오른쪽에 도달하지 못하였을때 -1을 반환
}

3. 코드 설명

BFS문제 형식처럼 풀다가 중간에 배열 인덱스를 이용하여 오른쪽으로 증가하는 부분만 조심하면 될 거 같습니다.?

( 주석에 제가 생각하는 코드 이유를 적어뒀...)

 

4. 후기

기존에 BFS문제를 날로 먹고 풀었지만 이번엔 배열 인덱스 이용해서? 쉽지 않았다 많이 헷갈리고 머릿속에 꼬였음