- 지난 게시물에서 그래프와 그래프 순회에 대한 강의를 듣고 내용을 정리하여 포스팅했었다.
- 이번에는 강의 내용을 활용하여 풀었던 문제들을 짧게 공유한다.
- 문제들은 대부분 백준 문제집의 DFS+BFS 필수 문제 에 속한 문제들이다.
백준 2178번
이차원 배열 형태의 미로를 탐색하며, 출발점부터 도착점까지의 최소 거리를 구하는 문제이다. BFS/DFS 문제를 제대로 푸는게 처음이라, 공부한 개념을 적용하기 조금 어려웠는데 다음과 같이 풀었다.
- BFS로, 시작점(0, 0)에서부터 순회를 시작한다.
- 미로는 길이 존재하고, 현재 접점과 인접한 사방의 접점으로만 진행할 수 있다. 따라서 순회 시 이를 전부 체크한다.
- 위의 조건을 만족하며 아직 방문하지 않은 인접점은 방문 처리 후 BFS 탐색 큐에 넣어줌으로써, 다음 반복 때 탐색할 수 있게 한다.
- 3번에서의 방문 처리 시, '해당 인접점 바로 직전의 접점(현재 접점)까지의 최소거리 + 1'을 기록한다. → 각 접점까지의 최소거리를 기록하고, 최종적으로는 목표인 도착점까지의 최소거리를 도출하기 위해서다.
최종적으로 구현한 코드는 아래와 같다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
const board = [];
rl.on("line", (line) => {
input.push(line);
}).on("close", function () {
const [n, m] = input[0].split(" ").map((el) => parseInt(el));
input.slice(1).forEach((str) => {
board.push(str.split("").map((el) => parseInt(el)));
});
const visited = new Array(n); // 방문 여부 배열
for (let i = 0; i < visited.length; i++) {
const newArr = new Array(m);
visited[i] = newArr.fill(0);
}
let queue = [[0, 0]];
visited[0][0] = 1;
while (queue.length > 0) {
const [row, col] = queue.shift();
if (row + 1 < n && board[row + 1][col] === 1) {
if (!visited[row + 1][col]) {
visited[row + 1][col] = visited[row][col] + 1;
queue.push([row + 1, col]);
}
}
if (col + 1 < m && board[row][col + 1] === 1) {
if (!visited[row][col + 1]) {
visited[row][col + 1] = visited[row][col] + 1;
queue.push([row, col + 1]);
}
}
if (col - 1 >= 0 && board[row][col - 1] === 1) {
if (!visited[row][col - 1]) {
visited[row][col - 1] = visited[row][col] + 1;
queue.push([row, col - 1]);
}
}
if (row - 1 >= 0 && board[row - 1][col] === 1) {
if (!visited[row - 1][col]) {
visited[row - 1][col] = visited[row][col] + 1;
queue.push([row - 1, col]);
}
}
}
console.log(visited[n - 1][m - 1]);
process.exit();
});
순회까지는 떠올렸지만 최소 거리를 어떻게 도출해야할지 고민하다, 다른 분들의 게시물을 참고하며 적용했다. 조금 알아보니 BFS가 이런 종류의 최단 거리 탐색에 잘 쓰이는 듯 하다.
백준 2606번
컴퓨터와 각 컴퓨터 간의 연결 관계가 주어지고, 1번 컴퓨터가 바이러스에 걸렸다고 했을 때 최종적으로 바이러스에 감염되는 컴퓨터의 총 개수를 구하는 문제. 그림을 보자마자 강의에서 배웠던 그래프 구현을 활용할 수 있겠다! 싶어서 금방 풀 수 있었다.
풀이에는 다음과 같은 과정을 거쳤다.
- 주어진 컴퓨터 수(== 정점 수), 각 컴퓨터 간의 연결 관계(== 간선) 정보를 이용해 그래프를 만든다.
- 만든 그래프를 BFS/DFS를 사용하여 순회한다. 바이러스에 걸린 컴퓨터는 1번 컴퓨터이므로, 1번 접점에서부터 탐색을 시작하며 1번과 연결된 컴퓨터의 수를 구한다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
// 그래프 구현 클래스
class Graph {
constructor(num) {
this.adjacencyList = {}; // 간선 정보를 담은 인접 리스트
for (let i = 1; i <= num; i++) {
this.adjacencyList[i] = [];
}
}
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
startDfs() { // DFS를 사용해 순회
let visited = {};
const adjacencyList = this.adjacencyList;
const result = [];
const dfs = (v) => {
if (v == null) return null;
result.push(v);
visited[v] = true;
for (let el of adjacencyList[v]) {
if (!visited[el]) {
dfs(el);
}
}
};
dfs(1);
return result.length;
}
}
rl.on("line", (line) => {
input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
const computers = input.shift();
const graph = new Graph(computers);
for (let i = 1; i < input.length; i++) {
const [v1, v2] = input[i];
graph.addEdge(v1, v2);
}
const result = graph.startDfs();
console.log(result - 1); // 결과 배열에 시작점인 1번 접점이 들어가므로, 1을 빼준다
process.exit();
});
강의에서 들은 내용을 사용해서 금방 구현할 수 있어서 손쉽게 푼 문제였다. 공부한 것을 활용할 기회가 된 것 같아 좋기도 했다.
백준 2644번
위의 바이러스 문제와 비슷한 형태로, 가족들(정점)과 그 사이 부모자식 관계(간선)가 주어지고 주어진 두 사람의 촌수를 구하는 문제. 촌수는 간단히 생각해서 촌수를 구하고자 하는 두 사람 간의 거리(혹은 간선의 개수)이다. 따라서 주어진 두 사람 중 한 명을 시작 접점으로 하여 그래프를 순회하고, 다른 한 사람을 찾으면 거리를 반환/찾지 못했다면 -1을 출력한다. 두 사람 간의 거리를 구하는 것에는 맨 위의 2178번 미로탐색 문제에서 배운 것을 응용해, 시작점부터 각 접점까지의 최소 거리를 저장하는 방식으로 구하였다.
다음과 같은 과정을 거쳤다.
- 바이러스 문제와 똑같이, 주어진 가족들(== 정점)과 부모자식 관계(== 간선)를 이용해 그래프를 만든다.
- 주어진 시작 접점에서 순회를 시작한다. 여기서는 BFS를 사용하였다. 현재 접점의 아직 방문하지 않은 인접점을 방문 처리할 때 (현재 접점까지의 거리 + 1)를 기록함으로써 최종적으로 목표 접점까지의 거리를 구한다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
class Graph {
constructor(num) {
this.adjacencyList = {};
for (let i = 1; i <= num; i++) {
this.adjacencyList[i] = [];
}
}
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
startBfs(start, target) {
let visited = {};
const queue = [start];
const adjacencyList = this.adjacencyList;
visited[start] = 1;
while (queue.length > 0) {
const currentVertex = queue.shift();
if (currentVertex === target) {
break;
}
adjacencyList[currentVertex].forEach((v) => {
if (!visited[v]) {
queue.push(v);
visited[v] = visited[currentVertex] + 1;
}
});
}
return visited[target];
}
}
rl.on("line", (line) => {
input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
const people = input.shift();
const [start, target] = input.shift();
const graph = new Graph(people);
for (let i = 1; i < input.length; i++) {
const [v1, v2] = input[i];
graph.addEdge(v1, v2);
}
const result = graph.startBfs(start, target);
console.log(result ? result - 1 : -1);
process.exit();
});
미로탐색 문제를 풀지 않았으면 여기서도 거리를 어떻게 기록해야할지 고민하는데 시간을 좀 썼을 것 같았다. 다행히 전에 푼 문제가 도움이 되어 그리 오랜 시간을 들이지 않고 푸는 데 성공했던 것 같다.
백준 5014번
각각 특정 층수 밖에 올라가지/내려가지 못하는 엘리베이터를 몇 번 사용해야 목표한 층수로 갈 수 있는지를 구하는 문제이다. 처음엔 '엘리베이터'라는 특징 때문에, 그래프보다는 배열의 느낌이 더 짙게 나서 이걸 어떻게 그래프로 생각해야 할지 헷갈렸었다. 조금 더 생각해보니 의외로 금방 그래프로 표시할 수 있음을 알 수 있었다.
엘리베이터가 A층만큼 올라갈 수 있고, B층만큼 내려갈 수 있다고 가정한다. 각 층을 그래프의 정점이라고 한다면, 한 층과 간선으로 연결된 층은 그 층보다 A층 높은 층 + B층 낮은 층이다.
아래는 이 문제의 예제 케이스를 그래프로 그린 것이다. 엘리베이터는 위/아래의 방향을 갖고 있으므로, 그래프 또한 방향 그래프의 형태로 나타난다. 빨간 선은 이 케이스에서 시작점(1층)에서 도착점(10층)까지 엘리베이터를 타는 방법을 나타낸 것이다. 결론적으로, 그래프를 그리고 시작점부터 도착점까지의 거리를 구하면 된다.
해결방안은 촌수 문제와 똑같으므로, 코드 또한 거의 똑같다. 다른 곳이라면 도착할 수 있는 방법이 없을 경우 텍스트를 출력하는 것 뿐이다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
class Graph {
constructor(num) {
this.adjacencyList = {};
for (let i = 1; i <= num; i++) {
this.adjacencyList[i] = [];
}
}
addEdges(up, down) {
const max = Object.keys(this.adjacencyList).length;
for (let i = 1; i <= max; i++) {
if (i - down >= 1) {
this.adjacencyList[i].push(i - down);
}
if (i + up <= max) {
this.adjacencyList[i].push(i + up);
}
}
}
startBFS(start, goal) {
const queue = [start];
const visited = {};
visited[start] = 0;
const adjacencyList = this.adjacencyList;
while (queue.length > 0) {
const current = queue.shift();
if (current === goal) {
break;
}
adjacencyList[current].forEach((v) => {
if (!visited[v] && visited[v] !== 0) {
visited[v] = visited[current] + 1;
queue.push(v);
}
});
console.log(visited);
}
return visited[goal];
}
}
rl.on("line", (line) => {
input = line.split(" ").map((el) => parseInt(el));
}).on("close", function () {
const [floor, start, goal, upStairs, downStairs] = input;
const graph = new Graph(floor);
graph.addEdges(upStairs, downStairs);
const result = graph.startBFS(start, goal);
console.log(result == null ? "use the stairs" : result);
process.exit();
});
백준 2667번
주어진 지도에서 서로 붙어있는 단지들이 몇 개인지 + 각 단지에 몇 개의 집이 있는지를 구하는 문제. 단지를 한 개의 그래프라고 생각하면, 복수의 그래프를 탐색하는 문제라고도 해석할 수 있다. 즉, 그래프 순회를 여러 번 행한다는 것이다.
따라서 지도 정보가 담긴 이차원 배열을 순회하며, 아직 방문하지 않은(== 순회하지 않은) 집이 나오면 그래프 순회를 시작한다.
코드는 다음과 같은 로직으로 짜였다.
- 지도의 시작지점(0, 0)에서부터 순회를 시작한다.
- 현재 위치에 집이 존재하고, 아직 방문하지 않은 집일 경우 그래프 순회를 시작한다. 단지를 이룰 조건은 좌우 혹은 상하로 붙어있어야 한다는 것이므로, 현재 정점의 사방을 살펴야 한다. 이 때, 각 단지 내 집의 개수를 기록할 변수를 생성하여 1로 초기화해둔다(시작점을 포함해야 함으로).
- 현재 정점의 사방에 인접점(집)이 존재할 때마다 변수를 1 증가시키고, 순회 큐에 넣는다. 탐색이 끝나면 결과 배열에 단지 내 집 개수를 넣는다.
- 지도의 순회가 모두 끝나면 결과 배열의 길이 + 배열의 내용물을 출력한다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on("line", (line) => {
input.push(line);
}).on("close", function () {
const board = [];
const n = parseInt(input.shift());
input.forEach((str) => {
board.push(str.split("").map((el) => parseInt(el)));
});
const visited = [];
for (let i = 0; i < n; i++) {
const newArr = new Array(n);
visited.push(newArr.fill(false));
}
let queue = [];
const answer = [];
let num = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (!visited[i][j] && board[i][j]) {
queue = [[i, j]];
visited[i][j] = true;
num = board[i][j];
while (queue.length > 0) {
const [currentX, currentY] = queue.shift();
if (currentY + 1 < n) {
if (
board[currentX][currentY + 1] &&
!visited[currentX][currentY + 1]
) {
visited[currentX][currentY + 1] = true;
num++;
queue.push([currentX, currentY + 1]);
}
}
if (currentX + 1 < n) {
if (
board[currentX + 1][currentY] &&
!visited[currentX + 1][currentY]
) {
visited[currentX + 1][currentY] = true;
num++;
queue.push([currentX + 1, currentY]);
}
}
if (currentY - 1 >= 0) {
if (
board[currentX][currentY - 1] &&
!visited[currentX][currentY - 1]
) {
visited[currentX][currentY - 1] = true;
num++;
queue.push([currentX, currentY - 1]);
}
}
if (currentX - 1 >= 0) {
if (
board[currentX - 1][currentY] &&
!visited[currentX - 1][currentY]
) {
visited[currentX - 1][currentY] = true;
num++;
queue.push([currentX - 1, currentY]);
}
}
}
if (num > 0) {
answer.push(num);
}
}
}
}
console.log(answer.length);
console.log(
answer
.sort((a, b) => a - b)
.join("\n")
.trim()
);
process.exit();
});
처음에 현재 정점이 "방문하지 않은 >>집<<이면 그래프 순회를 시작한다" 조건을 추가하는 걸 까먹어서 + 순회를 시작하는 정점을 방문처리 하지 않아서 틀렸었다^^; 몇 번 테스트 예제를 돌리고 문제를 찾아내 무사히 정답 처리되었다.
'공부 > 알고리즘' 카테고리의 다른 글
| 문자열 문제 풀이 (0) | 2023.12.11 |
|---|---|
| 구현 문제 풀이 (1) | 2023.12.04 |
| 그래프 + 그래프 순회 정리 (0) | 2023.11.17 |
| 유클리드 호제법 (1) | 2023.10.29 |
| 백준에서 JS로 문제 풀이하기 + 이런저런 메모(+추가: 2023.11.22) (3) | 2023.10.23 |
