[G4] 백준 16929번 Two Dots C++ 깊이 우선 탐색

리뷰

 

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

4방향으로 탐색이 가능한 맵 상에서 동일한 알파벳으로 이루어진 사이클이 존재하는지 판단하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• s : 맵 정보를 저장할 문자열 배열
• n, m : 맵의 세로/가로 크기를 저장할 변수
• v : 각 칸에 방문한 시간을 저장할 2차원 배열
• cycle : 사이클이 발생했는지 여부를 저장할 변수
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. dfs

void dfs(int cx, int cy, const char& ch, int t) {
	if (cycle) return;

	for (int i = 0; i < 4; ++i) {
		int nx = cx + dx[i], ny = cy + dy[i];

		if (0 <= nx && nx < n && 0 <= ny && ny < m && s[nx][ny] == ch) {
			if (!v[nx][ny]) {
				v[nx][ny] = t + 1;
				dfs(nx, ny, ch, t + 1);
			}
			if (v[nx][ny]) {
				if (abs(v[nx][ny] - t) < 2) continue;
				else {
					cycle = true;
					return;
				}
			}
		}
	}
}

 

맵을 탐색하며 동일한 색을 이어가며 사이클이 발생하는지 여부를 체크하기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, 맵 정보를 입력 받아 s배열을 초기화한다.
2. 맵의 각 칸을 순회하며 이미 방문한 칸이라면 continue처리한다.
3. 방문하지 않은 칸이라면 값을 1로 저장하고, dfs함수에 좌표와 문자, 시작 시간을 매개변수로 전달하여 호출한다.
4. dfs함수 내부에서 변수 cx, cy에 좌표를, ch에 문자를, t에 방문 시간을 매개변수로 받아 파싱한다.
5. 기저 조건으로 cycle이 true라면 이미 사이클을 발견한 상태이므로 리턴 처리한다.
6. 4방향을 탐색하며 맵의 범위 내에 있고, 동일 문자라면 일단 이동이 가능한 칸이다.
7. 아직 방문하지 않은 칸이라면 v배열에 t+1을 저장하고 재귀를 이어서 수행한다.
8. 이미 방문한 칸이면서 현재 칸과 시간 차이가 1이하라면 이동을 하지 않는다.
9. 이미 방문한 칸이면서 현재 칸과 시간 차이가 2이상이라면 cycle을 true로 저장하고 리턴 처리한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 방문한 시간이 2이상 차이가 나는 칸에 접근하는 경우 사이클이 발생한 경우로 보면 된다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 50;
string s[N];
int n, m;
int v[N][N];
bool cycle;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void dfs(int cx, int cy, const char& ch, int t) {
	if (cycle) return;

	for (int i = 0; i < 4; ++i) {
		int nx = cx + dx[i], ny = cy + dy[i];

		if (0 <= nx && nx < n && 0 <= ny && ny < m && s[nx][ny] == ch) {
			if (!v[nx][ny]) {
				v[nx][ny] = t + 1;
				dfs(nx, ny, ch, t + 1);
			}
			if (v[nx][ny]) {
				if (abs(v[nx][ny] - t) < 2) continue;
				else {
					cycle = true;
					return;
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	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 (v[i][j]) continue;
			v[i][j] = 1;
			dfs(i, j, s[i][j], 1);
			if (cycle) break;
		}
	}
	cout << (cycle ? "Yes" : "No");
}