https://www.acmicpc.net/problem/16929
//C++
#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.1415926535
using namespace std;
typedef long long ll;
char arr[51][51];
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int visited[51][51];
int n, m;
bool go(int x, int y, int px, int py, char color)
{
if (visited[x][y] == 1) //mark 1
return true;
visited[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if ((nx != px) || (ny != py))
{
if ((arr[nx][ny] == color) && (nx >= 0 && nx < n && ny >= 0 && ny < m))
{
if(go(nx, ny, x, y, color)) return true;
}
}
}
return false;
}
int main() {
F_I;
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 (visited[i][j]) //mark 2
continue;
if (go(i,j, 0,0, arr[i][j]))
{
cout << "Yes" << '\n';
return 0;
}
}
}
cout << "No" << '\n';
}
> 방문을 할 때의 방문 조건!
1. 방문하는 점들의 색깔이 같아야 하고(애초에 같은 색깔 끼리 사이클을 이루어야 하니까) ((arr[nx][ny] == color))
2. 방문하는 점들이 범위 안에 있어야 하고 ((nx >= 0 && nx < n && ny >= 0 && ny < m))
3. 또한 '서로 다른' 점들을 하나씩 방문해야 한다. ((nx != px) || (ny != py))
이 3가지 조건을 모두 만족하면서 dfs 로 방문을 하다가, 이미 방문한 적이 있는 점을 만났다는 것은(위 소스코드의 mark 1 부분), 다시 말해서 사이클이 존재한다는 의미이므로, true 를 return 한다.
> main문에서는 이중 반복문을 통해 입력된 점을 모두 한번씩 돌면서 (물론, 여기서는 이미 방문한 점을 가지고 또 함수 호출을 하면 안된다. 소스코드의 mark 2 부분), go 함수를 호출했을 때, return 값이 true인게 하나라도 있다면, 사이클이 최소 1개 이상 존재한다는 의미이므로, 그때는 Yes를 출력하고 바로 프로그램 종료를 한다.
모든 점을 다 돌았음에도 불구하고 true를 한번이라도 return 받지 못했다면, 사이클이 하나도 없다는 의미이므로, No를 출력하고 프로그램을 종료한다.
'Problem Solving > 백준' 카테고리의 다른 글
[백준] 12865번 : 평범한 배낭 (0) | 2020.08.12 |
---|---|
[백준] 11052번 : 카드 구매하기 (0) | 2020.08.10 |
[백준] 10972번 : 다음 순열 (0) | 2020.07.16 |
[백준] 15650번 : N과 M (2) (0) | 2020.07.15 |
[백준 ] 1748번 : 수 이어 쓰기 1 (0) | 2020.07.14 |