[C++]백준16929번 Two Dots

오늘은 백준16929번 Two Dots 문제를 풀어보도록 하자.

DFS로 탐색을 하면서 cnt>=4 이고 처음 들어갔던 자리로 돌아오면 Yes를 출력해주는 문제였다.

함수 종료 조건을 for문 안에 인덱스가 바뀌고 나서 처리해준는 것이 핵심이다.

문제는 다음과 같다.

                               [접근법]

  1. DFS로 탐색을 하면서 처음 좌표 값에 도달하면 Yes를 출력해주면 된다. (기본 DFS)

                                     [코드]
#include <iostream>
using namespace std;
int R, C;
bool flag = false;
char map[50][50];
bool visit[50][50];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

bool Inbound(int y, int x) {
	return y >= 0 && y < R && x >= 0 && x < C;
}

void Init_visit() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			visit[i][j] = false;
		}
	}
}

bool dfs(int y, int x, int cnt, int dy, int dx) {
	visit[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int my = y + dir[i][0];
		int mx = x + dir[i][1];

		if (my == dy && mx == dx && cnt >= 4) {
			flag = true;
			return flag;
		}
		if (Inbound(my, mx)) {
			if (!visit[my][mx] && map[y][x] == map[my][mx]) {
				visit[my][mx] = true;
				dfs(my, mx, cnt + 1, dy, dx);
			}
		}
	}
	return flag;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (dfs(i, j, 1, i, j)) {
				cout << "Yes";
				return 0;
			}
			Init_visit();
		}
	}
	cout << "No";
}