[BAEKJOON] 16929. Two Dots

문제 :

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

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

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

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

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

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

입력 :

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

출력 :

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

풀이 :

처음에는 bfs로 같은 색깔의 칸을 4개 이상 방문하면 문제를 해결할 수 있을 것이라고 너무 쉽게 생각했다.

하지만 본 문제의 키 포인트는 사이클을 찾아야 한다. 따라서 bfs방식보다는 dfs 방식이 문제를 해결할 수 있다고 생각했다.

dfs를 구현할 때 다른 문제와 차ㅏ이가 있었던 점을 몇개 꼽아보았다.

1. 사이클을 찾아야 하기 때문에 방문했던 지점을 다시 방문하면 사이클이라고 판별하려 했다. 단, 직전에 방문한 포인트를 다시 방문하는 경우는 사이클이 아니라 다시 되돌아간 경우이기 때문에 직전에 지나왔던 방향으로는 체크하지 못하게 notdir 변수를 두고 방문 체크를 했다.
2. dfs 탐색에서 한번 탐색한 지점은 다시 탐색하지 않아도 된다. 이미 그 지점에서는 같은 색상 지점의 사이클이 없는 것을 확인했기 때문에 visit 배열의 상태를 바꾸지 않고 유지하면 문제를 해결할 수 있었다.

dfs 구현이 익숙하다면 비교적 쉽게 접근할 수 있었던 문제였던 것 같다. 사이클 문제는 처음부터 bfs로 생각하지 않도록 주의해야 할 것 같다.

코드 :

#include <iostream>

using namespace std;
bool visit[50][50];
char map[50][50];
int n, m, di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};

bool dfs(int x, int y, int cnt, int notdir) {
    visit[x][y] = true;
    char standard = map[x][y];
    for (int k = 0; k < 4; k++) {
        if (notdir == k) continue;
        int cmpx = x + di[k], cmpy = y + dj[k];
        if (cmpx < 0 || cmpx >= n || cmpy < 0 || cmpy >= m) continue;
        if (map[cmpx][cmpy] != standard) continue;
        if (visit[cmpx][cmpy]) return true;
        if (dfs(cmpx, cmpy, cnt + 1, (k + 2) % 4)) return true;
    }
    return false;
}

int main() {
    int i, j;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            cin >> map[i][j];

    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            if (!visit[i][j])
                if (dfs(i, j, 1, 5)) {
                    cout << "Yes\n";
                    return 0;
                }

    cout << "No\n";
    return 0;
}