이 글은 백준 1260번 DFS와 BFS를 풀이한다. Javascript를 이용해 알고리즘을 구현했다.
문제
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.
(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.
예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.
(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다.
예제 입력 1
2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5출력
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다
예제 출력 1
5
1풀이
접근
배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로, 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.
예시로 주어진 그림을 보고, 군데군데 모여있는 배추들이 여러 개의 이분 그래프를 이룬다는 사실을 알아냈다.
아래 그림처럼 입력으로 주어지는 배추의 위치에 1을, 나머지에 0을 이중 배열 형태(graph[r][c])로 저장하고, 각 그래프를 탐색하여 필요한 배추흰지렁이 마리 수를 파악해야겠다고 생각했다.
알고리즘
[1] 그래프 생성
배추의 위치를 이용해 그래프를 생성한다. 배열의 n번째 인덱스 요소가 n번째 행의 배추들로 이루어진 배열이 되도록 그래프 배열을 생성한다(graph[r][c]).
[2] 탐색
처음에는 깊이 우선 탐색 알고리즘으로 코드를 구현했으나, 채점을 돌리면 계속해서 런타임 에러가 발생하였다. 질문을 검색해보니, m(가로 길이)=50, n(세로 길이)=50, k(배추의 수)=2500일 때 재귀 깊이가 너무 깊어져(2500 이상) 런타임 에러가 발생한 것으로 추정된다. 그래서 너비 우선 탐색 알고리즘을 이용해 그래프들을 탐색했다.
배추의 위치들을 다 방문하기 전까지 방문하지 않은 배추의 위치를 찾는다. 만약 배추가 존재하면 해당 위치를 bfs 함수의 인자로 넘겨 호출한다. 다음은 이 알고리즘의 수도 코드이다.
while(true){
for(i=0; i<rowCount; i++){
j = i행에서의 방문하지 않은 배추의 열 위치;
if(i행의 배추 다 방문한 상태){
continue;
}
r=i, c=j;
break;
}
if(배추 다 방문한 상태) break;
(필요한 벌레 수)++;
bfs(r, c);
}
const bfs = (시작 정점) => {
const 방문할 정점 큐 = [시작 정점];
while(방문할 정점 큐에 요소가 없어질 때까지){
현재 정점=큐에서 첫 번째 요소를 pop;
현재 정점 방문 사실 저장;
인접한 정점 중 방문하지 않은 정점을 큐에 삽입;
}
};
구현
코드 (아래 설명 있음)
const input = [];
let inputIndex = 0;
const distances = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let graph, columnCount, rowCount, cabbageCount, result=0;
const strToNumArr = (str) => str.split(" ").map((numString) => Number(numString));
require("readline")
.createInterface(process.stdin, process.stdout)
.on("line", function (line) {
input.push(line.trim());
})
.on("close", function () {
let t = Number(input[inputIndex++]);
while(t--){
[columnCount, rowCount, cabbageCount] = strToNumArr(input[inputIndex++]);
graph = [...Array(rowCount)].map(()=>Array(columnCount).fill(0));
result = 0;
while(cabbageCount--){
const [c, r] = strToNumArr(input[inputIndex++]);
graph[r][c] = 1;
}
while(true){
let r, c;
for(let i=0; i<rowCount; i++){
const j = graph[i].indexOf(1);
if(j===-1){
continue;
}
r=i, c=j;
break;
}
if(r===undefined && c===undefined) break;
result++;
bfs(r, c);
}
console.log(result);
}
});
const bfs = (rStart, cStart) => {
const queue = [[rStart, cStart]];
let currentR, currentC, r, c;
while(queue.length!==0){
[currentR, currentC]=queue.shift();
if(!graph[currentR][currentC]){
continue;
}
graph[currentR][currentC]=0;
distances.forEach(([dr, dc])=>{
r=currentR+dr;
c=currentC+dc;
if(r<0 || r>=rowCount || c<0 || c>=columnCount){
return;
}
if(graph[r][c]){
queue.push([r, c]);
}
});
}
};
코드+설명
const input = [];
let inputIndex = 0;
//상, 하, 좌, 우
const distances = [[-1, 0], [1, 0], [0, -1], [0, 1]];
//그래프 이중 배열, 가로 길이(열 개수), 세로 길이(행 개수), 배추 개수, 결과 담는 변수
let graph, columnCount, rowCount, cabbageCount, result;
const strToNumArr = (str) => str.split(" ").map((numString) => Number(numString));
require("readline")
.createInterface(process.stdin, process.stdout)
.on("line", function (line) {
input.push(line.trim());
})
.on("close", function () {
let t = Number(input[inputIndex++]);
//테스트 케이스 수만큼
while(t--){
[columnCount, rowCount, cabbageCount] = strToNumArr(input[inputIndex++]);
//그래프 초기화
graph = [...Array(rowCount)].map(()=>Array(columnCount).fill(0));
//결과(필요한 벌레 수) 담는 변수 초기화
result = 0;
//배추 있는 위치 그래프에 표시
while(cabbageCount--){
const [c, r] = strToNumArr(input[inputIndex++]);
graph[r][c] = 1;
}
while(true){
let r, c;
//그래프 돌면서 방문하지 않은 배추 위치 알아내기
for(let i=0; i<rowCount; i++){
const j = graph[i].indexOf(1);
//없으면 계속
if(j===-1){
continue;
}
//있으면 해당 위치 저장하고 break
r=i, c=j;
break;
}
//방문하지 않은 배추 없으면 break
if(r===undefined && c===undefined) break;
//필요한 벌레 수+1
result++;
//인접한 배추 방문
bfs(r, c);
}
console.log(result);
}
});
//너비 우선 탐색으로 인접한 배추 방문
const bfs = (rStart, cStart) => {
//방문할 배추 위치 담는 큐
const queue = [[rStart, cStart]];
let currentR, currentC, r, c;
//큐가 비기 전까지
while(queue.length!==0){
//첫 원소 pop
[currentR, currentC]=queue.shift();
//이미 방문했으면 continue
if(!graph[currentR][currentC]){
continue;
}
//배추 방문 사실 저장
graph[currentR][currentC]=0;
//인접한 정점 중 방문하지 않은 정점 큐에 삽입
distances.forEach(([dr, dc])=>{
r=currentR+dr;
c=currentC+dc;
if(r<0 || r>=rowCount || c<0 || c>=columnCount){
return;
}
if(graph[r][c]){
queue.push([r, c]);
}
});
}
};
'Algorithm' 카테고리의 다른 글
| [Algorithm] 백준 6549 히스토그램에서 가장 큰 직사각형 - node.js (0) | 2021.02.05 |
|---|---|
| [Algorithm] 조합(nCr)의 모든 경우를 구하는 방법(c++, javascript) (0) | 2021.01.30 |
| [Javascript] 백준 2606번 바이러스 - node.js (0) | 2020.12.23 |
| [Javascript] 백준 1260번 DFS와 BFS - node.js (0) | 2020.12.18 |
| [Algorithm] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) - 그래프 탐색 알고리즘 (0) | 2020.12.17 |
