[백준] 16929번 two dots

16929 Two Dots 

문제

---

Two dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다. 
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 
• 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

입력

---

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 

게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

출력

---

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

제한

---

• 2 ≤ N, M ≤ 50
  

풀이)

처음에 bfs 풀었다가 틀린 문제이다. bfs로 구현을 하니, 

사이클을 형성하는지 안하는지의 조건을 만들기 어려웠다.

그래서 두번째로 dfs로 풀었다. 각 모든 점들에 대해서 같은 문자일 경우(즉, 같은 색일 경우) 방문하게 해놓고, 

만약 처음 시작한 점과 방문한 점이 같다면 사이클이 형성된 것으로 보았다.

코드)

#include <stdio.h>
#include <queue>
using namespace std;
 
char map[50][50];
int n, m;
//상하좌우
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1};
bool visited[50][50];
int result = 0;
pair<int, int> start;
 
void dfs(int y, int x, char ch, int depth) {
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= 0 && ny < n&&nx >= 0 && nx < m) {
            if (map[ny][nx] == ch) {
                //사이클이 되려면 최소 4개의 점이 필요하니깐
                //이전점까지 3개는 무조건 있어야함
                //또한, 사이클이 된다는것 시작점으로 다시 돌아온다는 뜻
                if (depth >= 3 && ny == start.first && nx == start.second) {
                    result = 1;
                    return;
                }
                if (visited[ny][nx] == true) continue;
                visited[ny][nx] = true;
                dfs(ny, nx, ch,depth+1);
            }
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    getchar();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%c", &map[i][j]);
        }
        getchar();
    }
    //각 모든 점들에 대해서 사이클이 형성되는지 검사
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            start = { i,j }; //시작점
            visited[i][j] = true;
            dfs(i, j, map[i][j], 1);
            
            for (int t = 0; t < n; t++) { //다음을 위해서 false로 초기화
                fill(visited[t], visited[t] + m, false);
            }
 
            if (result == 1) {
                printf("Yes");
                return 0;
            }
        }
    }
    printf("No");
 
    return 0;
}

결과)