[구름톤 챌린지] 3주차_발전기

 

필요한 개념

---

• Stack (스택)
• Queue (큐)
• BFS (너비 우선 탐색)

 

 

문제 분석

---

주어진 행렬에서 요구하는 값을 찾는 문제로, 행렬에서 효율적인 이동을 하면서 값을 빠르게 찾아내는 것이 중요하다.

그러기 위해서는 완전 탐색이 아닌, 다른 탐색 방법이 필요하다.

 

• 행렬은 0과 1로 이루어지며, 1이면 집이 있는 칸이다.
• 어떤 집에 발전기를 설치해 전력을 공급할 수 있다.
• 어떤 집에 상하좌우로 인접한 집 중 하나가 전력을 공급받고 있으면, 그 집도 전력을 공급받는다.
• 설치해야 하는 발전기의 최소 개수를 구해야 한다.

 

이 문제를 해결하기 위해서는 어떤 집에 발전기를 설치했을 때 전기를 공급받을 수 있는 집을 알아야 한다.

공급 받은 집에는 발전기를 설치하지 않아도 되기 때문이다.

즉, 인접한 집의 집합의 개수를 구하는 문제이다.

이를 효율적으로 찾기 위해서 BFS가 필요하다.

 

 

Stack (스택)

---

스택은 First-In-Last-Out, 먼저 들어간 것이 나중에 나오는 자료구조이다.

자바스크립트에서 Array 자료형으로 스택을 구현할 수 있다.

// 스택으로 사용할 리스트를 선언
let stack = [];

// push를 이용해 스택에 원소 채우기
stack.push(1);
stack.push(2);
stack.push(3);

// 스택의 맨 꼭대기에 있는 원소를 조회할 땐 length - 1 인덱스 사용
console.log(stack[stack.length - 1]); // 3

// 스택에서 값을 제거할 때 pop() 사용
stack.pop(); // 스택의 끝에 있는 3 제거
let value = stack.pop(); // 스택의 끝의 2를 할당
console.log(value); // 2

 

 

Queue (큐)

---

큐는 First-In-First-Out, 스택과 반대로 먼저 들어간 것이 먼저 나오는 자료구조이다.

먼저 서있던 사람이 먼저 나가는 대기열을 큐의 예시라고 할 수 있다.

// 큐로 사용할 리스트를 선언
let queue = [];

// enqueue를 이용해 큐에 원소 채우기
queue.push(1);
queue.push(2);
queue.push(3);

// 큐의 맨 앞에 있는 원소를 조회할 땐 0 인덱스를 사용
console.log(queue[0]); // 1

// 큐에서 값을 제거할 때에는 shift() 사용
queue.shift(); // 큐의 앞에 있는 1을 제거
let value = queue.shift(); // 큐의 앞의 2를 바로 할당
console.log(value); // 2

 

 

BFS (너비 우선 탐색)

---

BFS(Breadth-First-Search)는 현재 위치를 기준으로, 방문이 가능한 모든 위치를 탐색한다.

그 다음 단계에서는 이전 단계에서 구한 위치들을 기준으로 다시 방문이 가능한 모든 위치를 탐색한다.

각각의 칸을 하나의 위치로 생각하고, 현재 위치에서 갈 수 있는 위치부터 먼저 탐색한다는 의미이다.

보통은 상하좌우 이며, 문제에 따라서는 대각선도 나올 수 있다.

완전 탐색과 다른 점은 갈 수 있는 위치만 탐색한다는 점이다.

결론적으로 못 가거나, 갈 수 없는 위치는 굳이 탐색할 필요가 없으므로 완전 탐색보다는 효율적이다.

 

 

탐색을 위한 구조 만들기

---

• 하나의 발전기를 퉁해서 어떤 집에 전기가 공급된다면, 상하좌우 인접한 집에 전기를 공급할 수 있다.
  • 즉, 어떤 집에 공급되고 있다면 해당 집을 기준으로 전기를 공급할 수 있는 새로운 집을 찾아야 한다.
• 하나의 발전기로 전기가 공급되는 집을 탐색한 뒤, 다시 전기가 필요한 집을 탐색한다.

 

우선 상하좌우 이동을 위해서

• dx/dy 기법을 사용하여 상하좌우 이동을 구현한다.
• matrix 변수를 사용하여 현재 마을의 상태를 저장한다.
• visited 변수를 활용해서 전기가 공급되고 있는 집을 기록한다.

..code
let input = [];
rl.on('line', (line) => {
	input.push(line.trim());
	if (input.lenght === Number(input[0]) + 1){
		rl.close();
	}
});

let N;
let matrix = [];
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
rl.on('close', () => {
	N = Number(input[0]);
	for (let i = 1 ; i <= N ; i++){
		matrix.push(input[i].split(' ').map(Number));  // 현재 마을의 상태 저장
	}
	let visited = Array.from({length : N}, () => Array(N).fill(false));  // 전기가 공급되고 있는 집 기록
	}
})

 

 

탐색하기

---

• matrix[x][y] 의 값이 1이면서, visited[x][y] 의 값이 0인 (x, y)를 찾는다.
• 해당 위치를 기준으로 상하좌우에 또 다른 집이 있는지 확인한다.
  • 만약에 그 집의 matrix[x][y] 의 값이 1이면서, visited[x][y] 의 값이 0이라면, 다음 탐색 후보에 추가한다.
• 탐색 후보가 모두 없어질 때까지 탐색을 계속한다.

 

이때 탐색 후보의 자료구조 형태가 큐 또는 스택이다.

BFS는 큐로 구현을 하고, 모든 탐색 후보는 큐를 통해서 관리된다.

..code

let N;
let matrix = [];
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
rl.on('close', () => {
	N = Number(input[0]);
	for (let i = 1 ; i <= N ; i++){
		matrix.push(input[i].split(' ').map(Number));
	}
	let visited = Array.from({length : N}, () => Array(N).fill(false));
	}
	for (let i = 0 ; i < N ; i++){
		for (let j = 0 ; j < N ; j++){
				/*
				matrx[x][y] 의 값이 1 이면서, 
				visited[x][y] 의 값이 0 인 
				(x, y) 를 우선 찾기
				*/
			if (matrix[i][j] === 1 && !visited[i][j]){
				// q는 탐색 후보를 관리할 큐
				// 첫 번째 탐색 후보 추가
				q = [];
				q.push([i, j]);

				// 탐색 후보가 없을 때까지 탐색
				while (q.length > 0){

					/* 
					현재 탐색 후보를 꺼내오고, 이는 전기가 공급됨을 의미함으로
					visited 변수 갱신
					*/
					let [currentR, currentC] = q.pop();
					visited[currentR][currentC] = true;

					/* 
					현재 탐색 위치에서 상하좌우 탐색
					*/					
					for (let k = 0 ; k < 4 ; k++){
						let nextR = currentR + dx[k];
						let nextC = currentC + dy[k];
						// 마을 안의 좌표인지 확인
						if (nextR >= 0 && nextR < N && nextC >= 0 && nextC < N) {
							// 집이 있으면서, 전기가 공급되고 있는지 확인
							if (matrix[nextR][nextC] === 1 && !visited[nextR][nextC]) {
									// 모든 조건을 만족하면 새로게 전기가 공급되는
									// 집이기 때문에, 탐색 후보에 추가									
									q.push([nextR, nextC]);
							}
						}
					}
				}
			}
		}
	}
})

 

즉, 하나의 발전기를 세울 때마다 위의 BFS 코드가 실행된다.

이를 count 변수로 관리하고 출력한다.

..code

let N;
let matrix = [];
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
rl.on('close', () => {
	N = Number(input[0]);
	for (let i = 1 ; i <= N ; i++){
		matrix.push(input[i].split(' ').map(Number));
	}
	let visited = Array.from({length : N}, () => Array(N).fill(false));
	}
	let count = 0;
	for (let i = 0 ; i < N ; i++){
		for (let j = 0 ; j < N ; j++){
				/*
				matrx[x][y] 의 값이 1 이면서, 
				visited[x][y] 의 값이 0 인 
				(x, y) 를 우선 찾기
				*/
			if (matrix[i][j] === 1 && !visited[i][j]){
				// q는 탐색 후보를 관리할 큐
				// 첫 번째 탐색 후보 추가
				count++;
				..BFS
			}
		}
	}
	console.log(count);
})

 

 

 

3주차에 접어들면서 완전 탐색, 너비 우선 탐색 등 구현하기 쉽지 않은 문제들이 나왔다.

문제를 다시 풀어보고 정리하면서 스택, 큐, BFS도 확실하게 짚고 넘어갈 수 있었다.

탐색을 구현하는 방법이 아직은 어려워서 최대한 이해하는 시간을 가지고 넘어가야겠다.