Tree Traverse (트리 순회 or Graph Search)

bubobubobo·2022년 8월 14일
0

우리는 길을 찾을 때 보통 지도를 들고 시작점부터 끝점까지 갈 수 있는 방법들을 대략적으로 그린 뒤, 그 중 기준에 따라서 시간이 제일 짧게 걸리거나, 거리가 제일 짧은 경로를 선택해서 가곤 한다. 그런데 컴퓨터는 바보라서 지도를 전체적으로 볼 수도 없고, “대략적인 경로”라는 걸 직접 가보기 전에는 생각해낼 수가 없다. 컴퓨터는 무조건 어떤 좌표를 주면 눈 앞에 있는 것밖에 보지 못하기 때문이다. 마치 정원 미로에 들어간 사람처럼…

하지만 우리가 생각해내기 귀찮은 아주 반복적인 작업을 빠르게 잘하는 컴퓨터는, 모든 경로를 우리 눈 보다 빠르게 뒤져보고 우리보다 빨리 정답 경로를 찾아낼 수 있다. 그래서 눈앞에 주어진 정보만으로 주어진 지도의 모든 경로를 뒤져보는 알고리즘트리순회(Tree Traverse, 줄이면 ㅜㅜ) 알고리즘이라고 부른다.

이 트리 순회는 정말 많은 알고리즘들이 있다. 간단한 DFS, BFS부터 시작해서 Parameter가 주어지는 다익스트라 알고리즘, 그리고 스타크래프트에도 들어있고 그럴듯한 길찾기 인공지능의 시작점인 A*(A star) 알고리즘 등 경우에 따라서 정말 많은 알고리즘들이 쓰이고 있다. 그 중에 이 글에서는 DFS와 BFS란 걸 다뤄보려 한다.

DFS(Depth First Search, 깊이 우선 탐색)


DFS는 이름에 써있듯이 처음 시작점에서 방향을 정해 출발하면 그 방향으로 쭉 가본 다음에 갈 수 없으면 안가본 길을 차근차근 찾는 방식의 순회 방법이다. 예를 들어 트리가 아래처럼 생겼다면

1번부터 시작해서 2번 → 4번 → 5번 → 3번 순서대로 순회를 하게 된다. 앞에서 말했던 미로에 빗대어 얘기해보면, 컴퓨터는 일단 1번 위치에서 2번하고 3번을 눈앞에 보게 된다. 여기서 순서는 상관 없지만 작은 숫자 먼저 간다고 생각하면, 3번을 “아직 안간 곳 리스트” 메모해두고 2번으로 가면서 1번은 “이미 간 곳 리스트”에다가 기록을 한다. 그럼 이제 컴퓨터는 눈앞에 4번과 5번을 보게 되는데, 여기서 다시 작은 숫자인 4번으로 가면 3번을 메모한 메모지 옆에 5번을 쓰고 2번은 이미 간 곳으로 처리한다. 그러면 안 간 곳에 3번과 5번이 써있는데, 가장 최근에 써넣은 곳부터 방문한다고 하면 5번과 3번을 차례대로 방문하게 되고 위의 그림처럼 그래프 위의 모든 점들을 한 번씩 가보게 된다.

알고리즘스럽게 DFS로 그래프를 순회하는 법을 정리하면 이렇게 된다.

  1. 현재 위치와 인접한, 아직 가보지 않은 곳을 스택에 저장해 기록
  2. 스택에서 하나를 꺼내 현재 위치를 꺼낸 위치로 다시 설정
  3. 현재 위치를 이미 간 곳으로 표시한 뒤 스택이 빌 때까지 1, 2, 3 순서대로 반복

코드로 그래프 객체와 DFS 알고리즘을 구현하면 이렇게 할 수 있다.

const graph = [
    [], // 0번 노드는 없으므로 빈 배열
    [3, 2], // 1번 노드의 자식 노드들
    [5, 4], // 2번 노드의 자식 노드들
    [], // 3번 노드의 자식
    [], // 4번 노드의 자식
    [] // 5번 너 이 자식
]

function dfs(graph, startNode) {
    // 아직 안간 곳 체크하는 스택
    const stack = []
    // 이미 간 곳들 체크하는 배열(안갔으니 false로 초기화)
    const visited = new Array(graph.length).fill(false)

    // 처음 시작 지점 스택에 저장
    stack.push(startNode)

    let current // 그래프에서 현재 위치
    const traversePath = []
    // 스택이 빌 때까지(=안간 곳이 없을 때까지)
    while (stack.length) {
        current = stack.pop()
        // 현재 위치를 경로에 저장
        traversePath.push(current)
        // 최근 위치를 간 곳으로 표시
        visited[current] = true
        
        // 현재 위치에서 보이는 노드들에 대해서
        for (let child of graph[current]) {
            // 아직 안가본 곳이라면
            if (!visited[child]) {
                stack.push(child) // 스택에 저장
            }
        }
    }
    return traversePath
}

console.log(dfs(graph, 1)) // 결과 : [1, 2, 4, 5, 3]

이렇게 stack과 visited를 만들고 시작 위치로 초기화한 다음에 stack에서 하나씩 pop 해가면서 주변에 안 간 곳들을 stack에 넣으면 그래프의 모든 곳들을 한 번씩 순회하는 코드를 만들어낼 수 있다.

그런데 그래프를 순회할 수 있는걸로 뭘 할 수 있는데? 라는 궁금증이 생길 수 있다. 우리가 코테 공부하면서 제일 많이 볼 수 있는 예시를 들면, 지도에서 특정한 지점과 연결되어있는 영역의 크기를 구할 때 굉장히 유용하게 사용할 수 있다.

음료수 얼려먹기 문제

문제 링크 : https://velog.io/@jinsol/DFSBFS-음료수-얼려-먹기

"이것이 취업을 위한 코딩 테스트다"(줄여서 이코테)에 있는 간단한 문제중에 하나이다. 0은 음료수를 부을 수 있는 곳이고 이렇게 음료수를 부으면 붙어있는 0끼리는 하나의 얼음덩어리가 돼서, 만들 수 있는 얼음덩어리 개수를 세는 문제로, DFS를 이용해서 풀면 아래 코드처럼 풀 수 있다.

function solution(N, M, iceTray) {
    let res = 0 // 전체 얼음 개수
    for (let x = 0; x < M; x++) {
        for (let y = 0; y < N; y++) {
            if (iceTray[y][x] === 0) {
                iceTray = freezeSoda(N, M, iceTray, x, y)
                res++
            }
        }
    }
    return res
}

// (x, y) 위치를 받아 해당 위치에서 인접한 0들을 모두 1로 바꿈(얼려버림)
function freezeSoda(N, M, iceTray, x, y) {
		// 순서대로 아래, 위, 왼쪽, 오른쪽
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    const stack = []
    // 2차원 배열로 선언!
    const visited = Array.from(Array(M), () => new Array(N).fill(false))

    // 처음 시작 지점 스택에 저장
    stack.push([x, y])

    let current // 그래프에서 현재 위치
    while (stack.length) {
        current = stack.pop()
        const [curX, curY] = current
        // 현재 위치를 0에서 1로 바꿔 얼려버림
        iceTray[curY][curX] = 1
        // 최근 위치를 간 곳으로 표시
        visited[curY][curX] = true

        // 현재 위치에서 보이는 위/아래/왼쪽/오른쪽 4방향에 대해서
        for (let i = 0; i < 4; i++) {
            // 다음 위치 설정
            const nextX = curX + dx[i]
            const nextY = curY + dy[i]
            // 만약 다음 위치가 갈 수 없는 곳이면 무시
            if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N) continue

            // 만약 다음 위치가 벽이라면(1이라면) 무시
            if (iceTray[nextY][nextX] === 1) continue

            // 아직 가지 않은 곳이라면
            if (!visited[nextY][nextX]) {
                stack.push([nextX, nextY]) // 스택에 저장
            }
        }
    }
    return iceTray // 한 구역 얼린 뒤의 얼음판 반환
}

const N = 4 // 세로 길이
const M = 5 // 가로 길이
const iceTray = [ // 얼음 틀
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
]

console.log(solution(N, M, iceTray)) // 결과 : 3

이렇게 인접한 영역들을 동적으로 확인하고 계산할 때 많이 쓸 수 있다. 이 외에도 다양한 활용 방식이 있으나 BFS를 먼저 살펴보자.

BFS(Breadth First Search, 너비 우선 탐색)


BFS는 DFS와는 조금 다르게 그래프의 노드를 모두 한 번씩 순회하는 방식으로, 그림으로 보면 아래와 같다.

먼저 1번에서 보이는 2, 3번을 순서대로 간 다음에, 2번의 자식 노드들을 또 차례대로 거쳐간다. DFS 코드를 한 번 짜보면 BFS는 쉽게 짤 수 있는데, DFS에서 스택으로 썼던걸 큐로 바꿔주기만 하면 되기 때문이다. 아래의 BFS 코드와 위의 DFS 코드를 비교해보면 확인할 수 있다.

const graph = [
    [], // 0번 노드는 없으므로 빈 배열
    [2, 3], // 1번 노드의 자식 노드들
    [4, 5], // 2번 노드의 자식 노드들
    [], // 3번 노드의 자식
    [], // 4번 노드의 자식
    [] // 5번 너 이 자식
]

function bfs(graph, startNode) {
    // 아직 안간 곳 체크하는 큐
    const queue = []
    // 이미 간 곳들 체크하는 배열(안갔으니 false로 초기화)
    const visited = new Array(graph.length).fill(false)

    // 처음 시작 지점 큐에 저장
    queue.push(startNode)

    let current // 그래프에서 현재 위치
    const traversePath = []
    // 큐가 빌 때까지(=안간 곳이 없을 때까지)
    while (queue.length) {
        current = queue.shift()
        // 현재 위치를 경로에 저장
        traversePath.push(current)
        // 최근 위치를 간 곳으로 표시
        visited[current] = true
        
        // 현재 위치에서 보이는 노드들에 대해서
        for (let child of graph[current]) {
            // 아직 안가본 곳이라면
            if (!visited[child]) {
                queue.push(child) // 큐에 저장
            }
        }
    }
    return traversePath
}

console.log(bfs(graph, 1)) // 결과 : [1, 2, 3, 4, 5]

마찬가지로 얼려먹는 문제도 풀어보면 아래 코드처럼 풀 수 있다.

function solution(N, M, iceTray) {
    let res = 0 // 전체 얼음 개수
    for (let x = 0; x < M; x++) {
        for (let y = 0; y < N; y++) {
            if (iceTray[y][x] === 0) {
                iceTray = freezeSoda(N, M, iceTray, x, y)
                res++
            }
        }
    }
    return res
}

// (x, y) 위치를 받아 해당 위치에서 인접한 0들을 모두 1로 바꿈(얼려버림)
function freezeSoda(N, M, iceTray, x, y) {
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    const queue = []
    // 2차원 배열로 선언!
    const visited = Array.from(Array(M), () => new Array(N).fill(false))

    // 처음 시작 지점 큐에 저장
    queue.push([x, y])

    let current // 그래프에서 현재 위치
    while (queue.length) {
        current = queue.shift()
        const [curX, curY] = current
        // 현재 위치를 0에서 1로 바꿔 얼려버림
        iceTray[curY][curX] = 1
        // 최근 위치를 간 곳으로 표시
        visited[curY][curX] = true

        // 현재 위치에서 보이는 위/아래/왼쪽/오른쪽 4방향에 대해서
        for (let i = 0; i < 4; i++) {
            // 다음 위치 설정
            const nextX = curX + dx[i]
            const nextY = curY + dy[i]
            // 만약 다음 위치가 갈 수 없는 곳이면 무시
            if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N) continue

            // 만약 다음 위치가 벽이라면(1이라면) 무시
            if (iceTray[nextY][nextX] === 1) continue

            // 아직 가지 않은 곳이라면
            if (!visited[nextY][nextX]) {
                queue.push([nextX, nextY]) // 큐에 저장
            }
        }
    }
    return iceTray // 한 구역 얼린 뒤의 얼음판 반환
}

const N = 4 // 세로 길이
const M = 5 // 가로 길이
const iceTray = [ // 얼음 틀
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
]

console.log(solution(N, M, iceTray)) // 결과 : 3

BFS는 DFS와는 다른 장점이 하나 더 있다. 바로 최단경로를 구할 수 있다는 점이다. 예를 들어 어떤 미로가 있는데 시작지점부터 끝까지 최단거리를 구하고 싶다면 BFS로 단번에 구할 수가 있다. 최단경로 문제 하나랑 최단경로인 이유는 아래에서 확인할 수 있다.

게임 맵 최단거리(프로그래머스, Lv. 2) : https://programmers.co.kr/learn/courses/30/lessons/1844

BFS가 최단경로인 이유 : https://nulls.co.kr/graph/141

profile
Analyze... Develop!

0개의 댓글