mojo's Blog

[백준 16929] Two Dots 본문

백준/BFS, DFS

[백준 16929] Two Dots

_mojo_ 2021. 7. 7. 20:43

문제 링크 => 16929번: Two Dots (acmicpc.net)

 

16929번: Two Dots

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문

www.acmicpc.net


전형적인 DFS 문제이다.

 

점마다 DFS를 돌리면서 4번이상 이동함과 동시에 다시 재자리 점으로 돌아올 경우 Yes를 출력하도록 하면 된다.

 

이때 이동은 점의 색이 같아야 하며 인접하는 경우(좌우상하) 인 경우여야 한다.

 

그리고 방문처리의 초기화를 위해 별도의 init 함수를 생성하였다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

int n, m;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
char arr[50][50];
bool visited[50][50];
string result = "No";

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = false;
		}
	}
}

void dfs(int startX, int startY, int x,int y, int cnt, char c) {
	if (visited[x][y]) {
		if (x == startX && y == startY && cnt>=4) {
			result = "Yes";
		}
		return;
	}
	visited[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int nextX = x + dx[i];
		int nextY = y + dy[i];
		if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
			if(arr[nextX][nextY]==c) dfs(startX, startY, nextX, nextY, cnt + 1, c);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (result == "No") {
				init();
				dfs(i, j, i, j, 0 ,arr[i][j]);
			}
		}
	}

	cout << result;

	return 0;
}

'백준 > BFS, DFS' 카테고리의 다른 글

[백준 15684] 사다리 조작  (0) 2021.09.05
[백준 2146] 다리 만들기  (0) 2021.07.19
[백준 16947] 서울 지하철 2호선  (0) 2021.07.19
[백준 19538] 루머  (0) 2021.07.17
[백준 2151] 거울 설치  (1) 2021.06.30
Comments