문제

문제 링크 : https://www.acmicpc.net/problem/16928 (단계별로 풀어보기 : 그래프와 순회)

문제 풀이

해당 문제를 단계별로 풀기로 접근한게 아니라 다른 경로로 그냥 처음 접했으면 dp로 풀지 bfs로 풀지 고민했을 것같다. 하지만 dp로 푼다면 다시 내려가는 뱀때문에 아주 복잡해질 것 같다. 나는 그래프 문제를 풀고 있었기 때문에 바로 bfs를 생각하여 풀었다. 30분만에 알고리즘 스케치와 구현을 마쳤지만 처음에는 100초과 인덱스 초과 문제로 런타임 에러가 발생했고, 해당 부분을 수정하여 제출하니 틀렸다.. 예외를 생각하는데가 한참 걸렸다. 내가 틀린부분은 방문한 노드는 방문안하도록 구현한 부분이었다. 사다리와 뱀이 있기 때문에 기본적인 bfs 처럼 방문한 노드라고 방문하지 않는게 아니라 방문하였더라도 그보다 적은 횟수로 해당 노드를 방문할 수 있으면 방문하여 visited값을 초기화 해주어야 한다. 그래야 최단횟수를 확보할 수 있다. 이 부분을 고치니 문제를 맞을 수 있었다.
일단 기본 bfs알고리즘을 사용하고 해당 노드가 뱀이나 사다리가 있는 경우와 아무것도 없는 경우를 나누어서 생각한다. 해당 노드에 뱀이나 사다리가 있다면 그곳으로 이동하도록 구현하고 (이때는 주사위횟수(=visited)값은 증가하지않는다) 뱀이나 사다리가 없으면 주사위 수만큼(1~6)만큼 이동가능하도록 구현한다. 또한 방문한 노드도 방문주사위횟수가 적어지는 경우는 방문하도록 한다. 그리고 큐에서 꺼낸 값이 100일때 종료되도록 구현한다. 나는 초기값을 1로 잡아 마지막에 출력값에 -1을 해주었다.
문제를 풀고나니 큐에서 꺼낸 값이 100일 때 종료되도록 구현했는데 이부분도 케이스가 크면 처음 100에 방문했을때보다 값이 적어질 수 도 있어 오류가 생길 수 있을것 같다. 따라서 그냥 bfs를 전체 다 돌린 다음 visited[100]값을 출력하는것이 더 안전해보인다.(이 때 그래프 사이즈 수정해야함) 대신 수정하면 bfs가 모두 돌고 끝나기 때문에 시간은 증가한다. 해당 문제에서는 아래 코드로도 통과되었다.

알고리즘 스케치

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector <vector<int>> graph;
vector <int> visited;
int N, M;
queue <int> que;

void input();
void bfs(int n);
void sol();

int main()
{   
    fastio;
    input();
    sol();
    return 0;
}

void input()
{
    cin >> N >> M;
    graph.resize(100);
    visited.resize(101);
    int x, y;
    for(int i=0; i<N; i++){
        cin >> x >> y;
        graph[x].push_back(y);
    }
    for(int i=0; i<M; i++){
        cin >> x >> y;
        graph[x].push_back(y);
    }
}

void bfs(int n)
{
    int u;
    visited[n] = 1; //처음 1의 최소1번이라 가정하고 결과값에서 -1 해주어야함.
    que.push(n);
    while(que.size()!=0){
        u = que.front();
        if(u == 100)  break;  // 이 부분을 빼주어야 더 안전할 것 같다. 이 부분 뺄시 graph size 101로	
        que.pop();
        if(graph[u].size()){
            if(visited[graph[u][0]]==0 || visited[graph[u][0]]>visited[u]){
                visited[graph[u][0]] = visited[u];  //x번 칸에 도착하면, y번 칸으로 이동. 이동횟수 증가x.
                que.push(graph[u][0]);
            }         
        }
        else{
            for(int i=1; i<=6; i++){
                if(u+i<=100 && (visited[u+i]==0 || visited[u+i]>visited[u])){
                    visited[u+i] = visited[u] + 1;
                    que.push(u+i);
                }
            }
        }
    }
}

void sol()
{
    bfs(1);
    printf("%d\n", visited[100] - 1);   //처음 시작값을 1로 가정했으니 결과값에 -1.
}