이분 그래프

문제

언어

  • JavaScript

문제 풀이 step 1

  • 우선 주어지는 입력을 통해서 인접 리스트 형식의 그래프를 생성합니다.
  • 그리고 BFS 탐색을 실시합니다.
  • BFS 탐색을 할 때 각 정점의 그룹을 정해줘야 합니다.
  • 그룹을 정해줄 때는 탐색 하기 바로 전 정점의 그룹을 기억하고 있다가, 그에 반대되는 그룹을 지정해야 합니다.
    • 즉, 1 번 정점에서 2 번 정점으로 탐색을 할 때, 1 번 정점의 그룹을 A 그룹이라고 지정했다면, 2 번 정점의 그룹은 B 그룹이라고 지정해야 합니다.
  • 그리고 입력받은 간선 정보들을 이용해서 같은 그룹에 있는 정점끼리 연결되는 간선이 있는지 파악하고, 있다면 ‘NO’ 없다면 ‘YES’ 를 출력합니다.

주의할 점

  • 저는 연결 요소가 한 개인 그래프가 입력으로 나올줄 알았습니다.
  • 하지만 연결 요소가 여러개인 그래프가 입력으로 나옵니다.
  • 그러니 각 정점마다 BFS 탐색을 실시해서, 모든 정점의 그룹을 정해줘야 합니다.
  • 문제에서 그에 대한 말이 없었으니, 이런 섣부른 판단은 안하는 것이 좋을 것 같습니다.ㅎㅎ

소스 코드 1

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

const solution = (input) => {
	let t = Number(input[0]);

	let res = "";
	let index = 1;
	while (t-- > 0) {
		const [v, e] = input[index++].split(" ").map(Number);
		const length = index + e;

		// 간선 정보를 기억 (나중에 사용)
		const edges = input.slice(index, length);

		// 인접리스트 형식의 그래프 생성
		const graph = Array.from({length: v + 1}, () => []);
		for (; index < length; index++) {
			const [from, to] = input[index].split(" ").map(Number);

			graph[from].push(to);
			graph[to].push(from);
		}

		// 각 그룹을 정해주기 위한 배열
		const side = Array.from({length: v + 1}, () => 0);

		// BFS
		const queue = [];
		const visited = Array.from({length: v + 1}, () => false);
		for (let i = 1; i < v + 1; i++) {
			if (visited[i]) continue;

			visited[i] = true;
			queue.push(i);
			side[i] = 1;
			while (queue.length) {
				const from = queue.shift();

				for (let j = 0; j < graph[from].length; j++) {
					const to = graph[from][j];
					if (visited[to]) continue;

					// 이전 정점에 반대되는 그룹을 정해줌
					if (side[from] === 1) side[to] = -1;
					else side[to] = 1;

					visited[to] = true;
					queue.push(to);
				}
			}
		}

		// 아까 기억한 간선 정보들을 이용해서 같은 그룹끼리 간선이 있는지 파악
		let ans = "YES";
		for (let i = 0; i < edges.length; i++) {
			const [from, to] = edges[i].split(" ").map(Number);

			if (side[from] === side[to]) {
				ans = "NO";
				break;
			}
		}

		res += `${ans}\n`;
	}

	return res;
};

console.log(solution(input));