[프로그래머스] 258711 도넛과 막대 그래프(javascript)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258711

풀이

차수(Degree)를 활용하는 그래프 문제였다.

코딩 테스트 문제를 풀 때 항상 스스로에게 두 가지 원칙을 세운다.

1. 새로운 저장 공간(자료구조)을 가능하면 만들지 말고, 주어진 입력을 최대한 활용하자
2. 각 원소를 가능한 한 적은 횟수만 방문하자

출제자의 의도에 맞는 풀이는 대부분 이 두 원칙을 자연스럽게 만족하는 경우가 많았다.

이번 문제에서도 edges를 별도의 graph로 변환하지 않고 해결하려 했다. 또한 전체 데이터를 여러 번 순회하지 않는 방향으로 접근했다.

하지만 한 번의 탐색만으로 모든 요구사항을 동시에 해결하기는 쉽지 않았다. 특히 생성한 정점의 번호를 구하면서 동시에 그래프의 종류까지 판별하는 방법이 바로 떠오르지 않았다.

그래서 전략을 다음과 같이 나눴다.

1. 먼저 생성한 정점의 번호를 구한다.
2. 이후 해당 정점에서 뻗어나간 그래프들을 각각 분석한다.

생성한 정점을 찾고 나니 이후 과정은 비교적 단순했다. 해당 정점에서 연결된 각 시작점은 서로 다른 그래프의 일부였고, 그 정점에서 출발하여 그래프의 형태를 판별하면 되었다.

그래프 타입 판별을 위해 그래프를 탐색하며 각 노드의 차수를 통해 그래프의 형태를 구분했다.

해당 해결법을 피드백하며 개선점을 찾은 결과,

라는 공식이 이 문제의 핵심이였던 것을 알 수 있었고, 해당 방법으로 주어진 인자 외의 저장 공간(자료구조)을 생성하지 않고도 문제를 해결할 수 있었다.

최종적으로 사용한 판별 기준은 다음과 같다.

• 생성한 정점의 번호: 2 <= out-degree이고, in-degree = 0인 정점
• 총 그래프의 개수: 생성한 정점의 out-degree
• 막대 모양 그래프의 수: out-degree = 0인 정점의 개수
• 8자 모양 그래프의 수: out-degree = 2이고, 생성한 정점이 아닌 정점의 개수

개선점 적용 전 정답 코드

const TYPE = Object.freeze({
	DONUT: 1,
	BAR: 2,
	EIGHT: 3,
});

const solution = (edges) => {
	const ret = Array(4).fill(0);
	const toVisit = new Map();
	const inDegree = new Map();

	const isTypeOf = (begin) => {
		let current = begin, nexts;

		while ((nexts = toVisit.get(current)) !== undefined) {
			if (nexts.length === 2) {
				return TYPE.EIGHT;
			}
			current = toVisit.get(current)[0];
			if (current === begin) {
				return TYPE.DONUT;
			}
		}

		return TYPE.BAR;
	};

	edges.forEach(([u, v]) => {
		if (!toVisit.has(u)) toVisit.set(u, []);
		toVisit.get(u).push(v);
		inDegree.set(v, (inDegree.get(v) ?? 0) + 1);
	});

	for (const [node, nexts] of toVisit) {
		if (2 <= nexts.length && inDegree.has(node) == false) {
			ret[0] = node;
			break;
		}
	}

	toVisit.get(ret[0]).forEach((next) => {
		ret[isTypeOf(next)] += 1;
	});

	return ret;
};