백준 BOJ 16929 - Two Dots

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

16929번: Two Dots

그래프에서 사이클을 찾아내는 문제.

DFS로 접근했다.

dfs를 진행할때, 바로 전에 지나고 있던 점의 위치를 px, py에 담아놓아서,

탐색한 다음 뒤를 돌아서 다시 탐색하는것을 막아준다.

 

보통은 방문 여부를 저장하는 vis 배열을 통해서 재탐색을 막아주는데,

방문여부를 통해서 재탐색을 막을 수 없는 이유로

 

문제에서 요구하고 있는 것이

"방문한 적이 있던 같은 점의 색을 가진 위치" 로 이동하는 것이기 때문이다.

해당 조건에 맞는 위치에 도착하였을때 Yes를 출력하게 소스코드를 작성해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int vis[100][100] = {0};

string S[100];

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int N,M;

bool dfs(int x, int y, int bx, int by){
	if(vis[x][y]) return true;
	vis[x][y] = true;
	
	for(int t=0; t<4; t++){
		int nx = x+dx[t];
		int ny = y+dy[t];
		
		if(-1==nx || nx==N || -1==ny || ny==M) continue;
		if(S[nx][ny] != S[x][y]) continue;
		if(nx==bx && ny==by) continue;
		
		if(dfs(nx,ny,x,y)) return true;
	}
	return false;
}

int main(){
	cin >> N >> M;
	for(int i=0; i<N; i++) cin >> S[i];
	
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(vis[i][j]) continue;
			if(dfs(i,j,-1,-1)){
				cout << "Yes\n";
				return 0;
			}
		}
	}

	cout << "No\n";
	return 0;
}