16929 Two Dots

https://www.acmicpc.net/problem/16929

문제

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

 

=======

문제 분석

출발 지점과 같은 알파벳으로만 경로를 이동하면서 사이클을 만들 수 있냐는 문제다.

이중 반복문을 통해 각 정점에 방문해보면서 이전에 탐색했던 곳이라면 패스 하고 아니라면 경로를 탐색해본다.

사이클을 만들 수 있느냐를 찾는 것이므로 탐색 방법은 DFS로 출발한 지점으로부터 쭉 탐색 가본다

다른 알파벳이라면 패스

이미 방문한 정점이지만 사이클을 이루는 지 체크 => visited 를 만들어서 visited[cur]-visited[next]>=3 이라면 사이클 이룬것이므로 탐색 종료. 아니라면 패스 

오답노트

사이클을 이루는 것이 꼭 출발지점으로 돌아와야한다고 생각했었지만 출발 지점으로 돌아오지 않더라도 어떠한 점들끼리 이어져서 사이클을 이룰 수 있다는 것을 놓쳐서 틀렸었음

정답 코드

const init = (input) => {
    const [n, m] = input[0].split(' ').map((v) => +v);

    const gr = Array.from({ length: n }, () => []);

    for (let i = 0; i < n; i++) {
        gr[i].push(...input[i + 1].split(''));
    }
    return [n, m, gr];
};

const main = (input) => {
    const [n, m, gr] = init(input);
    const visited = Array.from({ length: n }, () =>
        Array.from({ length: m }).fill(-1)
    );

    const dx = [0, 0, -1, 1];
    const dy = [-1, 1, 0, 0];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (visited[i][j] !== -1) continue;
            const [si, sj] = [i, j];
            visited[si][sj] = 0;
            let answer = false;
            const dfs = (ci, cj) => {
                for (let k = 0; k < 4; k++) {
                    const nx = ci + dx[k];
                    const ny = cj + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if (gr[nx][ny] !== gr[si][sj]) continue;

                    if (visited[nx][ny] !== -1) {
                        if (visited[ci][cj] - visited[nx][ny] >= 3) {
                            answer = true;
                            return;
                        }
                        continue;
                    }
                    visited[nx][ny] = visited[ci][cj] + 1;
                    dfs(nx, ny);
                }
            };
            dfs(si, sj);
            if (answer) {
                console.log('Yes');
                return;
            }
        }
    }
    console.log('No');
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');
main(input);