Lee's Programming Practice

알고리즘 문제 풀이

문제

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

풀이

언뜻 보기에 DP문제로 보여 DP로 문제해결을 하려했으나, DP로 문제풀이를 했을 경우 예외 및 오류가 많아 BFS 방식으로 재풀이하였다.

소스 코드

#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <cctype>
#include <set>
#include <string.h>

using namespace std;

queue<int> q;
int arr[101];
int dist[101];
bool visited[101];

void BFS(int num) {
	dist[num] = 0;
	visited[num] = true;
	q.push(num);

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		
		for (int i = 1; i <= 6; i++) {
			int y = x + i;

			if (y > 100)
				continue;
			if(arr[y] != 0)
				y = arr[y];

			if (!visited[y]) {
				dist[y] = dist[x] + 1;
				q.push(y);
				visited[y] = true;
			}
		}
	}
}

int main() { 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;

	memset(arr, 0, sizeof(arr));

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		arr[x] = y;
	}

	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		arr[x] = y;
	}

	BFS(1);

	cout << dist[100] << '\n';

	return 0;
}