[백준/C++] 13903 출근

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

코드

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

#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
#define MAX 1001
typedef pair<int, int> pi;
int r, c, arr[MAX][MAX], n, ans = INT_MAX, dx[11], dy[11];
bool visit[MAX][MAX];
queue<pair<pi, int>> q;

void bfs() {
	while (!q.empty()) {
		int nx = q.front().first.first;
		int ny = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (nx == r - 1) {
			ans = min(ans, cnt);
			return;
		}

		for (int i = 0; i < n; i++){
			int gx = nx + dx[i];
			int gy = ny + dy[i];

			if (gx >= 0 && gx < r && gy >= 0 && gy < c && !visit[gx][gy] && arr[gx][gy]) {
				q.push({ { gx, gy } , cnt + 1});
				visit[gx][gy] = true;
			}
		}
	}
}

int main() {
	FASTIO;
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> arr[i][j];
			if (i == 0 && arr[i][j] == 1) {
				q.push({ { 0, j }, 0 });
				visit[0][j] = true;
			}
		}
	}

	cin >> n;
	for (int i = 0, a, b; i < n; i++)
		cin >> dx[i] >> dy[i];

	bfs();

	if (ans == INT_MAX) cout << -1;
	else cout << ans;
	return 0;
}

 

설명

첫 번째 행에서 출발해 마지막 행에 도착 가능한지 보면 됩니다.
이를 위해 주어지는 이동 규칙을 이용해 bfs를 돌립니다.


마지막에 ans값이 초기 설정한 값이라면 도착 불가능이니 -1을 출력합니다.  그렇지 않을 경우 ans값을 출력하면 됩니다.
 

느낀 점

시간초과로 한 번 틀렸습니다.. bfs를 첫 번째 행에서 매번 진행해서 발생한 문제라 한 번만 수행하도록 바꿔주니 한 번에 맞았습니다!