취미로 코딩하기

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

이번에 볼 문제는 백준 6191번 문제인 Cows on Skates이다.
문제는 아래 링크를 확인하자.

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

주어지는 농장을 돌이 많지 않은 상하좌우 칸끼리 연결되어있는 그래프로 생각하면 주어진 문제는 농장의 (1,1) 칸에 대응되는 그래프의 노드에서 (R,C) 칸에 대응되는 그래프의 노드로 이어지는 경로를 찾는 문제가 된다. 경로의 존재성은 문제가 보장해주고 있으므로, bfs 등의 그래프 탐색 알고리즘을 이용해 경로를 찾아 문제를 해결하자.

이 때, 각 노드를 탐색할 때마다 해당 노드를 어떤 노드로부터 접근해왔는지를 기록해두자. 그리고 모든 탐색을 마친 다음 (R,C) 칸으로부터 탐색경로를 역추적해 문제의 답을 구하자.

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

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

int R, C;
string board[115];
pair<int, int> backtrack[115][79];
bool visited[115][79];

queue<pair<int, int>> que;
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
void bfs() {
	que.push(make_pair(1, 1));
	visited[1][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 (visited[rr][cc] || board[rr][cc] == '*') continue;
			visited[rr][cc] = 1;
			backtrack[rr][cc] = make_pair(r, c);
			que.push(make_pair(rr, cc));
		}
	}
}

vector<pair<int, int>> stk;
pair<int, int> p11 = make_pair(1, 1);

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

	cin >> R >> C;

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

	bfs();

	pair<int, int> cur = make_pair(R, C);
	while (cur != p11) {
		stk.emplace_back(cur);
		cur = backtrack[cur.first][cur.second];
	}

	cout << 1 << ' ' << 1 << '\n';
	while (!stk.empty()) {
		cout << stk.back().first << ' ' << stk.back().second << '\n';
		stk.pop_back();
	}
}