백준 16173, 16174번 - 점프왕 쩰리 (C++)

유형: 그래프, BFS

문제 Small: https://www.acmicpc.net/problem/16173

문제 Large: https://www.acmicpc.net/problem/16174

16174번: 점프왕 쩰리 (Large)

 

입출력 형식

main에서 입력을 받아오고, solution 함수에서 계산함.

이후 풀이는 solution 부분 코드만 올림.

#include "iostream"
#include "vector"
#include "queue"

using namespace std;

string solution(int n, vector<vector<int>> arr){
	// ...
    return "Hing"; // 도착 못하는 경우
}

int main(){
    int n; cin >> n;
    vector<vector<int>> arr(n);
    
    for(auto &now: arr){
        for(int i = 0; i < n; i++){
            int temp; cin >> temp;
            now.push_back(temp);
        }
    }
    
    cout << solution(n, arr);
    return 0;
}

 

Small 풀이

BFS를 사용하여, 위쪽/오른쪽에서 step 만큼 이동했을 때 유효하면 큐에 넣는다.

큐에서 꺼낸 원소중에 도착지점이 있으면 종료한다.

주의할 점은, step의 값이 0인 경우는 막다른 길이라는거. 이런 경우는 따로 예외처리를 해줘야 한다.

문제의 범위가 2~3이라, 효율성을 따지지 않아도 정답으로 처리된다.

이 코드를 Large 문제에 적용하면, 메모리 초과 판정을 받는다.

문제를 개선한 코드는 바로 아래 항목에 작성했다.

string solution(int n, vector<vector<int>> arr){
    queue<pair<int, int>> q;
    q.push(make_pair(0,0)); // 큐에 시작점 추가

    while (!q.empty()){
        // 큐에서 하나 꺼냄
        auto now = q.front(); q.pop();
        int x = now.first, y = now.second;
        int step = arr[x][y];

        if(step == -1) return "HaruHaru"; // 정답에 도달하면 끝!
        if(step == 0) continue; // 이동칸수가 0이면 그냥 넘긴다 (막다른거라)

        // 위쪽, 오른쪽 방향에서 가능한거 다 큐에 넣기
        if(x+step < n) q.push(make_pair(x+step, y));
        if(y+step < n) q.push(make_pair(x, y+step));
    }

    return "Hing"; // 도착 못하는 경우
}

 

Large 풀이

바로 위의 코드가 메모리 초과가 나오는 이유는, 큐에 중복되는 값이 들어오기 때문이다.

중복을 피하려면 방문 여부를 판단하는 과정이 필요하다. 이를 위해 visited 벡터를 새로 만들고 관련 코드를 추가했다.

방문처리는 큐에 파생 노드를 추가하는 시점에서 같이 해준다. 나이트의 이동 문제를 다시 생각해보자...

 

이렇게 방문처리를 적용하면, Small 코드에서 step이 0일 때 무한루프에 빠질 수 있는 문제도 해결된다.

Small 코드에선 따로 예외처리를 했지만, 이 코드에서는 파생 노드인 x+0과 y+0은 이미 방문한 것으로 되었기에,

step이 0인 노드를 만나면 큐에 파생노드를 넣는 일이 없어진다.

 

앞으로는 범위가 작은 그래프 문제라도 방문처리를 꼭 하는 습관을 들여야겠다.

중복을 피하려면 파생노드를 큐에 넣는 시점에 방문처리 한다. 이번에 배운 교훈이다. 중요해서 두번 씀.

string solution(int n, vector<vector<int>> arr){
    queue<pair<int, int>> q;
    q.push(make_pair(0,0)); // 큐에 시작점 추가

    vector<vector<bool>> visited(n); // 방문 여부 추가
    for(auto &now: visited){
        for(int i = 0; i < n; i++) now.push_back(false);
    }

    while (!q.empty()){
        // 큐에서 하나 꺼냄
        auto now = q.front(); q.pop();
        int x = now.first, y = now.second;
        int step = arr[x][y];

        if(step == -1) return "HaruHaru"; // 정답에 도달하면 끝!
        // if(step == 0) continue; // 방문여부를 따지기에 더는 필요없는 코드

        // 위쪽, 오른쪽 방향에서 가능한거 다 큐에 넣기
        if(x+step < n && !visited[x+step][y]) {
            q.push(make_pair(x+step, y));
            visited[x+step][y] = true;
        }
        if(y+step < n && !visited[x][y+step]) {
            q.push(make_pair(x, y+step));
            visited[x][y+step] = true;
        }
    }

    return "Hing"; // 도착 못하는 경우
}