유기농 배추
문제
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.
(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.
예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 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예제 입력 2
1 5 3 6 0 2 1 2 2 2 3 2 4 2 4 0예제 출력 2
2출처
- 문제를 만든 사람: author2
- 빠진 조건을 찾은 사람: jinsj1
알고리즘 분류
- BFS
- DFS
해결한 코드
function b1012() {
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');
var t = parseInt(input[0])
input.shift() // 테스트케이스 갯수 정보 삭제
var count = 0
var i = 1
var answer = []
while(t !== count){
var testCaseInfo = input[i-1].split(' ')
var m = parseInt(testCaseInfo[0]) // 가로 길이
var n = parseInt(testCaseInfo[1]) // 세로 길이
var k = parseInt(testCaseInfo[2]) // 배추가 심어진 위치의 갯수
var cabbageLocation = []
for(var c = i; c<k+i; c++){
var temp = input[c].split(' ').map((element)=> element/1)
var y = temp[0]
var x = temp[1]
cabbageLocation.push({y: y, x: x, visit: false})
}
var result = []
for(var l = 0; l < cabbageLocation.length; l++){
if(cabbageLocation[l].visit === false){
var startV = cabbageLocation[l]
result.push(bfs(cabbageLocation, startV, n, m))
}
}
answer.push(result.length)
i += k+1 // 다음 테스트케이스를 위해 인덱스 조정
count++ // 테스트케이스를 모두 계산하면 반복문을 종료하기 위해 count 세어주기
}
for(var i=0; i<answer.length; i++){
console.log(answer[i])
}
}
function bfs(cabbageLocation, startV, n, m){
var q = []
var result = []
startV.visit = true
q.push(startV)
while(q.length !== 0){
var current = q.shift()
result.push(current)
var dy = [-1, 1, 0, 0]
var dx = [0, 0, -1, 1]
for(var i=0; i<4; i++){
var a = current.y + dy[i]
var b = current.x + dx[i]
if((a >= 0 && a < m) && (b >= 0 && b < n)){
if(cabbageLocation.some((element)=> element.y === a && element.x === b && element.visit === false)){
var index = cabbageLocation.findIndex((element)=> element.y === a && element.x === b && element.visit === false)
var next = cabbageLocation[index]
next.visit = true
q.push(next)
}
}
}
}
return result
}
b1012()알고리즘
※ dfs로도 풀 수 있지만, 나는 bfs로 풀었다.
📍 여러 개의 테스트케이스가 한번에 입력될 수 있다.
각 테스트케이스별로 답을 출력해야 하니까... (나는) 반목문을 사용했다.
테스트케이스 별로 입력되는 m, n, k값이 다르므로 이를 위한 작업을 해주어야 한다.1. 배추가 심어진 위치와 방문 여부에 대한 정보를 모은다.
즉, 배추가 심어진 위치의 정보가
[1, 0]이라면,cabbageLocation = [ {y: 1, x: 0, visit: false} ]이런식으로 object의 형태로 저장했다.
(※ 참고로 y는 각 열(가로), x는 각 행(세로)에 대한 정보이다.)2. bfs를 구현한다.
bfs를 구현하기 위해 필요한 것은?
✔ bfs를 시작할 정점
✔ 방문 여부를 체크할 visit
✔ 순회한 정점을 저장할 result
✔ 다음 순회 정점을 위한 큐2-1. cabbageLocation의 첫번째 원소부터 bfs를 시작한다.
- 첫번째 원소를 방문하였으니, 해당 원소의 visit값을 true로 바꾼다.
- 방문한 원소를 큐에 넣는다.
2-2. 큐에 들어간 첫번째 원소를 순회한다.
- 순회하고 있는 정점을 result에 넣는다.
- 순회하고 있는 정점과 상하좌우로 붙어있는 정점을 탐색한다.
👉🏻 dx, dy를 만들어 상하좌우를 탐색할 수 있다.dy = [-1, 1, 0, 0] dx = [0, 0, -1, 1]
- 만약, 상하좌우에 붙어있는 정점이 cabbageLocation에 있다면
👉🏻 ex. 현재 정점이{y: 1, x: 0, visit: true}라면,y = 1 x = 0 dy[0] = -1, dx[0] = 0 y + dy[0] = 0, x + dx[0] = 0cabbageLocation에
{y: 1, x: 0, visit: false}인 원소가 있나?
- if (있으면) : visit을 true로 바꾸고 큐에 넣기 !
- else (없으면) : y, x값에 dy[1], dx[1]을 더해보고 visit이 false인 원소가 있는지 탐색하기
(만약 끝까지 없으면) 그대로 넘어간다...2-3. (큐가 비어있지 않다면) 큐에 저장된 첫번째 원소를 꺼내 순회한다.
- 해당 원소를 순회하고 있으니 result에 넣는다.
- 순회하고 있는 해당 원소와 상하좌우로 붙어있는 정점을 탐색한다.
👉🏻 위 과정을 큐가 빌때까지 반복한다.
2-4. 큐가 비면, 방문할 수 있는 모든 정점을 방문한 것이므로 순회한 결과가 담긴 result를 반환한다.
3. bfs로 반환된 result 배열의 길이를 새로운 배열에 저장한다.
이 새로운 배열은 최종 답을 출력할 때 사용할 것
(나는 새로운 배열 이름을 answer라고 붙였다.)4. 첫번째 테스트케이스가 끝났으니, 다음 테스트케이스를 돌리기 위한 작업을 한다.
4-1. 다음 테스트케이스의 m, n, k값에 대한 정보가 어디있는지 계산해야 한다.
- 이전 테스트케이스의 m, n, k값에 대한 정보는 인덱스 1의 자리에 있었다.
- 그런 후 k개의 배추가 심어진 위치에 대한 정보들이 나오고, 그 다음에야 다음 테스트케이스의 정보가 나온다.
👉🏻 다음 테스트케이스의 m, n, k값에 대한 정보는 이전 테스트케이스의 인덱스 + k를 한 자리에 있다.
👉🏻 다음 테스트케이스의 배추가 심어진 위치 정보들은 이전 테스트케이스의 인덱스 + k + 1을 한 자리에 있다.
(※ 참고로 나는 계산이 헷갈려서 테스트케이스가 몇개인지 확인한 후, 입력으로 받아오는 배열에서 테스트케이스 갯수의 원소를 shift로 빼버렸다... 이로서 첫번째 테케 정보의 위치는 인덱스 0...)4-2. 다음 테스트케이스를 정상적으로 돌릴 수 있도록 인덱스 값을 계산해 반복문을 이어간다.
- 새로운 테스트케이스로 위 과정을 반복하면 되는 것
- 각 테스트케이스별로 bfs한 결과 값들을 answer에 저장한다.
5. 반복문이 끝나면, answer에 담긴 배열 원소의 개수를 차례로 출력한다.
