[C++] 백준 1600번: 말이 되고픈 원숭이 (BFS)

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

---

문제 이해하기

문제의 요구사항은 다음과 같습니다.

원숭이가 말처럼 이동할 수 있는 횟수가 정해져 있을 때, 원숭이 동작수의 최솟값을 구하여라.

---

시간복잡도 어림하기

BFS 알고리즘

 가중치가 같은 최단거리 문제이므로 BFS를 사용할 수 있습니다. 또한, 이번 문제는 시작 위치가 하나로 고정되어 있으므로 BFS를 한 번만 시행해도 됩니다. 일반적인 BFS 알고리즘의 시간복잡도는 O(N^2)입니다. 이번 문제에서는 가로와 세로의 길이가 주어지므로 200 x 200 = 40,000입니다.

 이 문제에서는 고려해야할 것이 하나 더 있는데, 바로 말처럼 이동할 수 있는 횟수입니다. 각 위치마다 말처럼 이동할 수 있는 횟수를 저장한다고 해봅시다. 말처럼 이동 가능한 횟수가 최대 30이므로 전체 시간복잡도는 200 x 200 x 30 = 1,200,000입니다. 따라서 제한 시간 내에 문제를 해결할 수 있습니다.3

 

---

알고리즘 설계하기

 일반적으로는 탐색한 위치에 대해 방문처리를 진행합니다. 이번 문제에서는 말처럼 이동 가능한 횟수도 있으므로 탐색 위치 + 말처럼 이동가능 횟수를 기준으로 방문처리를 진행합니다. 따라서 방문처리 배열은 3차원 배열이 될 것입니다.

 

 일반적인 BFS의 구조는 다음과 같습니다.

visited[시작위치]; q.push({시작위치});
whlie(!q.empty()){
    q의 가장 앞 원소 가져오기
    for(int i = 0; i < 4; i++) //4방향 탐색
        int ny, nx = 다음 위치 계산;
        if(다음 위치 유효성 검사) continue;
        visited[다음위치], q.push({다음위치});
}

 위 코드에서는 한 위치에 대해 4방향을 탐색합니다. 말처럼 이동 가능한 경우에는 8방향까지 이동할 수 있으므로 방향 배열을 두 종류를 만들어야 합니다.

 

 말처럼 이동 가능한 경우는 항상 있는 것이 아니므로 말처럼 이동 가능한 횟수가 0보다 큰 경우에만 수행해야 합니다. 따라서 다음과 같은 구조가 될 것입니다.

visited[시작위치]; q.push({시작위치});
whlie(!q.empty()){
    (x, y) = q의 가장 앞 원소 가져오기
    cnt = q의 가장 앞 원소의 말처럼 이동 가능한 횟수 가져오기
    if(cnt > 0){
        for(int i = 0; i < 8; i++){ //8방향 탐색
            //다음 위치 이동 로직
        }
    }
    for(int i = 0; i < 4; i++){ //4방향 탐색
        //다음 위치 이동 로직
    }
}

 이때, 4방향 탐색을 항상 진행하는 이유는 한 칸 이동은 횟수와 상관없이 항상 가능하기 때문입니다.

 

 최단거리 계산은 어떻게 할 수 있을까요? 일반적인 BFS 문제와 같이 visited 배열을 사용하면 됩니다.

//일반적인 최단거리 계산 코드
visited[ny][nx] = visited[y][x] + 1;

//8방향 이동시 최단거리 계산
visited[ny][nx][cnt - 1] = visited[y][x][cnt] + 1;

//4방향 이동시 최단거리 계산
visited[ny][nx][cnt] = vistied[y][x][cnt] + 1;

 가장 위는 일반적인 BFS의 최단거리 계산입니다. 현재 방문 값에 1을 더해 다음 위치까지의 거리를 구합니다.

 

 이번 문제에서는 말처럼 이동 가능한 횟수가 있으므로 배열에 값을 하나더 추가합니다. 이때, 8방향 이동 시에는 이동 가능 횟수를 하나 소진하므로 cnt - 1를 진행하고 그렇지 않은 경우에는 cnt 값을 유지합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<cstring>
#include<queue>
#include<tuple>
using namespace std;

int k, n, m, a[204][204], visited[204][204][34], ret = 1e9;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int dy2[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dx2[] = {-2, -1, 1, 2, 2, 1, -1, -2};
queue<pair<pair<int, int>, int>> q;
int main(){
    cin >> k >> m >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) cin >> a[i][j];
    }
    q.push({{0, 0}, k}); visited[0][0][k] = 1;
    int y, x, cnt;
    while(!q.empty()){
        tie(y, x) = q.front().first;
        cnt = q.front().second;
        q.pop();
        if(cnt > 0){
            for(int i = 0; i < 8; i++){
                int ny = y + dy2[i];
                int nx = x + dx2[i];
                if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                if(a[ny][nx] == 1 || visited[ny][nx][cnt - 1]) continue;
                visited[ny][nx][cnt - 1] = visited[y][x][cnt] + 1;
                q.push({{ny, nx}, cnt - 1});
            }
        }
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if(a[ny][nx] == 1 || visited[ny][nx][cnt]) continue;
            visited[ny][nx][cnt] = visited[y][x][cnt] + 1;
            q.push({{ny, nx}, cnt});
        }
    }
    
    for(int i = 0; i <= k; i++){
        if(visited[n - 1][m - 1][i])
            ret = min(ret, visited[n - 1][m - 1][i]);
    }
    cout << (ret == 1e9 ? -1 : ret - 1);
    return 0;
}

 BFS 로직은 위에서 본것과 동일합니다. 주의해야할 부분은 목표 지점까지의 최단거리를 구하는 부분입니다. 위 코드를 보면 0부터 k까지 목표 위치의 방문값을 확인하며 최단거리를 갱신합니다. 이와 같이 가능한 모든 cnt에 대해 탐색을 진행하는 이유는 경로에 따라 목표지점에서 cnt 값이 다를 수 있기 때문입니다.

 따라서 해당 위치의 모든 방문 값을 확인하여 최단거리를 구해야 합니다.

---