이분 그래프
📚 문제 설명
테스트 케이스 K 개가 주어지고, 각각의 테스트 케이스는 정점의 갯수 V와 간선의 갯수 E가 주어진다.
그리고 각각의 간선이 어떻게 이어져있는지 주어진다.
이때, 해당 테스트 케이스가 이분 그래프인지 구하여라.
이분 그래프는 그래프 정점의 집합을 둘로 나누었을 때, 각 집합의 속한 정점끼리는 이어지지 않는 그래프이다.
👨🏻💻 풀이 과정
이분 그래프의 특징은 간선의 두 정점은 서로 다른 영역에 속하는 것이라고 생각했다.
따라서 전체적인 과정은 BFS 함수와 동일하게 작성했지만,
visited 배열을 이용할 때 간선의 두 정점을 1과 -1로 만들었다.
BFS함수
- 간선의 연결을 따라 진행
- 만약
visited[NEXT] === visited[NOW]라면 종료. (이분 그래프가 아님)
const BFS = (start, linesOBJ, visited) => {
// 시작 지점.
let Queue = [start];
// 시작 지점은 1로 초기화.
visited[start] = 1;
// while 문에서 매번 Queue.shift()를 쓰지 않기 위한 변수.
let idx = 0;
while (Queue.length > idx) {
const NOW = Queue[idx];
// 지금 위치
const POSITION = visited[NOW];
// 현재 위치와 반대쪽
const OtherPos = POSITION === 1 ? -1 : 1;
// 간선을 보고 다음 간선 확인.
for (const NEXT of linesOBJ[NOW]) {
// 만약 두 간선의 정점이 같은 위치라면 종료.
if (visited[NEXT] === POSITION) {
return false;
}
// 아직 가지 않은 간선이라면, Queue에 삽입, visited 결정.
if (visited[NEXT] === 0) {
Queue.push(NEXT);
visited[NEXT] = OtherPos;
}
}
idx++;
}
return true;
};이제 모든 정점을 한번씩 확인하며 BFS 코드를 진행하면 테스트 케이스 한개가 완성된다.
전체적인 로직은 아래와 같이 구현했다.
- 연결리스트 형식으로 간선 저장.
- 연결리스트를 하나씩 확인하면서 아직
visited값이 0이라면BFS()진행. answer배열에 결과 추가.
1차 제출 코드
let fs = require("fs");
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const TESTCASE = parseInt(input.shift());
const BFS = (start, linesOBJ, visited) => {
// 시작 지점.
let Queue = [start];
// 시작 지점은 1로 초기화.
visited[start] = 1;
// while 문에서 매번 Queue.shift()를 쓰지 않기 위한 변수.
let idx = 0;
while (Queue.length > idx) {
const NOW = Queue[idx];
// 지금 위치
const POSITION = visited[NOW];
// 현재 위치와 반대쪽
const OtherPos = POSITION === 1 ? -1 : 1;
// 간선을 보고 다음 간선 확인.
for (const NEXT of linesOBJ[NOW]) {
// 만약 두 간선의 정점이 같은 위치라면 종료.
if (visited[NEXT] === POSITION) {
return false;
}
// 아직 가지 않은 간선이라면, Queue에 삽입, visited 결정.
if (visited[NEXT] === 0) {
Queue.push(NEXT);
visited[NEXT] = OtherPos;
}
}
idx++;
}
return true;
};
// 메인 함수.
const solution = () => {
let answer = [];
// 테스트 케이스
for (let i = 0; i < TESTCASE; i++) {
// [정점 수, 간선 수]
let [n, l] = input.shift().split(' ').map(Number);
let visited = new Array(n + 1).fill(0);
// 연결 리스트
let lines = {};
for (let j = 0; j < l; j++) {
const [Start, End] = input.shift().split(' ').map(Number);
lines[Start] = lines[Start] ? [...lines[Start], End] : [End];
lines[End] = lines[End] ? [...lines[End], Start] : [Start];
}
// 결과 저장할 변수.
let result = true;
// 간선이 있는 정점만 확인.
for (const linesKey in lines) {
for (const next of lines[linesKey]) {
// 만약 아직 확인하지 않은 점이라면.
if (visited[next] === 0) {
result = BFS(next, lines, visited);
if (!result) break;
}
}
if (!result) break;
}
// 결과 삽입.
answer.push(result ? 'YES' : 'NO');
}
// 결과 출력.
console.log(answer.join('\n'));
};
solution();
전체적인 로직은 문제가 없다고 생각했는데 시간 초과가 나게 된다.
조금씩 수정을 해봤지만 6%에서 바로 시간 초과가 나게 된다.
시간 초과가 난 것을 보고 가장 먼저 들었던 생각은 아래와 같았다.
- "BFS 함수 로직이 잘못되었나?"
- "
visited체크를 하지 않은 부분이 있어서 불필요한 과정이 들어가고 있나?"
따라서 다른 사람들의 코드를 확인하고 BFS 코드를 살펴봤는데 다른 코드와 시간 복잡도 차이가 나지 않는것 같아 보였다.
그래서 일단 solution 함수를 수정해보기로 했다.
- 입력 받는 부분의 .shift() 함수 제거.
lines[Start] = lines[Start] ? [...lines[Start], End] : [End];이 부분이 마음에 들지 않는다. 따라서 객체가 아닌 배열로 저장하기로 생각했다.
수정 후 solution 코드
const solution = () => {
let answer = [];
// .shift() 연산 대신 인덱스값 이용.
let index = 0;
for (let i = 0; i < TESTCASE; i++) {
const [n, l] = input[index++].split(' ').map(Number);
// 기존에 객체를 이용하던 것을 배열을 이용하도록 수정.
const graph = Array.from({ length: n + 1 }, () => []);
let visited = new Array(n + 1).fill(0);
for (let i = 0; i < l; i++) {
const [start, end] = input[index++].split(' ').map(Number);
// 매번 [...기존배열, 추가할 원소] 를 진행하면 O(n) 이지만, push() 함수는 0(1) 이다.
graph[start].push(end);
graph[end].push(start);
}
let result = true;
for (let i = 1; i <= n; i++) {
if (visited[i] === 0) {
if (!Check(i, graph, visited)) {
result = false;
break;
}
}
}
answer.push(result ? 'YES' : 'NO');
}
console.log(answer.join('\n'));
};이렇게 수정한 전체 코드는 아래와 같다.
통과 코드 (주석X)
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const TESTCASE = parseInt(input.shift());
const BFS = (start, linesOBJ, visited) => {
let Queue = [start];
visited[start] = 1;
let idx = 0;
while (Queue.length > idx) {
const NOW = Queue[idx];
const POSITION = visited[NOW];
const OtherPos = POSITION === 1 ? -1 : 1;
for (const NEXT of linesOBJ[NOW]) {
if (visited[NEXT] === POSITION) {
return false;
}
if (visited[NEXT] === 0) {
Queue.push(NEXT);
visited[NEXT] = OtherPos;
}
}
idx++;
}
return true;
};
const solution = () => {
let answer = [];
let index = 0;
for (let i = 0; i < TESTCASE; i++) {
const [n, l] = input[index++].split(' ').map(Number);
const graph = Array.from({ length: n + 1 }, () => []);
let visited = new Array(n + 1).fill(0);
for (let i = 0; i < l; i++) {
const [start, end] = input[index++].split(' ').map(Number);
graph[start].push(end);
graph[end].push(start);
}
let result = true;
for (let i = 1; i <= n; i++) {
if (visited[i] === 0) {
if (!BFS(i, graph, visited)) {
result = false;
break;
}
}
}
answer.push(result ? 'YES' : 'NO');
}
console.log(answer.join('\n'));
};
solution();
통과 후에 solution 함수 문제가 맞는지 확인을 위해 BFS 함수 수정 후에 다시 제출했다.
🧐 후기
입력을 shift() 함수를 통해 받는 것과 전개 구문 (...)을 이용하면 시간 복잡도가 O(n)이라는 것은 알았지만, BFS 함수에 너무 포커스를 맞추다 보니 다른 부분은 너무 가볍게 생각했던 것 같다.
조금 더 변명을 하자면, 전체 로직 부분이 아니라 저런 부분 때문에 시간 초과가 나게 될지 전혀 몰랐다.
앞으로는 좀 더 신경 써서 코드를 작성해야겠다.
JavaScript를 사용하는 모두를 위해...