dfs, bfs 1번문제 dfs코드

코딩테스트 [ ALL IN ONE ]

[코테 적용] 👉 [1번 문제] 완전 탐색 (후반부)

해결된 질문

작성

300

안녕하세요 bfs코드로 문제를 푸셨는데 이 문제를 dfs코드로 푸신 것도 볼 수 있을까요? (bfs로 푸신 것은 이해했습니다만 dfs는 dx, dy를 어떻게 적용해야하는지 궁금해서요)

또한 bfs는 최단거리 구할때 풀고 이외에는 dfs로 풀면 되는 것으로 아는데 애초에 bfs로 모든 문제를 접근하게 되면 최단거리 문제도 풀 수 있으니 dfs보다 포괄하는 문제유형이 많아서 효율적인 것이 아닌가요?

좋은 강의 해주셔서 감사합니다.

python 코딩-테스트 알고리즘

답변 2

개발남노씨

지식공유자

안녕하세요 oldcar27님

해당강의 교재에 문제풀이 코드들이 수록되어 있습니다~

학습에 참고하세요 :)

또한 문제를 풀다보면 구현단계에서 BFS보다 DFS가 자연스러운 경우가 있습니다. 왜냐하면 BFS는 큐의 관점에서 문제를 해결하는 것이고, DFS는 스택과 재귀 관점에서 문제를 해결하기 때문에 어떻게 접근방법을 떠올리냐에 따라서 둘 다 유용하게 사용할 수 있게 됩니다!

하나의 완벽한 알고리즘(문제해결방법)은 없으니 같은 문제를 다양한 방법으로 풀어보고, 각자의 스타일을 찾아가시면 좋습니다 ~

또 질문있으면 남겨주세요!

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

oldcar27님, dfs(깊이 우선 탐색) 코드에 대한 질문 주셨군요. dfs 방식에서도 dx, dy 배열을 이용해서 각 방향으로 탐색이 가능합니다. 간단한 코드 예시는 다음과 같습니다.

def dfs(x, y):
    # 방문 처리, 예를 들어 방문한 곳을 True로 마킹
    visited[x][y] = True
    
    # 탐색할 네 방향 정의 (상, 하, 좌, 우)
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    
    # 네 방향에 대해 탐색
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        # 특정 조건(예: 범위 내에 있고, 방문하지 않은 곳)을 만족하는지 체크하고 dfs 재귀 호출
        if <조건>:
            dfs(nx, ny)

bfs와 dfs의 사용은 문제의 특성에 따라 달라집니다. 맞습니다, 최단 경로 문제에는 주로 bfs가 사용되고, bfs로 모든 노드를 방문하는 것이 dfs보다 더 빠른 경우가 많습니다. 하지만, 경우에 따라 dfs가 더 유용한 경우도 있습니다. 예를 들어, 경로의 모든 경우를 탐색하거나, 백트래킹을 이용하는 문제 등에서는 dfs가 더 적합할 수 있습니다. 응용하고자 하는 문제의 유형을 정확히 파악하고 적절한 알고리즘을 선택하는 것이 중요합니다.

강의에 만족하셨다니 저희도 기쁩니다. 궁금한 사항이 더 있으시면 언제든 문의해 주세요. 감사합니다!

인프런 커뮤니티 질문&답변

dfs, bfs 1번문제 dfs코드