[C/C++] 백준 16929번 - Two Dots

✏️ 문제 링크

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

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

주어진 배열 안에서 사이클의 유무를 찾는 문제이며, dfs로 접근할 수 있습니다. bfs로도 똑같은 방식으로 문제를 풀어봤는데 자꾸 예제 2번에서 틀리다고 나와서 포기했습니다... 가로와 세로의 길이가 50보다 작거나 같기 때문에 모든 점에 대해서 dfs로 탐색을 해도 시간초과가 발생하지 않습니다. dfs함수에서 조건을 조금만 생각하면 쉽게 풀 수 있습니다

1. 다음으로 가고자 하는 mx와 my의 값이 배열의 범위를 벗어나지는 않는가?
2. 다음으로 가고자 하는 map[mx][my]가 이전에 방문했던 알파벳 값과 동일한가?
3. 다음으로 가고자 하는 visit[mx][my]가 이전에 이미 방문한 적이 없는가? => 방문 후 탐색하기
4. 이미 방문했던 곳이지만 그곳이 출발점이면서 방문한 점의 개수가 4보다 크거나 같은가?

 

✏️ 문제 코드

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

typedef pair<int, int>edge;
char map[51][51];
bool visit[51][51];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int N, M;
bool check = false;
int start_X = 0;
int start_Y = 0;

void dfs(int i, int j,int cnt);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	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++) {
			start_X = i;
			start_Y = j;
			dfs(i, j,1);
			if (check) {
				cout << "Yes";
				return 0;
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					visit[i][j]=false;
				}
			}
		}
	}
	cout << "No";
}
void dfs(int i, int j,int cnt) {

	if (check)
		return;
	visit[i][j] = true;
	
	for (int x = 0; x < 4; x++) {
		int mx = dx[x] + i;
		int my = dy[x] + j;
		if (mx < 0 || my < 0 || mx >= N || my >= M)
			continue;
		if (map[mx][my] != map[i][j])
			continue;
		if (visit[mx][my] == false) {
			visit[mx][my] = true;
			dfs(mx, my, cnt + 1);
		}
		else {
			if (cnt >= 4 && mx == start_X && my == start_Y) {
				check = true;
				return;
			}
		}
	}
}