게임판에 사각형 사이클이 존재하면 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;
}