문제

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"를 출력한다.

풀이

기존에 풀었던 dfs문제들과 비슷한 유형같아보였다.

중요하게 생각했던 부분은
1) 한번 갔던 방향의 반대 방향으로 가면 다시 되돌아 오게 되므로 반대방향을 빼고 구해줘야 한다.(오른쪽을 갔다가 다시 왼쪽으로 오면 같은 자리이므로)
2) 아래의 모양같이 꼭 시작점에서 끝나지 않고 지나오던 길과 만날수도 있다.

1. 먼저 지나온길을 기록할 memory배열과 answer을 만든다.
2. 게임판을 for문으로 돌려 dfs함수를 호출한다. 만약 이미 지나왔던 길이면 continue로 넘어가고 answer='Yes'로 답이 나왔다면 break해 준다.
3. dfs함수는 기준점, 점들이 연결된 배열 리스트, 이동한 방향, 현재 알파벳을 받는다.
4. 만약 현재 기준점이 이미 배열에 있는경우 사이클이 생겼다는 의미이므로 answer='Yes'를 해주고 return 시켜준다.
5. 기준점의 좌표를 memory배열값에 1로 넣어주고 현재 함수로 들어온 기준점을 연결할 배열 리스트에 넣어준다.
6. right, bottom, left, top을 순서대로 넣어주는데 만약 이전의 방향과 반대이거나 이동할 방향의 좌표가 기준이되는 알파벳이 아닐경우 다음으로 넘어간다.

코드

var fs = require('fs');
const input = fs
	.readFileSync('/dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v, index) => (index === 0 ? v.split(' ') : v.split('')));
const [N, M] = input.shift().map(Number);

let memory = Array.from(Array(N), () => Array(M).fill(0));
let answer = 'No';

function solution() {
	function dfs(dot, array, direction, charactor) {
		const [n, m] = dot;
		if (array.length > 3 && array.includes(`${n} ${m}`)) {
			answer = 'Yes';
			return;
		}

		//지나온길 기록하기
		memory[n][m] = 1;

		//현재 기준점을 배열에 추가
		array.push(`${n} ${m}`);

		const directions = {
			right: [n, m + 1],
			bottom: [n + 1, m],
			left: [n, m - 1],
			top: [n - 1, m],
		};

		Object.keys(directions).map((d) => {
			const [n_, m_] = directions[d];
			if (n_ < 0 || m_ < 0 || n_ >= N || m_ >= M) return;

			//같은 알파벳이 아닐시에 return
			if (input[n_][m_] !== charactor) return;

			//이전방향의 반대로 가면 제자리로 가므로 반대방향을 제외
			if (direction === 'right' && d !== 'left') {
				dfs([n_, m_], array, d, charactor);
			}
			if (direction === 'left' && d !== 'right') {
				dfs([n_, m_], array, d, charactor);
			}
			if (direction === 'top' && d !== 'bottom') {
				dfs([n_, m_], array, d, charactor);
			}
			if (direction === 'bottom' && d !== 'top') {
				dfs([n_, m_], array, d, charactor);
			}
		});
	}

	for (let i = 0; i < N; i++) {
		for (let j = 0; j < M; j++) {
			//답이 나왔다면 break
			if (answer === 'Yes') break;
			//이미 지나왔던 길이면 continue
			if (memory[i][j] === 1) continue;

			const c = input[i][j]; //기준점의 알파벳
			dfs([i, j], [], 'right', c);
		}
	}
	console.log(answer);
}

solution();

오랜만에 한번에 성공한 문제! 매번 실패하거나 시간초과가 되서 채점 때마다 너무 떨림...😇