3. 이분 그래프(1707)
문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
작성한 코드
class Queue {
constructor() {
this.items = {};
this.headIndex = 0;
this.tailIndex = 0;
}
enqueue(item) {
this.items[this.tailIndex] = item;
this.tailIndex++;
}
dequeue() {
let item = this.items[this.headIndex];
delete this.items[this.headIndex];
this.headIndex++;
return item;
}
peek() {
return this.items[this.headIndex];
}
getLength() {
return this.tailIndex - this.headIndex;
}
}
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let tc = Number(input[0]); // 테스트 케이스 개수
let line = 1;
while (tc--) {
// 정점의 개수(V), 간선의 개수(E)
let [v, e] = input[line].split(" ").map(Number);
// 그래프 정보 입력받기
let graph = [];
for (let i = 1; i <= v; i++) graph[i] = [];
for (let i = 1; i <= e; i++) {
let [u, v] = input[line + i].split(" ").map(Number);
graph[u].push([v]);
graph[v].push([u]);
}
let visited = new Array(v + 1).fill(-1); // 방문 정보
// BFS를 이용해 색칠
for (let i = 1; i <= v; i++) {
if (visited[i] == -1) bfs(i, graph, visited);
}
line += e + 1; // 다음 테스트 케이스로 이동
if (isBipartite(graph, visited)) console.log("YES");
else console.log("NO");
}
// 미방문(color: -1), 빨강(color: 0), 파랑(color: 1)
function bfs(x, graph, visited) {
queue = new Queue();
queue.enqueue(x);
visited[x] = 0; // 처음 노드는 빨간색으로 색칠
while (queue.getLength() != 0) {
x = queue.dequeue();
for (let y of graph[x]) {
if (visited[y] == -1) {
visited[y] = (visited[x] + 1) % 2; // 빨강 <-> 파랑
queue.enqueue(y);
}
}
}
}
function isBipartite(graph, visited) {
for (let x = 1; x < visited.length; x++) {
for (let y of graph[x]) if (visited[x] == visited[y]) return false;
}
return true;
}풀이
- 이분 그래프는 노드들을 두 개의 집합으로 분할한 뒤, 같은 집합에 속한 정점끼리 서로 인접하지 않는 그래프를 의미
- 풀이 방법
- 아직 방문하지 않은 각 노드에서 시작하여 BFS로 인접노드로 이동하며 빨 → 파 → 빨 → 파 … 색칠
- 이분 그래프 판별: 모든 노드에 대하여 인접 노드와 색상이 다른지 여부 판별
- Stack Size 초과로 DFS 해결 불가능
4. 4연산(14395)
문제
정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.
사용할 수 있는 연산은 아래와 같다.
s = s + s; (출력: +)s = s - s; (출력: -)s = s * s; (출력: *)s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)
입력
첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)
출력
첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.
연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.
작성한 코드
class Queue {
constructor() {
this.items = {};
this.headIndex = 0;
this.tailIndex = 0;
}
enqueue(item) {
this.items[this.tailIndex] = item;
this.tailIndex++;
}
dequeue() {
const item = this.items[this.headIndex];
delete this.items[this.headIndex];
this.headIndex++;
return item;
}
peek() {
return this.items[this.headIndex];
}
getLength() {
return this.tailIndex - this.headIndex;
}
}
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [s, t] = input[0].split(" ").map(Number);
// 너비 우선 탐색(BFS) 수행
let queue = new Queue();
// (값, 해당 값을 만들기 위한 연산자) 삽입
queue.enqueue([s, ""]);
let visited = new Set([s]);
let found = false;
// 시작 값과 목표 값이 같은 경우
if (s == t) {
console.log(0);
process.exit();
}
while (queue.getLength() != 0) {
let [value, opers] = queue.dequeue();
if (value > 1e9) continue; // 값의 범위를 벗어나느 경우
// 목표 값에 도달한 경우
if (value == t) {
console.log(opers); // 전체 연산자들 출력
found = true;
break;
}
for (let oper of ["*", "+", "-", "/"]) {
let nextValue = value;
if (oper == "*") nextValue *= value;
if (oper == "+") nextValue += value;
if (oper == "-") nextValue -= value;
if (oper == "/" && value != 0) nextValue = 1;
if (!visited.has(nextValue)) {
queue.enqueue([nextValue, opers + oper]);
visited.add(nextValue);
}
}
}
// 바꿀 수 없는 경우
if (!found) console.log(-1);풀이
- BFS는 최단 거리를 찾거나 최소 횟수 찾는 문제에서 많이 사용됨
- 특정한 정수 s에서 시작해서 “탐색”하는 형태로 간주 → t인 노드 만날때까지 BFS 수행
- 최소 연산 횟수를 구하는 문제
