알고리즘 DFS 구현하기 - C++, JavaScript

큰돌님 블로그를 참고해서 DFS 개념을 먼저 이해하고 예시 문제를 풀어보았다.

먼저 C++코드로 작성되어 있었기 때문에 C++ 코드로 이해한 바를 다시 자바스크립트 코드로 구현해보았다.

예시 문제 종화는 방구쟁이야!를 푸는 코드이다.

문제는 위와 같다.

C++ 코드

사실 이건 C++ 솔루션 코드를 보고 익혔기 때문에 큰돌님 코드랑 다른 점이 없다. ㅋㅋ

그래도 이제 솔루션 아예 안보고 똑같이 짤 수 있다! 시간은 쪼오끔 걸린다.

#include <bits/stdc++.h>
using namespace std;

int N, M;
int x = 1;
int y = 1;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int a[104][104];
int visited[104][104];
int cnt;

void DFS(int x, int y){
	visited[x][y] = 1;
	
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(ny < 0 || nx < 0 || nx >= 100 || ny >= 100) continue;
		if(visited[ny][nx] == 0 && a[ny][nx] == 1){
			DFS(ny, nx);
		}
	}
	
	return;
}

int main(){
	
	cin >> N >> M;
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> a[i][j];
		}
	}
	
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(a[i][j] == 1 && visited[i][j] == 0){
				cnt++;
				DFS(i, j);
			}
		}
	}
	
	cout << cnt << "\n";
	
	return 0;
}

자바스크립트 코드

C++에서는 입력을 받았지만 자바스크립트에서는 애초에 배열로 미리 문제를 만들어서 함수를 호출시키는 방법을 사용했다. (사실 입력 받게 할 줄 모름)

let plan = [
  [1, 0, 1, 0, 1],
  [1, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 1, 1],
  [0, 1, 0, 0, 0]
];

let visited;
let count = 0;

function main(n, m, a) {
  visited = Array(n)
    .fill(0)
    .map(() => Array(m).fill(0));

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (visited[i][j] === 0 && a[i][j] === 1) {
        count++;
        DFS(i, j);
      }
    }
  }

  console.log(count);
}

function DFS(y, x) {
  visited[y][x] = 1;

  let dy = [-1, 0, 1, 0];
  let dx = [0, 1, 0, -1];

  for(let i = 0; i < 4; i++){
    let ny = y + dy[i];
    let nx = x + dx[i];

    if(ny < 0 || nx < 0 || ny >= plan.length || nx >= plan[0].length ) continue;
    if(visited[ny][nx] === 0 && plan[ny][nx] === 1){
      DFS(ny, nx);
    }
  }
}

main(5, 5, plan)

plan 부분에서 1을 바꿔서 출력을 확인해 봤는데 잘 나오는 것을 보아 제대로 이해했다고 생각한다.

물론 다른 문제를 풀때 DFS를 사용해야 한다면 그 문제를 풀 수 있을지는..아직 모르겠지만 ㅋㅋㅋ

BFS까지 익혀서 적용해보고 DFS/BFS 관련 알고리즘 문제 풀이를 진행할 생각이다.

DFS 며칠 전에 C++ 코드 보고 자바스크립트로 구현하려고 했을 때는 제대로 작동 안했었는데..ㅠㅠ 그때는 C++ 코드를 그냥 베껴서 풀려고 했어서 아마 로직이 잘못 꼬였던 것 같다.

지금은 그래도 이해했으니 자바스크립트 코드가 제대로 돌아가는 거 맞겠지..?ㅋㅋㅋ

4 방향은 이런 식으로 짜면 되는구나-를 우선 익혔다고 생각한다.

---

예시 문제 출처
큰돌의 터전