백준 16929번 Two Dots

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

16929번: Two Dots

 

 

 

 

 

 

<접근방법>

정점의 갯수가 4이상인 사이클의 존재 여부를 묻는 문제입니다.

 

dfs를 돌면서 이미 방문한 지점도 확인해주어야 하는 문제였습니다.

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

struct point {
	int y, x;
};

int n, m;
char map[51][51];
bool visit[51][51];
bool suc;
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

point start;

void dfs(int dep, int y, int x) {
	if (suc) return;

	for (int i = 0; i < 4; i++) {
		int ty = y + dy[i];
		int tx = x + dx[i];

		

		if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;
		if (map[ty][tx] != map[start.y][start.x]) continue;

		if (visit[ty][tx]) {
			if (dep >= 4 && start.y == ty && start.x == tx) {
				suc = true;
				return;
			}
		}

		else {
			visit[ty][tx] = true;
			dfs(dep + 1, ty, tx);
		}
	}

}


int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			memset(visit, false, sizeof(visit));

			start = {i, j};
			visit[i][j] = true;

			dfs(1, i, j);

			if (suc) break;
		}
	}

	if (suc) cout << "Yes";
	else cout << "No";
	puts("");

	return 0;
}