[백준16929] Two Dots (C++)

유후·2022년 5월 22일
0

백준

목록 보기
33/66

📌 문제

BOJ 바로가기

게임판에 사각형 사이클이 존재하면 Yes를, 존재하지 않으면 No를 반환해야 한다.

🗡 풀이

📍 DFS를 이용하여 풀 수 있다.
📍 현위치에서 상하좌우로 계속해서 나아가되 다시 본래의 위치로 돌아오면 flag에 true값을 할당해준다. 이 때 주의해야 할 점은 cnt가 4 이상일 때에만 flag에 true값을 줘야 한다.
처음에 '어차피 visited 배열이 있으니까 cnt 선언 안해줘도 괜찮겠지' 하고 생각했다가 한참을 헤맸다.. 내 코드에서 nx, ny는 (당연하게도) visited 검사 전에 할당되기 때문에 cnt를 꼭 선언해주고 cnt >= 4일 때에만 Yes를 반환하도록 만들어줘야 한다.
📍 질문게시판을 보니 Yes를 YES로, No를 NO로 써서 틀리신 분들이 여럿 계셨다. 깊은 애도를 표합니다..😂

🚩 소스코드

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

int n, m;
string str[50];
bool visited[50][50] = { false };
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool flag = false;
int s_x, s_y;

void dfs(int x, int y, int cnt)
{
	visited[x][y] = true;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx == s_x && ny == s_y && cnt >= 4)
		{
			flag = true;
			return;
		}
		else if (0 <= nx && nx < n && 0 <= ny && ny < m && !visited[nx][ny] && str[x][y] == str[nx][ny])
			dfs(nx, ny, cnt + 1);
	}
	visited[x][y] = false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> str[i];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			s_x = i;
			s_y = j;
			dfs(i, j, 1);
			if (flag == true)
			{
				cout << "Yes";
				return 0;
			}
		}
	}
	cout << "No";
	return 0;
}
profile
이것저것 공부하는 대학생

0개의 댓글