단지번호붙이기
문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0 혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
예제 입력 1
7 0110100 0110101 1110101 0000111 0100000 0111110 0111000예제 출력 1
3 7 8 9출처
Olympiad > 한국정보올림피아드 > KOI 1996 > 초등부 1번
- 잘못된 데이터를 찾은 사람: djm03178
- 데이터를 추가한 사람: djm03178 jh05013
- 문제의 오타를 찾은 사람: metadata
알고리즘 분류
- BFS
- DFS
1. DFS - 스택
해결한 코드
function b2667() {
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 n = parseInt(input[0])
var group = []
for (var i = 1; i < input.length; i++) {
group.push(input[i].split('').map(e => e = e / 1))
}
var homes = isHome(group)
var result = []
for (var i = 0; i < homes.length; i++) {
if (homes[i].visit == false) {
var startV = homes[i]
result.push(dfs(homes, startV, n))
}
}
result.sort((a,b)=>a-b)
console.log(result.length)
for(var i=0; i<result.length; i++){
console.log(result[i])
}
}
function dfs(homes, startV, n) {
var stack = []
var result = []
startV.visit = true
stack.push(startV)
result.push(startV)
while (stack.length !== 0) {
var current = stack[stack.length - 1]
var flag = false
var dx = [-1, 1, 0, 0]
var dy = [0, 0, -1, 1]
for (var i = 0; i < 4; i++) {
var a = current.x + dx[i]
var b = current.y + dy[i]
if ((a >= 0 && a < n) && (b >= 0 && b < n)) {
if (homes.some(e => e.x == a && e.y == b && e.visit == false)) {
var idx = homes.findIndex(e => e.x == a && e.y == b && e.visit == false)
var next = homes[idx]
next.visit = true
stack.push(next)
result.push(next)
flag = true
break
}
}
}
if (!flag) {
stack.pop()
}
}
return result.length
}
function isHome(group) {
var result = []
for (var i = 0; i < group.length; i++) {
for (var j = 0; j < group.length; j++) {
if (group[i][j] == 1) result.push({
x: i,
y: j,
visit: false
})
}
}
return result
}
b2667()알고리즘
※ DFS - 스택 방식으로 풀었다.
1. 입력으로 오는 전체 좌표에서 집이 있는 좌표만 골라낸다.
집이 있는 곳 = 1
따라서, 만약 입력값으로[ [ 0, 1, 1, 0, 1, 0, 0 ], [ 0, 1, 1, 0, 1, 0, 1 ], [ 1, 1, 1, 0, 1, 0, 1 ], [ 0, 0, 0, 0, 1, 1, 1 ], [ 0, 1, 0, 0, 0, 0, 0 ], [ 0, 1, 1, 1, 1, 1, 0 ], [ 0, 1, 1, 1, 0, 0, 0 ] ]이렇게 들어왔다면, 값이 1인 것들만 모아놓는 것이다.
단, 이때 방문 여부도 같이 저장했다.
👉🏻 이를 위해 object 형태로 저장했다.
※ 참고로 x는 행, y는 열의 인덱스 번호이다.
(x는 세로, y는 가로 줄의 인덱스를 저장했다.)homes = [ { x: 0, y: 1, visit: false }, { x: 0, y: 2, visit: false }, { x: 0, y: 4, visit: false }, { x: 1, y: 1, visit: false }, { x: 1, y: 2, visit: false }, { x: 1, y: 4, visit: false }, { x: 1, y: 6, visit: false }, { x: 2, y: 0, visit: false }, { x: 2, y: 1, visit: false }, { x: 2, y: 2, visit: false }, { x: 2, y: 4, visit: false }, { x: 2, y: 6, visit: false }, { x: 3, y: 4, visit: false }, { x: 3, y: 5, visit: false }, { x: 3, y: 6, visit: false }, { x: 4, y: 1, visit: false }, { x: 5, y: 1, visit: false }, { x: 5, y: 2, visit: false }, { x: 5, y: 3, visit: false }, { x: 5, y: 4, visit: false }, { x: 5, y: 5, visit: false }, { x: 6, y: 1, visit: false }, { x: 6, y: 2, visit: false }, { x: 6, y: 3, visit: false } ]현재 방문하지 않았으니 visit 값은 false로 저장한다.
2. dfs를 구현한다.
우선 dfs를 위해 필요한 것은?
✔ 방문한 정점을 담을 스택
✔ 탐색한 정점을 담을 result2-1. 그럼 dfs를 시작할 정점을 어떻게 정할까?
📍 시작할 정점의 조건은
✔ homes의 원소여야 한다.
✔ visit은 false여야 한다.
👉🏻 따라서 homes에 저장된 순서대로 visit이 false인 원소부터 dfs를 시작한다.2-2. 시작한 정점으로부터 어떻게 dfs로 탐색할 수 있는가?
즉, 다음으로 탐색할 정점을 어떻게 선택해야 하는가가 문제였다.
📍 단지가 만들어지려면
✔ 현재 탐색하고 있는 정점과 상하좌우로 붙어있어야 한다.
✔ visit이 false여야 한다.
👉🏻 dx, dy를 만들어 상하좌우를 탐색하고, 해당 값이 false인 정점을 찾는다.dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]현재 정점의 [x, y] 값에서 + [-1, 0] or + [1, 0] or + [0, -1] or + [0, 1] 한 값이 homes안에 있으면,
그 값을 찾아 다음으로 탐색한다.ex. homes의 첫번째 원소 { x: 0, y: 1, visit: false }를 예로 들면,
- 방문했으니까 visit = true
- x = 0 y = 1 일때 + [1, 0] 하면, x = 1, y = 1
근데 homes에{ x: 1, y: 1, visit: false }인 값이 있다 !
👉🏻 다음으로 탐색할 정점은{ x: 1, y: 1, visit: false }이 된다 !🙋🏻♀️ 주의 !! dfs는 "깊이탐색"이다. 따라서, 해당 정점 1개를 찾았으면, 바로 break를 걸어주어야 한다.
2-3. 방문한 정점의 visit값을 true로 해준다.
방문한 정점을 다시 들리지 않기 위해서다.
ex.{ x: 1, y: 1, visit: true }2-4. 정점을 방문하면 result 배열에 해당 정점을 넣는다.
result = [ { x: 0, y: 1, visit: true }, { x: 1, y: 1, visit: true } ]2-5. 정점을 방문하면 stack에도 넣는다.
만약, 상하좌우로 다 탐색을 했는데 주변 정점들의 visit값이 모두 true이면, stack을 pop한다.
(참고) DFS - 스택
✔ stack에서 pop한 정점을 상하좌우로 탐색하며 방문하지 않은 집이 있는지 확인 !!2-6. 이렇게 위 과정을 반복하여 주변에 있는 모든 정점을 방문하면, result 배열의 길이를 return한다.
궁극적으로 단지 내 집이 몇개인지 구해야 하기 때문이다.2-7. 그리고 다음 dfs를 시작한다.
ex. 첫번째 원소에 대하여 dfs를 하고 오면,homes = [ { x: 0, y: 1, visit: true }, { x: 0, y: 2, visit: true }, { x: 0, y: 4, visit: false }, { x: 1, y: 1, visit: true }, { x: 1, y: 2, visit: true }, { x: 1, y: 4, visit: false }, { x: 1, y: 6, visit: false }, { x: 2, y: 0, visit: true }, { x: 2, y: 1, visit: true }, { x: 2, y: 2, visit: true }, { x: 2, y: 4, visit: false }, { x: 2, y: 6, visit: false }, { x: 3, y: 4, visit: false }, { x: 3, y: 5, visit: false }, { x: 3, y: 6, visit: false }, { x: 4, y: 1, visit: false }, { x: 5, y: 1, visit: false }, { x: 5, y: 2, visit: false }, { x: 5, y: 3, visit: false }, { x: 5, y: 4, visit: false }, { x: 5, y: 5, visit: false }, { x: 6, y: 1, visit: false }, { x: 6, y: 2, visit: false }, { x: 6, y: 3, visit: false } ]첫번째 단지에 해당하는 집들의 visit이 모두 true로 바뀌어온다.
따라서, visit이 false인 가장 첫번째 원소{ x: 0, y: 4, visit: false }를 시작으로 dfs를 진행한다.3. dfs를 진행하고 return되는 값들을 answer 배열에 저장한다.
4. 단지 수와 각 단지의 집 수를 출력한다.
단지 수: answer 배열의 길이
각 단지의 집 수: answer 배열 원소의 값
단, 집 수를 오름차순으로 정렬하여 출력한다.
2. DFS - 재귀
해결한 코드
function b2667() {
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 n = parseInt(input[0])
var group = []
for (var i = 1; i < input.length; i++) {
group.push(input[i].split('').map(e => e = e / 1))
}
var homes = isHome(group)
var answer = []
for (var i = 0; i < homes.length; i++) {
if (homes[i].visit == false) {
var result = []
var startV = homes[i]
answer.push(recursion_dfs(homes, startV, n, result))
}
}
answer.sort((a, b) => a - b)
console.log(answer.length)
for (var i = 0; i < answer.length; i++) {
console.log(answer[i])
}
}
function recursion_dfs(homes, startV, n, result) {
result.push(startV)
startV.visit = true
var current = startV
var dx = [-1, 1, 0, 0]
var dy = [0, 0, -1, 1]
for (var i = 0; i < 4; i++) {
var a = current.x + dx[i]
var b = current.y + dy[i]
if ((a >= 0 && a < n) && (b >= 0 && b < n)) {
if (homes.some(e => e.x == a && e.y == b && e.visit == false)) {
var idx = homes.findIndex(e => e.x == a && e.y == b && e.visit == false)
recursion_dfs(homes, homes[idx], n, result)
}
}
}
return result.length
}
function isHome(group) {
var result = []
for (var i = 0; i < group.length; i++) {
for (var j = 0; j < group.length; j++) {
if (group[i][j] == 1) result.push({
x: i,
y: j,
visit: false
})
}
}
return result
}
b2667()알고리즘
※ DFS 부분만 다르므로, DFS만 정리하였다.
1. homes의 원소 중 visit이 false인 원소를 찾아 순서대로 dfs를 시작한다.
1-1. 현재 탐색하는 정점의 visit을 true로 바꾼다.
1-2. 현재 탐색하는 정점의 상하좌우를 탐색한다.
👉🏻 dx, dy를 만들어 상하좌우를 탐색하고, 해당 값이 false인 정점을 찾는다.dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]즉, 현재 정점의 [x, y] 값에서 + [-1, 0] or + [1, 0] or + [0, -1] or + [0, 1] 한 값이 homes안에 있으면,
그 값을 찾아 다음으로 탐색한다.
👉🏻 그 값에 대하여 재귀함수를 돌린다.1-3. 위 과정을 반복하여 주변에 있는 모든 정점을 방문하면, result 배열의 길이를 return한다.
👉🏻 return된 값을 answer 배열에 저장한다.2. 그리고 homes의 원소 중 visit이 false인 첫번째 원소를 찾아 또 dfs를 시작한다.
3. BFS
해결한 코드
function b2667() {
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 n = parseInt(input[0])
var group = []
for (var i = 1; i < input.length; i++) {
group.push(input[i].split('').map(e => e = e / 1))
}
var homes = isHome(group)
var answer = []
for (var i = 0; i < homes.length; i++) {
if (homes[i].visit == false) {
var startV = homes[i]
answer.push(bfs(homes, startV, n))
}
}
answer.sort((a, b) => a - b)
console.log(answer.length)
for (var i = 0; i < answer.length; i++) {
console.log(answer[i])
}
}
function bfs(homes, startV, n){
var q = []
var result = []
startV.visit = true
q.push(startV)
while(q.length !== 0){
var current = q.shift()
result.push(current)
var dx = [-1, 1, 0, 0]
var dy = [0, 0, -1, 1]
for (var i = 0; i < 4; i++) {
var a = current.x + dx[i]
var b = current.y + dy[i]
if ((a >= 0 && a < n) && (b >= 0 && b < n)) {
if (homes.some(e => e.x == a && e.y == b && e.visit == false)) {
var idx = homes.findIndex(e => e.x == a && e.y == b && e.visit == false)
var next = homes[idx]
next.visit = true
q.push(next)
}
}
}
}
return result.length
}
function isHome(group) {
var result = []
for (var i = 0; i < group.length; i++) {
for (var j = 0; j < group.length; j++) {
if (group[i][j] == 1) result.push({
x: i,
y: j,
visit: false
})
}
}
return result
}
b2667()알고리즘
※ BFS 부분만 다르므로 BFS만 정리하였다.
1. homes의 원소 중 visit이 false인 원소를 찾아 순서대로 bfs를 시작한다.
2. bfs를 구현한다.
2-1. bfs를 위해 필요한 것은?
✔ 방문한 정점을 담을 큐
✔ 탐색한 정점을 담을 result2-2. 시작하는 정점을 큐에 담는다.
또한 visit값도 true도 바꾼다.2-3. 현재 탐색할 정점을 고른다.
현재 탐색할 정점은?
👉🏻 큐에 저장된 가장 첫번째 원소
따라서 큐를 shift하고, shift하여 나온 값을 result에 담는다.2-4. 현재 탐색하는 정점의 상하좌우를 탐색한다.
👉🏻 dx, dy를 만들어 상하좌우를 탐색하고, 해당 값이 false인 정점을 찾는다.dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]현재 정점의 [x, y] 값에서 + [-1, 0] or + [1, 0] or + [0, -1] or + [0, 1] 한 값이 homes안에 있으면,
이에 해당하는 모든 정점을 큐에 넣는다.
🙋🏻♀️ bfs는 "너비탐색"이다. 따라서 break를 걸지 않고, 위의 조건에 해당하는 모든 정점들을 큐에 넣는다.
👉🏻 그 정점들의 visit값을 true로 바꾼다.2-5. 이렇게 저장된 큐의 첫번째 원소를 뽑아 위 과정을 계속 이어간다.
2-6. 주변에 있는 모든 정점을 방문하면 result 배열의 길이를 return한다.
3. 그리고 homes의 원소 중 visit이 false인 첫번째 원소를 찾아 또 bfs를 시작한다.
큰 차이는 없지만, 메모리나 시간적으로 bfs가 가장 적게 걸렸다.
