취미로 코딩하기

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

이번에 볼 문제는 백준 26533번 문제인 Tractor Path이다.
문제는 아래 링크를 확인하자.

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

오른쪽 또는 아래쪽만으로 움직여 좌상단 칸에서 우하단 칸으로 이동할 수 있는지를 확인하는 문제이다.

이는 각 '.' 칸을 노드로, 각 '.'칸의 아래방향과 오른쪽 방향의 칸에 '.'있을 경우의 관계를 에지로 나타낸 그래프 위에서 좌상단 칸 노드로부터 우하단 칸 노드까지의 경로가 존재하는지를 구하는 것과 같은 문제로 생각할 수 있다.

위의 그래프를 모델링해 그래프탐색으로 문제를 해결하자.

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

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

int N;
vector<string> board;
vector<vector<bool>> visited;

void dfs(int r, int c) {
	visited[r][c] = 1;
	if (r + 1 < N && !visited[r + 1][c] && board[r + 1][c] == '.') dfs(r + 1, c);
	if (c + 1 < N && !visited[r][c + 1] && board[r][c + 1] == '.') dfs(r, c + 1);
}

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

	cin >> N;
	for (int r = 0; r < N; r++) {
		visited.emplace_back(vector<bool>(N));
		board.emplace_back("");
		cin >> board.back();
	}

	dfs(0, 0);

	if (visited[N - 1][N - 1]) cout << "Yes";
	else cout << "No";
}