Two Dots

문제

언어

  • JavaScript

문제 풀이 step 1

  • 결론적으로 문제에서 원하는 것은 같은 색으로 칠해진 공들을 하나의 그래프로 보고, 그 안에서의 사이클의 존재 여부입니다.
  • DFS 탐색을 이용해서 풀 수 있습니다.
  • 우선 문제의 사이클의 조건을 분석해보겠습니다.
    • 모든 k 개의 점은 서로 다르다.
      • 사이클에 포함되는 점들이 서로 다른 점들이라는 얘기일 것입니다.
    • k 는 4 보다 크거나 같다.
      • 사이클의 최소 크기가 4 라는 얘기일 것입니다. (일반적인 그래프가 아닌 정방형 그래프이기 때문에 당연한 얘기입니다.)
    • 모든 점의 색은 같다.
      • 같은 색으로 칠해진 공들 안에서만 사이클을 찾으라는 얘기일 것입니다.
    • 모든 1 <= i <= k - 1 에 대해서 di 와 di+1 은 인접하다. 또 dk 와 d1 도 인접해야 한다.
      • 이말은 사이클을 구성하는 점들 간에는 연결이 되어 있어야 하고, 사이클의 시작점과 끝점이 연결되어 있어야 한다는 얘기일 것입니다.

문제 풀이 step 2

  • 우선 저는 dist 라는 배열을 하나 생성했습니다.
    • dist 배열의 역할은 방문 처리의 역할과 탐색 시작점으로부터의 거리를 기억합니다.
    • 즉, 저는 DFS 탐색을 진행할 때마다 도착하는 노드에 시작점으로부터의 거리를 저장했습니다. (이는 탐색의 깊이를 이용해서 할 수 있습니다.)
  • DFS 탐색은 같은 색으로 칠해진 노드이자 방문하지 않은 정점에 대해서 실시합니다.
    • 그리고 탐색시 추가적으로 사이클이 생기는지 여부를 판단합니다.
    • 이것은 같은 색으로 칠해진 노드이며 방문한 정점들에 대해서 dist 차이를 구합니다.
    • 이 때, dist 값의 차이가 3 이상이면 사이클이 있다고 볼 수 있습니다.
  • 만약 사이클의 존재를 찾았으면 더 이상의 탐색은 무의미하므로 탐색을 종료합니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

class Dot {
	constructor(x, y) {
		this.x = x;
		this.y = y;
	}
}

let find = false;

const cx = [0, 0, 1, -1];
const cy = [1, -1, 0, 0];

// 갈 수 있는 경로인지 체크하는 함수
const isPossibleRoute = (n, m, arr, from, to) => {
	return (
		0 <= to.x &&
		to.x < n &&
		0 <= to.y &&
		to.y < m &&
		arr[from.x][from.y] === arr[to.x][to.y]
	);
};

// 사이클을 체크하는 함수
const checkCycle = (n, m, arr, dist, from) => {
	for (let i = 0; i < 4; i++) {
		const to = new Dot(from.x + cx[i], from.y + cy[i]);

		if (isPossibleRoute(n, m, arr, from, to) && dist[to.x][to.y] !== 0) {
			if (Math.abs(dist[from.x][from.y] - dist[to.x][to.y]) >= 3) return true;
		}
	}

	return false;
};

const DFS = (n, m, arr, dist, from, depth) => {
	// 사이클의 존재를 찾았을 경우 더 이상의 탐색은 무의미
	if (find) return;

	if (checkCycle(n, m, arr, dist, from)) {
		find = true;
		return;
	}

	for (let i = 0; i < 4; i++) {
		const to = new Dot(from.x + cx[i], from.y + cy[i]);

		if (isPossibleRoute(n, m, arr, from, to) && dist[to.x][to.y] === 0) {
			dist[to.x][to.y] = depth + 1;
			DFS(n, m, arr, dist, to, depth + 1);
		}
	}
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);
	const arr = [];
	for (let i = 1; i < n + 1; i++) {
		arr[i - 1] = input[i].split("");
	}

	const dist = Array.from({length: n}, () => Array(m).fill(0));
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			if (dist[i][j] !== 0) continue;

			dist[i][j] = 1;
			DFS(n, m, arr, dist, new Dot(i, j), 1);

			if (find) return "Yes";
		}
	}

	return "No";
};

console.log(solution(input));