[BOJ 26009 // C++] 험난한 등굣길

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

 

이번에 볼 문제는 백준 26009번 문제인 험난한 등굣길이다.
문제는 아래 링크를 확인하자.

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

26009번: 험난한 등굣길

방문할 수 없는 칸을 한칸한칸 접근 못하는 칸으로 칠하기에는 칠해야 할 칸의 수가 너무 많아 시간초과를 피할 수 없을 것이다. 대신 해당 칸들을 모두 접근 못하게 하는 것과 같게 해당 칸들의 경계만을 접근 못하는 칸으로 칠하는 것으로 의도와 같은 효과를 얻을 수 있다.

 

위와 같이 칠한 뒤에는 BFS 등을 이용해 간단히 문제를 해결할 수 있다.

 

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

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

int R, C, K;
int board[3001][3001];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void bfs() {
	board[1][1] = 1;
	queue<pair<int, int>> que;
	que.push({ 1,1 });

	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr<1 || rr>R || cc<1 || cc>C || board[rr][cc]) continue;

			board[rr][cc] = board[r][c] + 1;
			que.push({ rr,cc });
		}
	}
}

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

	cin >> R >> C >> K;
	while (K--) {
		int r, c, d; cin >> r >> c >> d;
		for (int i = 0; i <= d; i++) {
			int rr, cc;
			rr= r + i, cc = c + (d - i);
			if (rr > 0 && rr <= R && cc > 0 && cc <= C) board[rr][cc] = -1;
			rr = r - i, cc = c + (d - i);
			if (rr > 0 && rr <= R && cc > 0 && cc <= C) board[rr][cc] = -1;
			rr = r + i, cc = c - (d - i);
			if (rr > 0 && rr <= R && cc > 0 && cc <= C) board[rr][cc] = -1;
			rr = r - i, cc = c - (d - i);
			if (rr > 0 && rr <= R && cc > 0 && cc <= C) board[rr][cc] = -1;
		}
	}

	bfs();

	if (board[R][C]) cout << "YES\n" << board[R][C] - 1;
	else cout << "NO";
}