Python/이것이코딩테스트다with파이썬

18~20강 :: DFS 알고리즘, BFS 알고리즘

묘걍 2023. 11. 27. 20:26

👉🏻 DFS(Depth-First Search)

  • DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다
  • DFS는 스택 자료구조(혹은 재귀함수)를 이용한다
  • 구체적 동작 과정
    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
    2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
    3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다

- 매번 최 상단 원소를 기준으로 해서 방문하지 않은 인접 노드가 있으면 그 인접한 노드로 방문을 수행

👉🏻 DFS 동작 예시

출처: 이코테 유튜브

- 방향이 없는 무방향 그래프

- 인접한 노드가 여러개일 수 있다

     - 어떤 노드부터 방문할지에 대한 기준이 있어야 한다

     -  방문 기준은 문제에서 요구하는 내용에 따라 달라지거나 상관 없기도 하다

출처: 이코테 유튜브
출처: 이코테 유튜브

- 매번 스택의 최상단 노드 확인

- 인접한 노드 중에서 방문하지 않은 것에 방문

- 인접&방문X 노드가 여러개라면 조건에 맞게 방문

- 이제 2를 기준으로 시작

출처: 이코테 유튜브

- 1번과 7번이 있는데

- 1번은 이미 방문했고 7번은 방문한 적이 없기 때문에 7번으로

- 인접한 6번과 8번중 기준에 맞는 6번에 방문

 

- 이처럼 가장 깊은 부분부터 탐색

- 가장 깊게 들어갔다가 더 들어갈 수 없다면 다시 돌아와서 다른 방향으로 깊게 들어가는 방식

 

출처: 이코테 유튜브
출처: 이코테 유튜브
출처: 이코테 유튜브

👉🏻 DFS 예제

- 파이썬에서는 그래프를 표현하기 위해 2차원 리스트를 사용할 수 있다

- 일반적으로 그래프 문제가 출제되면 노드 번호가 1번부터 시작하는 경우가 많기 때문에 index 0에 대한 내용은 비워둔다

- index 1번부터 해당 노드의 인접한 노드가 무엇인지 리스트 형태로 담아줄 수 있다

     - 1번 노드와 연결돼있는 건 2, 3, 8번이라는 뜻

     - 2번 노드와 연결돼있는 건 1, 7번이라는 뜻

- 방문처리를 위해 1차원 리스트를 만듦

     - 모든 값을 False로 초기화 → 모든 노드를 하나도 방문하지 않은 것으로 처리

     - 1번 노드 ~ 8번노드를 가지고 있기 때문에 index0번은 사용하지 않기 위해서 일부러 하나 더 큰 크기로 만든 것

        - 코드 상에서 각 노드에서 -1을 적용해 처리할 수 도 있지만

          0은 사용하지 않는 방식으로 하는 게 번호를 그대로 맵핑해 직관적이다

- dfs 함수는 그래프 정보, 방문 처리 여부가 기록된 리스트를 이용

- 해당 노드를 방문처리

- 그 노드를 방문했다는 의미로 노드 번호 출력

- stack의 최상단에 있는 원소와 연결된 다른 노드를 하나씩 확인하며 인접한 노드가 방문되지 않은 상태라면 재귀함수를 이용해 방문 진행

     - 재귀적으로 방문하지 않은 노드를 방문함

     - 깊이 우선으로 최대한 깊게 그래프를 탐색

 

* C++ ver

https://github.com/ndb796/python-for-coding-test/blob/master/5/8.cpp

* Java ver

https://github.com/ndb796/python-for-coding-test/blob/master/5/8.java

 

 

👉🏻 BFS (Breadth-First-Search)

  • BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다
  • BFS는 큐 자료구조를 이용
  • 구체적 동작 과정
    1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다
    2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다
    3. 더이상 2번의 과정을 수행할 수 없을 때 까지 반복한다

- DFS수행시에서는 인접하지 않은 노드에 대해서? 다시 한번씩 큐에 넣으면서 방문한다는 특징

   (인접한 노드 중 방문하지 않은 노드에 대해서가 맞는 설명이겠지..?)

- BFS는 해당 시점에서 인접한 노드를 한 번에 전부 큐에 넣는다는 점이 다르다

- DFS와 마찬가지로 다양한 대기업 문제에서 출제되고 있다

- 특정 조건에서의 최단경로 문제 해결 위한 목적으로 효과적으로 사용

- 큐 자료구조를 사용하기 때문에 언어마다 큐 자료구조를 어떻게 구현하는지 알아야해

출처: 이코테 유튜브

- 방향성 없는 무방향 그래프

- 특정 노드에 대해서 인접한 노드가 여러개

출처: 이코테 유튜브

- 1번 노드 방문처리

- 큐에 넣음 (위에서 들어와서 아래로 나간다)

출처: 이코테 유튜브

- 큐에 들어 있던 원소인 1을 꺼내서 1에 대해 처리

- 현재 처리 중인 노드는 하늘색    

- 방문처리 수행한 노드는 회색    

- 2, 3, 8을 차례대로 큐에 넣고 방문처리

     - 작은 번호부터 넣음

출처: 이코테 유튜브

- 가장 밑에 있는 2를 꺼내 2에 대해 처리

- 인접한 노드 1과 7이 있는데 1은 이미 방문처리 되었기 때문에 7을 큐에 넣어준다

출처: 이코테 유튜브

- 다음으로 3을 꺼내 3에대해 처리

- 3번 노드와 인접한 노드이 1, 4, 5 중에

   1은 방문처리 되었기 때문에 4, 5를 순서대로 큐에 넣어 방문처리한다

출처: 이코테 유튜브

- 8번 노드를 꺼내 처리함

- 8번 노드의 인접 노드는 1, 7이 있으나 이미 모두 방문처리 되었기 때문에 8만 꺼내고 무시한다

출처: 이코테 유튜브

- 거리가 가까운 것 부터 탐색됨

     - 1번의 경우 2, 3, 8이 거리가 1이기 때문에 시작 노드와 가까운 것들 부터 처리된 것을 볼 수 있다.

     - 거리가 가장 먼 6번 노드가 가장 마지막에 처리

- 이러한 특징 때문에 각 간선의 비용이 모두 동일한 상황에서 최단거리 문제를 해결하기 위한 목적으로 활용되기도 함

 

👉🏻 BFS 예제

- 큐를 위해 덱 라이브러리 불러오기

- 그래프에서 0번 노드에 대한 내용은 비워 1~8에 대해서만 처리하도록 한다

     - 각 노드와 연결된 인접 노드 표현

- 방문 처리를 위해 visited 리스트를 만든다

- bfs 함수는

- 실행 노드를 큐에 넣고, 해당 노드를 방문처리

- 큐가 빌 때까지 실행

- 큐에서 하나의 원소를 뽑는다. 이때는 먼저 들어온 원소를 꺼낸다

- 해당 노드의 번호를 출력하고

- 해당 노드의 인접 노드 중 아직 방문하지 않은 원소를 큐에 모두 삽입해 방문 처리를 수행한다

 

* C++ ver

https://github.com/ndb796/python-for-coding-test/blob/master/5/9.cpp

 

* Java ver

https://github.com/ndb796/python-for-coding-test/blob/master/5/11.java

문제1️⃣. 음료수 얼려 먹기

🧩 문제 설명

출처: 이코테 유튜브

- 연결 요소(connected component)찾기

🧩 문제 조건

출처: 이코테 유튜브

- 전체 얼음틀의 공간은 100만개 이하

💡 스스로 풀어보기

DFS를 활용할 방법을 생각했지만 코드로 구현하지는 못함😔

🧩 문제 해결 아이디어

출처: 이코테 유튜브

- 그래프 형태로 모델링

- 각 위치에서 상하좌우로 연결된 위치들은 서로 인접한 노드로 표현할 수 있다

- 이 때 특정 지점에서 DFS / BFS를 수행해 이동 가능한 모든 경로에 대해서 모두 방문처리를 함

- DFS를 이용해 모든 위치에 대해서 현재 방문한 위치와 연결된 인접한 노드에 대해서도 반복적으로 DFS를 호출해 연결된 모든 노드들을 방문

💡 예시 답안

- n과 m 그리고 이차원 리스트의 맵 정보를 입력받는다

    - 그래프는 공백 없는 0과 1로 이루어진 문자열로 주어지기 때문에

      한 줄을 입력 받고 각 원소를 정수로 바꿔 리스트로 만든다

- n × m 크기의 각 위치에서 dfs를 수행한다

- 현재 위치에서 DFS를 수행해 방문처리가 되었다면 카운트를 진행한다

- dfs 함수에서

- 주어진 범위를 넘어갈 경우 종료되게 한다 (0~n-1 ,0~m-1)

- 범위를 넘지 않았고, 현재 노드를 아직 방문하지 않았다면, 방문처리를 한다 (1로 바꿔줌)

- 결과적으로 True 값을 반환

- 현재 위치에 대해서 처음 dfs가 수행된 것이기 때문에 그 위치에 대해서 result 값을 증가

- 연결된 모든 노드에 대해서 방문처리를 진행할 수 있도록 하기 위해서

   상하좌우 모든 위치에 대해 재귀적으로 dfs 함수를 호출

     -  여기서 호출되는 내용들은 리턴값을 사용하지 않기 때문에

        단순히 연결된 모든 노드에 대해 방문처리를 수행하기 위한 목적으로 사용된다

- dfs는 한 번 수행되면 해당 노드와 연결된 모든 노드들도 방문처리 할 수 있도록 하고

  그 시작점 노드가 방문처리됐다면 (= 처음 방문하는 것이라면) 그때만 result 값을 증가시킴

더보기
  1. def dfs(x, y):: DFS 함수를 정의합니다. 시작 노드의 좌표를 매개변수로 받습니다.
  2. if x <= -1 or x >= n or y <= -1 or y >= m:: 주어진 범위를 벗어나는 경우 함수를 즉시 종료합니다.
  3. if graph[x][y] == 0:: 현재 위치의 노드를 아직 방문하지 않았다면,
  4. graph[x][y] = 1: 해당 노드를 방문 처리합니다.
  5. dfs(x - 1, y), dfs(x, y - 1), dfs(x + 1, y), dfs(x, y + 1): 현재 노드에서 상, 하, 좌, 우로 인접한 노드들을 재귀적으로 방문합니다.
  6. return True: 현재 노드에서 DFS를 시작하여 연결된 모든 노드를 방문했음을 의미하는 True를 반환합니다.
  7. return False: 현재 노드가 이미 방문된 경우에는 False를 반환합니다.
  8. n, m = map(int, input().split()): N과 M을 공백을 기준으로 입력받습니다.
  9. graph = []: 빈 리스트 graph를 생성합니다.
  10. for i in range(n):: N번 반복하며,
  11. graph.append(list(map(int, input()))): 각 행에 대한 0과 1로 이루어진 리스트를 입력받아 graph에 추가합니다.
  12. result = 0: 결과값을 저장할 변수 result를 초기화합니다.
  13. for i in range(n):: N번 반복하며,
  14. for j in range(m):: M번 반복하며,
  15. if dfs(i, j) == True:: 현재 위치에서 DFS를 수행하고, 반환값이 True인 경우 (연결된 모든 노드를 방문한 경우),
  16. result += 1: 결과값을 1 증가시킵니다.
  17. print(result): 최종 결과값을 출력합니다.

 

  1. 사용자에게 N과 M 값을 입력받습니다. 이때, N은 행의 개수, M은 열의 개수를 나타냅니다.
  2. 빈 리스트 graph를 생성합니다. 이 리스트는 2차원 배열의 형태로 입력된 데이터를 저장할 공간입니다.
  3. for i in range(n):: N번 반복하면서 행에 대한 정보를 입력받습니다.
    a. graph.append(list(map(int, input()))): 각 행에 대한 0과 1로 이루어진 리스트를 입력받아 graph에 추가합니다. 이때, map(int, input())는 사용자로부터 입력받은 문자열을 각 문자를 정수로 변환하여 리스트로 만드는 역할을 합니다.
  4. 결과값을 저장할 변수 result를 초기화합니다.
  5. for i in range(n):: N번 반복하면서,
    a. for j in range(m):: M번 반복하면서,
 i. `if dfs(i, j) == True:`: 현재 위치에서 DFS를 수행하고, 반환값이 True인 경우 (연결된 모든 노드를 방문한 경우),

 ii. `result += 1`: 결과값을 1 증가시킵니다.

6. print(result): 최종 결과값을 출력합니다.

 

이제 각 단계를 정리하면 사용자가 입력한 N과 M에 따라 2차원 배열의 데이터를 입력받고, 그래프의 각 노드를 DFS를 통해 방문하여 연결된 모든 노드를 찾습니다. 이후에 찾은 영역의 개수를 최종적으로 출력합니다.

 

* C ++  ver

출처: 이코테 유튜브

* Java ver

https://github.com/ndb796/python-for-coding-test/blob/master/5/10.java

문제2️⃣. 미로 탈출

🧩 문제 설명

출처: 이코테 유튜브

🧩 문제 조건

출처: 이코테 유튜브

💡 스스로 풀어보기

모르겠다..

🧩 문제 해결 아이디어

출처: 이코테 유튜브

- BFS 문제는 간선의 비용이 모두 같을 때 최단 거리를 탐색하기 위해 사용할 수 있는 알고리즘

출처: 이코테 유튜브

- 첫 번째 위치인 (1,1)에서 BFS를 수행한다

- 인접한 노드 중에서 1인 노드로만 이동

     - 큐에 원소를 넣어 방문처리할 때 원소의 값이 1인 원소에 한해서만 BFS를 진행한다

출처: 이코테 유튜브

- 이번에 방문한 노드까지의 거리를 2로 기록

     - 이 문제에서는 시작 위치와 마지막 위치를 포함해서 마지막 위치까지 도달하는 최단 경로에 포함된 노드의 수를 출력

- 현재 노드도 큐에 담기게 되고

   해당 노드를 꺼내 상하좌우를 확인하고 인접한 1을 가진 노드까지 방문을 수행

     - 다음 노드를 큐에 넣을 때 방문 처리를 수행하고 이 노드까지는 거리가 3으로 기록

- 매번 새로운 지점을 방문할 때 이전 지점까지의 최단 거리 +1 하는 방식

출처: 이코테 유튜브

💡 예시 답안

- 입력받기

- 네 가지 방향 벡터를 정의한다

- bfs 함수를 호출

- deque를 이용해 큐를 구현

- 초기에 x와 y로 이루어진 튜플 데이터를 담는다

- 큐가 빌 때 까지 bfs를 수행한다

- 반복시마다 큐에 있는 원소 하나를 꺼내 현재 위치에서 네 가지 방향으로의 위치를 확인

- 연결된 위치가 공간을 벗어난 경우와 괴물이 있는 경우는 무시한다

- 해당 노드를 처음 방문할 때만 최단 거리를 기록할 수 있도록 한다

- 직전 노드 위치에서의 최단거리 +1 값을 넣는다

- 다음 이동 위치까지는 1만큼 거리가 더 먼 곳이기 때문에 큐에 데이터를 넣어 거리 값을 1 증가

- 결과적으로 bfs 수행한 뒤 가장 오른쪽 아래까지의 최단거리를 반환

더보기
  1. def bfs(x, y):: BFS 함수를 정의합니다. 시작 노드의 좌표를 매개변수로 받습니다.
  2. queue = deque(): BFS에서 사용할 큐를 선언합니다. deque는 양쪽에서 빠르게 삽입, 삭제할 수 있는 큐 구조를 제공합니다.
  3. queue.append((x, y)): 시작 노드의 좌표를 큐에 추가합니다.
  4. while queue:: 큐가 빌 때까지 반복합니다.
    a. x, y = queue.popleft(): 큐에서 좌표를 하나 꺼내옵니다.
    b. for i in range(4):: 상, 하, 좌, 우 네 방향에 대해서 확인합니다.
 i. `nx = x + dx[i]`: 다음 위치의 x 좌표를 계산합니다.
 
 ii. `ny = y + dy[i]`: 다음 위치의 y 좌표를 계산합니다.

 iii. `if nx < 0 or nx >= n or ny < 0 or ny >= m: continue`: 다음 위치가 미로 찾기 공간을 벗어난 경우 무시합니다.

 iv. `if graph[nx][ny] == 0: continue`: 다음 위치가 벽인 경우 무시합니다.

 v. `if graph[nx][ny] == 1:`: 다음 위치를 처음 방문하는 경우에만 최단 거리를 기록하고 큐에 추가합니다.

     - `graph[nx][ny] = graph[x][y] + 1`: 다음 위치의 최단 거리를 현재 위치의 거리 + 1로 갱신합니다.

     - `queue.append((nx, ny))`: 다음 위치의 좌표를 큐에 추가합니다.
  1. return graph[n - 1][m - 1]: 가장 오른쪽 아래까지의 최단 거리를 반환합니다.
  2. from collections import deque: 덱(Deque)을 사용하기 위해 라이브러리를 불러옵니다.
  3. n, m = map(int, input().split()): N과 M을 공백을 기준으로 입력받습니다.
  4. graph = []: 빈 리스트 graph를 생성합니다.
  5. for i in range(n):: N번 반복하며,
    a. graph.append(list(map(int, input()))): 각 행에 대한 0과 1로 이루어진 리스트를 입력받아 graph에 추가합니다.
  6. dx = [-1, 1, 0, 0]과 dy = [0, 0, -1, 1]: 이동할 네 가지 방향을 정의합니다. 위, 아래, 왼쪽, 오른쪽 순서입니다.
  7. print(bfs(0, 0)): BFS 함수에 출발점 (0, 0)을 넣고 실행한 결과를 출력합니다.
  1. 사용자로부터 N과 M 값을 입력받습니다. 이때, N은 행의 개수, M은 열의 개수를 나타냅니다.
  2. 빈 리스트 graph를 생성합니다. 이 리스트는 2차원 배열의 형태로 입력된 데이터를 저장할 공간입니다.
  3. for i in range(n):: N번 반복하면서 행에 대한 정보를 입력받습니다.
    a. graph.append(list(map(int, input()))): 각 행에 대한 0과 1로 이루어진 리스트를 입력받아 graph에 추가합니다.
  4. 이동할 네 가지 방향을 정의합니다. dx = [-1, 1, 0, 0]과 dy = [0, 0, -1, 1]는 상, 하, 좌, 우 방향으로의 이동을 나타냅니다.
  5. def bfs(x, y):에서 BFS 함수를 정의합니다. 시작 노드의 좌표를 매개변수로 받습니다.
  6. 큐를 선언하고 시작 노드의 좌표를 큐에 추가합니다.
  7. 큐가 빌 때까지 반복합니다..
    a. 큐에서 좌표를 하나 꺼내옵니다.
    b. 상, 하, 좌, 우 네 방향에 대해서 확인합니다
 i. 다음 위치가 미로의 범위를 벗어나면 무시합니다.

 ii. 다음 위치가 벽이면 무시합니다.

 iii. 다음 위치가 아직 방문하지 않은 위치인 경우,

     - 최단 거리를 갱신하고 큐에 다음 위치를 추가합니다.
  1. BFS 함수가 끝나면, 가장 오른쪽 아래까지의 최단 거리를 반환합니다.
  2. BFS 함수에 출발점 (0, 0)을 넣고 실행한 결과를 출력합니다.

이렇게 코드는 네 가지 방향으로 이동하면서 최단 거리를 계산하는데, 큐에는 현재 위치에서 갈 수 있는 모든 이동 가능한 위치가 차례로 추가되어 BFS가 진행됩니다. 이런 방식으로 BFS는 출발점에서 목적지까지의 최단 거리를 탐색합니다.

* C++ ver

https://github.com/ndb796/python-for-coding-test/blob/master/5/11.cpp

 

* Java ver

https://github.com/ndb796/python-for-coding-test/blob/master/5/11.java

 

 

 

 

 

 

 

 

출처: https://youtu.be/1vLqC1rItM8?si=duiCuBUMP06oRoLH

https://youtu.be/CJiF-muKz30?si=J3e7cF3Sv2dum_Oc

https://youtu.be/e7_H8SLZlHY?si=BQXmAwwFApenKvGI