[Tip] DFS & BFS 🖍

이 글을 참고했다.

비교

이 글을 참고했다.

• DFS
  • 스택 또는 재귀 이용
  • 연결된 그래프를 완전 탐색하는데 활용 가능
  • 모든 경우를 하나하나 다 탐색을 해야 될 경우 이용 (대표적으로 조합 순열 구현)
  • 재귀적인 특징과 백트래킹(참고)을 이용한, 모든 경우를 하나하나 전부 탐색하는 완전탐색 문제를 풀때 선호
• BFS
  • 큐 이용
  • DFS와 마찬가지로 연결된 그래프를 완전탐색하는데 활용
  • depth(깊이)특징을 이용한 문제(대표적으로 최단경로)를 풀어야할때 선호한다.

문제를 푸는 입장에서는 다음과 같은 구분점이 필요합니다.

• 최단 거리 문제를 푼다면 BFS를 사용합니다.
• 이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS로 구현하는 것이 좋습니다.

구현

이 글을 참고했다.

DFS

⭕ DFS 장점

• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용합니다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있습니다.

❌ DFS 단점

• 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색합니다.
  효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용합니다.
• DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 해에 도착하면 탐색을 종료하기 때문입니다.

BFS

⭕ BFS 장점

• 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.

❌ BFS 단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

대표문제

이 글을 참고했다.

DFS를 이용한 순열, 조합 구현

정말정말 코딩테스트에 자주 나오는 기술이다.
사실 파이썬이나 뭐 여러 언어에는 자체적으로 내장된 순열 조합 라이브러리가 있다.
하지만 삼성테스트의 경우 내장 라이브러리를 사용하지 못 하게 하는 경우가 있어 구현법을 숙지해야될 필요성이 있기도하고
단순 순열,조합 라이브러리를 쓰기엔 경우를 선택하는 분기를 순열,조합을 구성할때 넣어줘야 되는 경우가 있기 때문이다.

재귀를 통한 조합 (Combination)

이 글을 참고했다.

조합은 순서가 상관이 없는 모임을 의미한다.
순서가 상관 없기 때문에 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은것으로 취급을 한다.
순서가 상관없기 때문에 1, 2, 3 이라는 3개의 숫자로 이루어져있다는 점에서 똑같은 취급을 하는 것이 조합이다.

{ 1, 2, 3, 4, 5 } 5개의 숫자 중에서 순서와 상관없이 3개의 숫자를 뽑으세요 ! 가 문제이다.
일단 대충 적어보자면 { 1, 2, 3 }, {1, 2, 4, }, {1, 2, 5} … , {2, 3, 4 }, {2, 3, 5}, …… {3, 4, 5} 이런식으로 쭉 나올것이다.
재귀로 조합을 구현할 때에는, 시작점을 결정한 이후, 그 전의 요소는 다시는 쳐다도 안본다는 것이 중요하다.

처음에는 시작점이 1일 것이다. {1, 2, 3} …. {1, 4, 5} 까지 쭉 나오고 이 다음에 시작점이 2가 될 것이다.
{2, 3, 4}, {2, 3, 5}… 여기서 보면.. 시작점이 2가 되는 순간, 1은 쳐다도 보지 않는다.

조합을 구현할 때, 하나의 시작점을 정한다면, 그 시작점 이전에 나온 원소들을 다시 쳐다보지 말자 !

# 조합 (combination)
# { 1, 2, 3, 4, 5 } 5개의 숫자 중에서 순서와 상관없이 3개의 숫자를 뽑으세요 !
# nCr -> 5C3

N, R = 5, 3

arr = [1,2,3,4,5]
visited = [False] * N

def printSel():
  for i in range(N):
    if visited[i]:
      print(arr[i], end=' ')
  print()

def dfs(idx, cnt):
  if cnt == 3:
    printSel()
    return

  for i in range(idx, N):
    if visited[i]:
      continue
    visited[i] = True
    dfs(i, cnt+1)
    visited[i] = False # backtracking

dfs(0,0)

핵심은 DFS(int Idx, int Cnt) 함수이다. 이 함수의 재귀를 통해서 모두 구하게 된다. 먼저 사용한 배열들에 대해서 보자. Arr[] 배열이 있고, Select[] 라는 배열이 있다. Arr[] 배열은 그냥 우리가 입력하는 숫자들을 저장하는 변수들이다. 저 배열에 들어있는 값들 중 3개를 뽑는 것이다. Select[] 배열이 굉장히 중요하다. 이 배열의 역할은 이미 선택한 숫자라면 선택하지 않고, 선택하지 않은 숫자라면 선택할 수 있음을 표시해주는 배열이다. Select배열의 역할이 중요한 이유는, 우리가 현재 구하고자 하는 것인 “중복을 허용하는 뽑기가 아니기 때문” 이다. 반대로, 이후에 나오는 ‘중복순열’, ‘중복조합’ 글에서 보면 알겠지만, 중복을 허용하는 수열을 구하는 과정에서는 Select배열이 사용되지 않는다. 하지만, 지금 우리는 중복을 허용하지 않는 수열을 구하는 과정이다. 따라서, Select배열을 통해서 어떤 값이 이미 뽑혔는지, 반대로 어떤 값이 아직 뽑히지 않았는지에 대해서 판단을 해주어야 한다.

Select[] 배열을 선언하고, 이 배열을 통해서 중복을 허용하지 않도록 만들어주자 !

조합을 구하는 함수에는 보통 2개의 매개변수가 들어간다. 위의 코드에서 보면 int Idx, int Cnt 이렇게 2개의 변수가 들어가져있다. 여기서 Idx가 위에서 계속 말한 시작점을 결정해주는 변수이고, Cnt는 몇 개를 뽑아야 하는지, 우리가 원하는 갯수만큼 뽑았는지를 판단하는 변수이다. 구체적으로 알아보자. [ Idx변수 - 시작점을 결정하는 친구구나 ! ] Idx가 사용되는 for문부터 천천히 알아보자. 보면 for(int i = Idx; i < Max; i++) 라고 되어있다. 초심으로 돌아가보자. 이 문구의 의미는 “i 라는 int형 변수는 Idx라는 값에서 시작하여서 1씩 증가하면서 Max까지 반복합니다.” 가 된다. 그 안에 내용을 말 그대로 풀어쓰자면 “i번째 값을 선택 했으면 그냥 지나가세요. 선택하지 않았다면 선택했다고 표시해주고, 재귀호출을 하겠습니다. 그리고 다시 선택하지 않았다고 표시해줄게요” 가 된다. 여기까지만 일단 알아놓자.

[ Cnt변수 - 우리가 몇개를 골랐는지 알려주는 친구구나 ! ] Cnt변수가 사용된 if문부터 보자. if(Cnt == 3) 이라고 되어있다. 사실 3이 아니여도 된다. 본인은 지금 5개 중에 3개를 선택하기 때문에 3을 적어놨을 뿐, 저 값은 우리가 골라야 하는 갯수를 적어주면 된다. 우리가 원하는 만큼 골랐다면, 그 이후 하려는 작업을 진행해주면 된다

조합을 구현할 때에는 2개의 매개변수를 이용해서 구현할 수 있다.

1. Idx변수 : 시작점을 결정해주는 변수이다. 우리는 Idx를 시작점으로 삼는 순간, Idx이전에 나온 원소는 쳐다도 보지 않을 것이다.
2. Cnt변수 : 우리가 현재 뽑은 원소의 갯수를 결정해주는 변수이다. 현재 뽑은 원소의 갯수가 우리가 최종적으로 뽑고자 하는 원소의 갯수와 일치한다면, 그 다음 프로세스를 진행하면 된다.

재귀를 통한 순열 (Permutation)

이 글을 참고했다.

순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다.
말 그대로, 순서가 존재하는 열 이라는 것이다.
즉 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } 등.. 모두 다른 결과를 가져온다. 순서가 다르기 때문이다.

조합 → { 1, 2, 3 } = { 2, 1, 3 } 이므로, 시작점이 2가 되는 순간 더 작은 요소인 1은 쳐다도 보지 말아라 ! 순열 → { 1, 2, 3 } != { 2, 1, 3 } 이므로, 시작점이 2가 되더라도 더 작은 요소인 1을 쳐다봐야 한다 !

# 순열 (permutation)
# { 1, 2, 3, 4, 5 } 5개의 숫자 중에서 순서를 고려하여 3개의 숫자를 뽑으세요 !
# nPr -> 5P3

N, R = 5, 3

arr = [1,2,3,4,5]
visited = [False] * N
V = []

def printSel():
  for i in range(len(V)):
    print(V[i], end=' ')
  print()

def dfs(cnt):
  if cnt == 3:
    printSel()
    return

  for i in range(N):
    if visited[i]:
      continue
    visited[i] = True
    V.append(arr[i])
    dfs(cnt+1)
    V.pop()
    visited[i] = False # backtracking

dfs(0)

백트래킹

이 글을 참고했다.

위의 예를 보기위해 DFS와 재귀적 개념, 그리고 백트래킹 알고리즘에 대한 추가적인 지식이 필요할 수 있다.

BFS를 이용한 최단경로 탐색

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기