[중앙정보기술인재개발원] 87일차

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

깊이 우선 탐색(Depth First Search, DFS)의 개념과 재귀적 접근 방법 소개

DFS는 시작 정점에서 가장 깊숙한 곳까지 탐색을 진행하며, 더 이상 진행할 수 없을 때 이전 단계로 돌아와 다음 경로를 탐색하는 방식으로 작동합니다. 이번 콘텐츠에서는 DFS의 원리, 구현 방법, 그리고 어떻게 활용되는지에 대해 함께 알아보겠습니다.

 

DFS란?

깊이 우선 탐색, 또는 DFS는 시작 정점에서 가능한 한 깊이 들어가 탐색을 진행하며, 더 이상 방문할 곳이 없을 때 이전 단계로 돌아와 다른 경로를 탐색하는 알고리즘입니다. 즉, 하나의 경로를 완전히 탐색한 후에 다른 경로로 이동합니다.

 

DFS의 동작 원리

1. 먼저, 한 분기를 완전히 탐색합니다.
2. 만약 더 이상 탐색할 수 없는 상태가 되면, 이전 분기로 돌아가 다음 분기를 탐색합니다.
   • 이 방식은 하나의 경로를 끝까지 탐색한 후 다음 경로로 넘어가므로, 똑똑하게 선택한다면 목표지점을 빠르게 찾아낼 수 있습니다.
   • BFS에 비해 탐색 시간이 약간 더 걸릴 수는 있지만, 이는 모든 정점을 완전히 탐색하는 데 필요한 투자로 생각하면 좋습니다. BFS를 사용하면 가장 먼저 발견한 경로에 관계없이 모든 경로를 살펴봐야 합니다.
   • 현재 경로에 있는 정점들만 기억하면 되므로, 메모리 사용량은 비교적 적습니다. 또한, 목표 정점이 깊이 있는 곳에 위치해 있다면, DFS를 사용하면 빠르게 답을 찾을 수 있습니다.
3. 그러나 DFS는 그래프 내의 순환 구조를 반드시 고려해야 합니다. 방문했던 정점을 다시 방문하지 않도록 주의해야 합니다.
   • 이는 반복적으로 동일한 정점에 도달하는 경우, 무한 루프에 빠질 수 있기 때문입니다. 이를 피하기 위해 실제 애플리케이션에서는 종종 탐색 깊이를 미리 지정하고, 목표 정점을 발견하지 못하면 다른 경로로 탐색하는 전략을 사용합니다.
   • DFS를 사용하면 항상 최단 경로를 찾아주지는 않습니다. 여러 경로가 존재하고 목표 정점에 도달할 수 있는 경우, DFS는 처음 도달한 경로를 선택할 수 있으며, 이는 반드시 최적의 경로라는 보장이 없습니다.

재귀적 접근 방법

DFS를 재귀적으로 구현하는 방법은 다음과 같습니다:

1. 방문한 정점을 표시하기 위한 배열을 생성합니다.
2. 현재 정점을 확인합니다. 최초 실행시에는 일반적으로 root(최상위 노드)부터 탐색을 시작합니다.
3. 해당 현재 정점의 방문여부를 체크합니다. (방문했다고 표기 변경)
4. 현재 정점과 인접한 정점이 있는지 확인하고, 방문 여부를 확인합니다.
5. 인접한 정점 중에서 방문하지 않은 정점이 있다면, 해당 정점을 방문했다고 표시하고 2~5번 과정을 재귀 호출하여 해당 정점을 현재 정점으로 설정합니다.
6. 모든 정점을 방문할 때까지 2~5 단계를 반복합니다.

아래 예시와 함께 살펴보도록 하겠습니다.

DFS를 활용해야 하는 경우

DFS의 활용을 최대한으로 끌어내려면 어떤 경우에 적합한지, 그리고 사용 시 유의해야 할 점들을 알아야 합니다.

1. 그래프의 모든 정점을 방문하는 것이 주된 목표인 경우, DFS나 BFS 어느 것을 사용해도 무방합니다. 즉, 단순히 모든 정점을 방문하는 것이 필요하다면, 여러분이 더 편하게 사용할 수 있는 방법을 선택하시면 됩니다.
2. 경로의 특성을 기억해야 하는 문제 상황에서는 DFS가 적절합니다. 이는 탐색 도중 장애물을 마주하는 경우도 포함됩니다.
   • 예를 들어, 각 정점에 숫자가 부여되어 있고, a에서 b까지 이동하는 경로를 찾되, 경로상에 동일한 숫자가 있어서는 안 되는 상황이라면, DFS를 사용하는 것이 좋습니다. (BFS는 경로의 특성을 저장하지 않습니다)
3. 자동 미로 생성과 같은 문제에서도 DFS가 유용합니다.
   • 임의의 방향으로 계속해서 길을 파나가다가, 더 이상 길을 만들 수 없게 되면, 새로운 길을 만들 수 있는 곳이 나올 때까지 되돌아간 후 다시 길을 만드는 방식을 반복하면, 결국 출구까지의 경로를 만들 수 있습니다.
4. 만약 검색 대상이 되는 그래프의 크기가 매우 크다면, DFS를 고려하는 것이 바람직합니다.
   • 현재 경로상의 정점들만을 기억하면 되므로, 저장 공간이 상대적으로 적게 필요하며, 목표 정점이 깊숙한 곳에 위치하고 있다면, 방문할 수 있는 루트를 빠르게 찾을 수 있습니다.

DFS 활용 시 주의할 점

모든 정점을 방문할 수 있도록 시작 정점을 선정하는 것이 중요하며, 그래프 내의 순환구조를 감안해 이미 방문한 정점을 다시 방문하지 않도록 주의해야 합니다. 또한, DFS는 최단 경로를 보장하지 않습니다. 따라서, 최단 경로를 찾는 것이 필요한 경우에는 다른 알고리즘의 도움이 필요합니다.

---

그래프의 깊이 우선 탐색 순서

깊이 우선 탐색의 순서는 다음과 같습니다:

1. 시작 정점을 방문합니다. 시작 정점은 탐색의 출발점이며, 방문 여부를 표시합니다.
2. 시작 정점과 인접한 정점들 중에서 아직 방문하지 않은 정점을 선택하여 탐색을 진행합니다. DFS에서는 인접한 정점들 중 첫 번째 정점을 선택하는 것을 원칙으로 합니다.
3. 선택한 정점으로 이동하고, 그 정점을 방문한 것으로 표시합니다.
4. 방문한 정점에서 다시 인접한 정점들 중에서 아직 방문하지 않은 정점을 선택하여 탐색을 진행합니다. 이 과정을 재귀적으로 반복합니다. 즉, DFS는 한 정점의 탐색이 완전히 끝날 때까지 해당 정점의 자식 정점들을 우선적으로 탐색하는 방식을 취합니다.
5. 더 이상 방문할 정점이 없거나, 모든 정점을 방문했을 경우, 그 시점에서의 탐색을 마무리합니다.
6. 탐색을 마친 후에는 이전 정점으로 돌아가서 다른 후행 정점을 탐색합니다. 이 과정을 재귀적으로 반복하여 모든 정점을 방문합니다.

이렇게 하면, DFS를 통해 그래프의 모든 정점을 체계적이고 효과적으로 방문할 수 있습니다. 이 때, 각 단계에서의 선택과 진행 과정을 이해하고 체크해가며 진행하는 것이 중요합니다.

---

DFS 알고리즘의 구현

DFS 알고리즘 구현 방법

DFS 알고리즘은 스택 자료 구조 또는 재귀를 이용하여 구현할 수 있습니다. 보통은 재귀를 이용한 방식이 많이 쓰입니다.

알고리즘의 구현 방법은 아래와 같습니다:

1. DFS 알고리즘의 첫 걸음은 시작 정점을 선정하는 것입니다. 선정한 이후, 그 정점이 이미 방문한 곳인지를 확인하게 됩니다. 보통은 배열이나 집합을 이용하여 이 '방문 여부'를 체크합니다.
2. 그 다음 단계에서는 시작 정점이 이미 방문한 곳인지를 다시 한번 확인합니다. 만약 이미 방문한 곳이라면, 재귀 호출을 멈추고 이전의 호출 지점으로 돌아갑니다. 특별한 상황에서는 방문 여부를 기록해야 할 경우, 방문 여부를 기록하고 그 정보를 반환하는 방식으로 구현하기도 합니다.
3. 만약 시작 정점이 아직 방문하지 않은 곳이라면, 방문 여부를 체크한 후 이를 저장합니다. 예컨대, visited[index] = true;와 같은 방식으로 배열을 활용하여 방문 여부를 기록합니다.
4. 이후에는 현재 정점과 연결된 모든 정점들을 하나씩 확인하면서 순회하게 됩니다. 이를 위해 재귀 호출을 이용하여 각각의 연결된 정점을 방문하고, 그곳에서 다시 DFS 알고리즘을 수행합니다.
5. 마지막으로, 모든 정점들을 방문하거나 탐색이 끝난 경우, 알고리즘이 종료됩니다.

DFS 알고리즘을 구현할 때 가장 중요하게 기억해야 할 점은 '방문 여부'를 체크하는 것입니다. 이를 위해 배열이나 집합을 활용하여 방문 여부를 효율적으로 관리해야 합니다. 또한, DFS 알고리즘은 연결 그래프와 비연결 그래프 양쪽 모두에 적용할 수 있으며, 재귀를 이용한 구현에서는 스택 메모리를 사용하게 됩니다. 따라서 재귀 호출의 깊이 제한을 고려하면서 알고리즘을 설계해야 합니다.

---

그래프 깊이 우선 탐색 예제와 응용

그래프 탐색과 깊이 우선 탐색 이해하기

깊이 우선 탐색, 더 널리 알려진 이름으로 DFS는 그래프 탐색에 주로 사용되는 기법입니다. 실생활에서도 DFS는 네트워크 라우팅, 소셜 네트워크 분석 등 다양한 분야에서 활용됩니다. 이번 콘텐츠에서는 그 사용 사례를 간략하게 살펴보겠습니다.

라우팅 알고리즘에서 DFS의 활용

라우팅 알고리즘은 네트워크 장비 간의 최적 경로를 탐색하는 기법입니다. DFS를 활용하면 이러한 경로를 효과적으로 찾을 수 있습니다. 아래는 그 과정을 단계별로 설명한 것입니다:

1. 먼저, 라우팅 테이블을 그래프로 표현합니다. 그래프의 노드는 네트워크 장비를, 간선은 노드 간의 연결을 나타냅니다. 연결된 노드 간의 비용(가중치)은 간선의 속성으로 저장됩니다.
2. 이후, 출발지와 목적지를 설정합니다.
3. 이제 DFS 알고리즘을 활용하여 그래프를 탐색합니다. 출발지에서 시작하여 다음 노드로 이동하면서, 목적지에 도달할 때까지 계속해서 탐색합니다.
4. DFS를 진행하면서 현재 노드와 연결된 이웃 노드를 확인합니다. 방문하지 않은 이웃 노드 중 하나를 선택하여 해당 노드로 이동합니다.
5. 목적지에 도달하면, 이때의 경로를 저장하고 탐색을 마칩니다.
6. 마지막으로, 저장된 경로를 통해 최적 경로를 도출합니다. 이 경로는 출발지에서 목적지까지의 최단 경로를 나타내게 됩니다.

소셜 네트워크 분석에 적용된 DFS

소셜 네트워크를 그래프로 변환하고, DFS를 사용하여 네트워크에서 커뮤니티를 찾거나 영향력을 분석하는 방법에 대해 알아봅시다.

1. 소셜 네트워크를 그래프로 표현합니다. 각 노드는 개인이나 계정을 나타내고, 간선은 노드들간의 관계를 표현합니다.
2. 네트워크에서 특정 커뮤니티를 찾기 위해 시작 노드를 선택합니다.
3. DFS 알고리즘을 사용하여 그래프를 탐색합니다. 시작 노드에서 다음 노드로 이동하며, 해당 커뮤니티에 속하는 노드를 찾습니다.
4. 탐색 과정에서 현재 노드와 연결된 이웃 노드를 확인합니다. 방문하지 않은 이웃 노드를 선택하여 이동합니다.
5. 커뮤니티에 속하는 노드를 찾으며 필요한 정보를 수집합니다. 이를 통해 커뮤니티의 구성원 리스트를 만들거나, 영향력을 분석할 수 있습니다.
6. 탐색이 종료되면, 수집한 정보를 통해 커뮤니티의 특성을 분석하거나, 영향력 있는 노드를 식별할 수 있습니다.

예를 들어, 특정 소셜 네트워크에서의 커뮤니티 탐색을 위해 DFS를 활용할 수 있습니다. 시작 노드를 사용자 A로 설정하고, DFS를 통해 A와 직접 또는 간접적으로 연결된 다른 사용자를 탐색합니다. 탐색하며 방문한 노드들을 모아 A를 중심으로 한 커뮤니티로 분석할 수 있습니다. 이를 통해 A와 관련된 친구들이 속한 커뮤니티를 파악하거나, A의 영향력 있는 위치를 파악할 수 있습니다.

 

웹 크롤링에 적용된 DFS

웹 페이지를 그래프로 변환하고, DFS를 사용하여 웹 크롤러를 만드는 방법을 살펴봅시다.

1. 웹 페이지를 그래프로 표현합니다. 각 웹 페이지는 노드로 표현되며, 링크는 간선으로 표현됩니다.
2. 크롤러의 시작점을 설정합니다. 이는 크롤링을 시작할 초기 웹 페이지입니다.
3. DFS 알고리즘을 사용하여 그래프를 탐색합니다. 시작점에서 다음 웹 페이지로 이동하며, 새로운 웹 페이지를 크롤링합니다.
4. 탐색 과정에서 현재 웹 페이지와 연결된 링크를 확인합니다. 방문하지 않은 링크를 선택하여, 해당 링크로 이동하여 새로운 웹 페이지를 크롤링합니다.
5. 크롤링된 웹 페이지에서 필요한 정보를 추출하거나 다양한 작업을 수행합니다. 예를 들어, 웹 페이지의 제목, 본문 내용, 이미지, 하이퍼링크 등을 수집하거나 분석합니다.
6. 탐색이 종료되면, 수집한 정보를 활용하여 원하는 목적에 맞는 작업을 수행합니다.

이제, Python과 BeautifulSoup 라이브러리를 사용한 웹 크롤러 구현에 대한 예제 코드를 살펴봅시다.

import requests
from bs4 import BeautifulSoup

def web_crawler(url):
    visited = set()

    def dfs(current_url):
        visited.add(current_url)
        print("Crawling:", current_url)

# 웹 페이지 크롤링 수행 (여기서는 예시로 간단하게 링크 출력)
        response = requests.get(current_url)
        soup = BeautifulSoup(response.text, 'html.parser')
        links = soup.find_all('a')
        for link in links:
            next_url = link.get('href')
            if next_url and next_url not in visited:
                dfs(next_url)

    dfs(url)

# 웹 크롤러 실행
web_crawler("<https://www.example.com>")

[코드1-1] DFS를 활용한 웹 크롤러 구현 코드

백트래킹: 깊이 우선 탐색을 활용한 효율적인 문제 해결

백트래킹은 깊이 우선 탐색(DFS)를 기반으로 한 알고리즘 기법으로, 조합 최적화, 스도쿠, N-퀸 문제 등 복잡한 문제를 효과적으로 해결하는 데 적합합니다. 가능한 모든 경로를 고려하되, 최적의 해를 찾는 과정에서 비효율적인 경로는 미리 제외함으로써 연산 시간을 크게 단축시킬 수 있습니다. 이러한 방식으로 DFS를 활용하여 현재의 선택이 유망하지 않다고 판단되면 백트래킹을 통해 이전 상태로 돌아가 다른 선택을 탐색합니다.

백트래킹은 다음과 같이 작동합니다:

1. 해결하고자 하는 문제에 대한 상태 공간 트리를 구성합니다. 이 트리는 모든 가능한 해답 후보를 표현합니다.
2. DFS 알고리즘을 활용하여 상태 공간 트리를 탐색하며, 유망한 선택만을 고려합니다. 이 과정에서 비효율적인 선택은 가지치기(pruning)를 통해 빠르게 제거합니다.
3. 현재 경로의 유망성을 평가합니다. 이 과정은 문제에 따라 다르지만, 예를 들어 스도쿠 문제에서는 같은 행, 열, 3x3 박스 내에 중복된 숫자가 없는지 확인하여 유망성을 판단합니다.
4. 유망한 선택 중 하나를 결정하고, 그 선택을 바탕으로 다음 단계를 진행합니다.
5. 선택한 경로가 최종적으로 유망하지 않다고 판명나면, 백트래킹을 통해 이전 상태로 돌아가 다른 선택을 탐색합니다.
6. 탐색이 완료되거나 적합한 해를 찾게 되면, 결과를 출력하거나 필요한 후속 작업을 수행합니다.

암호 해석과 패턴 탐색: 깊이 우선 탐색을 이용한 정교한 데이터 처리

깊이 우선 탐색을 활용한 암호 해석과 패턴 탐색 알고리즘은 문자열 분석, 데이터 압축, 이미지 처리 등의 영역에서 두각을 나타냅니다. 이 방법은 문자열이나 데이터 속에서 특정 패턴을 발견하거나 암호를 해석하는 과정에서 모든 가능성을 체계적으로 탐색합니다.

이 알고리즘은 다음과 같이 작동합니다:

1. 탐색의 시작점을 저장하고, 해당 위치를 방문했다는 표시를 합니다.
2. 시작점을 기준으로 가능한 다음 상태를 생성합니다.
3. 각 상태에 대해 패턴 일치나 암호 해석을 시도합니다.
4. 조건이 충족되거나 암호 해석이 성공하면, 그 결과를 반환하고 탐색을 종료합니다.
5. 조건이 충족되지 않거나 암호 해석이 실패한 경우, 다음 상태로 이동하여 2단계부터 반복합니다.
6. 모든 가능한 경우를 탐색한 후에도 결과를 찾지 못했다면, 패턴이나 암호 해석이 실패한 것으로 나타냅니다.

아래는 암호 해독 및 패턴 찾기 코드의 예시입니다:

def decrypt(ciphertext, dictionary):
    def dfs(plaintext, index):
        if index == len(ciphertext):
            return plaintext

        for word in dictionary:
            if len(word) <= len(ciphertext) - index and ciphertext.startswith(word, index):
                decrypted = dfs(plaintext + word, index + len(word))
                if decrypted is not None:
                    return decrypted

        return None

    return dfs("", 0)

# 암호 해독 예시
ciphertext = "abcdabcdabcd"
dictionary = ["ab", "cd", "abcd", "bc", "d"]

decrypted = decrypt(ciphertext, dictionary)

if decrypted is not None:
    print("암호 해독 결과:", decrypted)
else:
    print("암호 해독에 실패했습니다.")

[코드2-1] Python으로 구현한 암호 해독 및 패턴 찾기 코드

public class Decryptor {
    public static String decrypt(String ciphertext, List<String> dictionary) {
        return dfs("", 0, ciphertext, dictionary);
    }

    private static String dfs(String plaintext, int index, String ciphertext, List<String> dictionary) {
        if (index == ciphertext.length()) {
            return plaintext;
        }

        for (String word : dictionary) {
            if (word.length() <= ciphertext.length() - index && ciphertext.startsWith(word, index)) {
                String decrypted = dfs(plaintext + word, index + word.length(), ciphertext, dictionary);
                if (decrypted != null) {
                    return decrypted;
                }
            }
        }

        return null;
    }

    public static void main(String[] args) {
        String ciphertext = "abcdabcdabcd";
        List<String> dictionary = List.of("ab", "cd", "abcd", "bc", "d");

        String decrypted = decrypt(ciphertext, dictionary);

        if (decrypted != null) {
            System.out.println("암호 해독 결과: " + decrypted);
        } else {
            System.out.println("암호 해독에 실패했습니다.");
        }
    }
}

[코드2-2] Java로 구현한 암호 해독 및 패턴 찾기 코드

게임 및 퍼즐 해결 전략: 깊이 우선 탐색을 이용한 최적의 해답 탐색

깊이 우선 탐색을 이용하여 게임이나 퍼즐을 해결하는 방법은 게임 인공지능, 퍼즐 풀이, 추리 문제 등 다양한 분야에서 활용되는 핵심적인 전략입니다. 이 방법은 가능한 모든 상태를 체계적으로 탐색하여, 최적의 해답을 찾아내는 데에 사용됩니다.

게임이나 퍼즐을 해결하기 위한 DFS 알고리즘의 작동 방식은 다음과 같습니다:

1. 시작점인 현재 상태를 스택에 넣고, 해당 상태를 방문했다는 표시를 합니다.
2. 스택이 비어있지 않는 한, 아래의 단계를 반복합니다:
   1. 스택에서 가장 최근의 상태를 추출합니다.
   2. 해당 상태에서 가능한 모든 다음 상태를 생성합니다.
   3. 각 상태에 대해 게임 또는 퍼즐의 규칙을 확인합니다.
   4. 만약 규칙이 충족된다면, 그 해답을 반환하고 탐색을 종료합니다.
   5. 만약 규칙이 충족되지 않는다면, 가능한 다른 상태들을 스택에 추가하고 그 위치를 방문했다는 표시를 합니다.
3. 모든 가능한 상태를 탐색한 후에도 해답을 찾지 못했다면, 해당 게임이나 퍼즐이 해결 불가능하다는 것을 알려줍니다.

아래는 스도쿠 퍼즐을 해결하는 DFS 알고리즘의 예시입니다:

def solve_sudoku(board):
    def dfs():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(i, j, num):
                            board[i][j] = num
                            if dfs():
                                return True
                            board[i][j] = '.'
                    return False
        return True

    def is_valid(row, col, num):
        for i in range(9):
            if board[i][col] == num or board[row][i] == num or board[(row//3)*3 + i//3][(col//3)*3 + i%3] == num:
                return False
        return True

    dfs()

# 스도쿠 퍼즐 예시
board = [
    ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
    ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
    ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
    ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
    ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
    ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
    ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
    ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
    ['.', '.', '.', '.', '8', '.', '.', '7', '9']
]

solve_sudoku(board)

print("스도쿠 퍼즐 해결 결과:")
for row in board:
    print(' '.join(row))

[코드3-1] Python으로 구현한 스도쿠 퍼즐을 해결하는 DFS 알고리즘

public class SudokuSolver {
    public void solveSudoku(char[][] board) {
        dfs(board);
    }

    private boolean dfs(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(board, i, j, num)) {
                            board[i][j] = num;
                            if (dfs(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num || board[row][i] == num
                    || board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == num) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };

        SudokuSolver solver = new SudokuSolver();
        solver.solveSudoku(board);

        System.out.println("스도쿠 퍼즐 해결 결과:");
        for (char[] row : board) {
            System.out.println(String.join(" ", new String(row)));
        }
    }
}

[코드3-2] Java로 구현한 스도쿠 퍼즐을 해결하는 DFS 알고리즘

문제: 스도쿠 퍼즐 해결하기

문제 설명: 주어진 스도쿠 퍼즐을 해결하는 프로그램을 작성하십시오. 스도쿠 퍼즐은 9x9 크기의 격자로 이루어져 있으며, 각 격자 칸에는 1부터 9까지의 숫자 중 하나를 채워야 합니다. 다음은 스도쿠 퍼즐을 해결하는 방법입니다:

1. 빈 칸을 찾습니다. (숫자가 '.'인 칸)
2. 1부터 9까지의 숫자 중 가능한 숫자를 찾습니다.
3. 가능한 숫자를 하나씩 채워보고, 해당 숫자가 스도쿠의 규칙을 만족하는지 확인합니다.
4. 규칙을 만족하면 해당 숫자를 채우고 다음 빈 칸으로 이동합니다.
5. 모든 빈 칸을 채우고 규칙을 만족하는 숫자를 모두 찾으면 스도쿠 퍼즐을 해결한 것입니다.

입력

• board: 스도쿠 퍼즐의 초기 상태입니다. 9x9 크기의 2차원 배열이며, 숫자와 '.'으로 이루어져 있습니다. '.'은 빈 칸을 나타냅니다.

알고리즘 설명

주어진 코드는 DFS(깊이 우선 탐색) 알고리즘을 이용하여 스도쿠 퍼즐을 해결합니다. 다음은 알고리즘의 동작 과정입니다:

1. dfs 함수는 현재 스도쿠 퍼즐 상태를 입력으로 받습니다.
2. 모든 칸을 순회하면서 빈 칸을 찾습니다.
3. 빈 칸을 찾았을 때, 가능한 숫자를 하나씩 채워보고 규칙을 확인합니다.
4. 규칙을 만족하는 숫자를 찾았을 경우, 해당 칸에 숫자를 채우고 재귀적으로 dfs 함수를 호출합니다.
5. 재귀적인 호출에서 해결에 성공한 경우, 스도쿠 퍼즐을 해결한 것이므로 **True*를 반환합니다.
6. 가능한 숫자를 모두 시도해도 해결에 실패한 경우, 스도쿠 퍼즐을 해결할 수 없으므로 **False*를 반환합니다.

입출력 예시

입력

board = [    ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
    ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
    ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
    ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
    ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
    ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
    ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
    ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
    ['.', '.', '.', '.', '8', '.', '.', '7', '9']
]

출력

스도쿠 퍼즐 해결 결과:
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

제한 사항

• 입력 스도쿠 퍼즐은 항상 유효한 상태로 주어집니다.