취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13903번 문제인 출근이다.
문제는 아래 링크를 확인하자.

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

주어진 세로블록들을 노드로, 각 블록에서 이동할 수 있는 블록으로의 이동을 에지로 나타내 문제의 상황을 그래프로 모델링할 수 있다. 위 모델을 이용하면, 주어진 문제는 첫 행의 세로블록들을 출발점들로, 마지막 행의 세로블록들을 도착점들로 생각하는 최단거리 문제로 생각할 수 있다.

각 에지의 가중치가 일정하므로 BFS를 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int R, C;
int board[1000][1000];
int dist[1000][1000];

int cnt;
int dr[10], dc[10];

void bfs() {
	queue<pair<int, int>> que;
	for (int c = 0; c < C; c++) {
		if (board[0][c]) dist[0][c] = 1, que.push(make_pair(0, c));
	}

	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < cnt; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (-1 < rr && rr < R && -1 < cc && cc < C && board[rr][cc] && dist[rr][cc] == 0) {
				dist[rr][cc] = dist[r][c] + 1;
				que.push(make_pair(rr, cc));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) cin >> board[r][c];
	}

	cin >> cnt;
	for (int i = 0; i < cnt; i++) cin >> dr[i] >> dc[i];

	bfs();

	int ans = 1000000007;
	for (int c = 0; c < C; c++) {
		if (dist[R - 1][c]) ans = min(ans, dist[R - 1][c]);
	}

	if (ans == 1000000007) cout << -1;
	else cout << ans - 1;
}