[백준 16929] Two Dots C++

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

16929번: Two Dots

 

 

이번 시간은 Tow Dots 문제 풀이법에 대해 설명드리겠습니다.

 

같은 색깔에 한해서 Circle이 존재하느냐를 찾는 문제입니다. 

 

그래프 탐색 알고리즘인 BFS와 DFS 중 어떤 것을 사용하면 좀 더 효율적으로 사용할지 고민하다가

DFS 깊이 탐색으로 일정하게 쭉 들어가면서 탐색하면 될 것이라고 생각했습니다.

 

DFS를 구현하는 방법은 대표적으로 2가지가 있습니다. 

1. Stack을 이용한 DFS 탐색 구현

 

2, 재귀함수를 이용한 DFS 탐색 구현

 

이 있습니다. 저는 Stack을 이용한 DFS를 평소에 자주 구현하지 않고 재귀로만 자주 구현했습니다.

오랜만에 Stack으로 구현해보아야겠다고 생각하니 문제가 정말 많더라고요......

 

깊이 탐색으로 그래프를 쭉 들어가면서 탐색하고, 갈 수 없는 방향일 때는 다시 back 돌아가서

다시 탐색해야하는데, Stack을 이용하게 되면 돌아온길을 표시도 해야하고, 앞으로 가야하는 길이 왔던 길인지도 판별해야해서 제어문이 정말로 많이 들어갑니다.

 

상태 정보를 임시 저장할 수 있는 재귀 함수를 이용하여 이 문제를 풀어보려고 합니다.

 

재귀함수도 코드상으로는 짧지만, Stack처럼 Stack메모리에 저장되어 순차적으로 탐색하게 됩니다.

결국, 메모리 낭비는 재귀함수로 푸나, Stack으로 푸나 비슷하다고 생각합니다..(혹시 다르다면 알려주세요!)

 

재귀함수로 DFS를 풀게 되면, 내가 진행한 방향을 기억할 수 있기 때문에, 함수가 return 되더라도 이전에 실행했던 상태 다음부터 실행할 수 있기 때문에 딱히 제어문을 많이 사용할 필요가 없습니다.

 

방향 상우하좌방향으로 계속 탐색하고, 왔던 길을 다시 돌아가게만 안하면 되니까요!

 

저는 왔던 길을 다시 되돌아 탐색하지 않고, 탐색하다가 circle을 발견하게 되면 "Yes"를 출력하고 프로그램을 종료하게 만들었습니다.

 

전체 코드는 다음과 같습니다.

 

#include <iostream>

using namespace std;

#define input_max 50 + 1
#define dir 4

char map[input_max][input_max];
bool check[input_max][input_max];


int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int n, m;


void dfs(int x, int y, char type, int d) {

	check[x][y] = true; // 방문했다는 표시 하기

	if (map[x][y] != type) return;  // 같은 문자열이 아니라면 반환하여 다음 방향 실행하기

	


	for (int i = 0; i < dir; i++) {

		if (i == ((d + 2) % 4)) continue;  // 진행해온 반대방향은 돌아가는 방향이기 때문에 돌아가지 않게 만든다.

		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == type && !check[nx][ny]) {  //같은 문자이고, 갔던 길이 아닌지 확인
			
			dfs(nx, ny, type, i);

		}


		else if (map[nx][ny] == type && check[nx][ny]) { //같은 문자이지만, circular가 형성이 되면 "Yes"를 출력하고 프로그램 종료

			cout << "Yes" << '\n';

			exit(0);
		}
		
	}

}

void solution() {

	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++) {
			char temp = map[i][j];

			if (!check[i][j]) {  // 탐색해봤던 길이 아니라면 i, j부터 탐색을 시작해본다.


				int d = -1;  
				
				for (int k = 0; k < dir; k++) {

					if (map[i + dx[k]][j + dy[k]] == temp) {   // i,j 중심으로 4방향 상우하좌 중에서 가장 처음에 찾은 방향을 값을 넣기
						d = k;
						break;
					}
					
				}

				if (d == -1) continue; // 주변에 i,j와 같은 문자가 없다는 뜻이다. 1개의 문자만 존재할 때 default -1, 연산 패스

				dfs(i, j, temp, d);  //재귀함수 dfs깊이 탐색하기


			}
			
			
		}

	cout << "No" << '\n';



}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	solution();


	return 0;
}