BFS

[알고리즘] 백트래킹(Backtracking)을 알아보자

요즘 백준 문제집을 풀고있는데, 백트래킹 개념의 문제가 나와서 한번 개념을 블로그에 정리해보려고 한다. # 등장 배경 이 글을 읽고있는 분들이라면 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 유명한 완전탐색 알고리즘은 한번쯤 들어본 적이 있을 것이다. 이러한 알고리즘은 모든 가능한 경우의 수를 탐색하는 특징이 있는데, 백트래킹도 이와 비슷한 motivation을 공유한다. 즉, '가능한 모든 방법'을 탐색하는 데에 관심사가 있는 것 ! 하지만 DFS와 BFS는 정말 모든 노드를 탐색한다. 그러다보면 해답이 될 가능성이 없는 그래프의 노드까지 "모두" 탐색하게 되는 것이다. 우리는 알고리즘 문제를 풀고있으므로, 전혀 가능성이 없는 노드는 관심이 없을 것이다. 따라서 백트래킹(Backtracki..

[알고리즘] 큐를 이용해 BFS 구현하기 (python)

오늘은 BFS 구현에서 주로 사용하는 큐에 대해 포스팅하고, 관련 적용 사례를 복습해보려고 한다. 사실 BFS/DFS 문제를 풀다보면 나는 DFS에 훨씬 더 익숙해서, DFS로 주로 풀이를 한다. 그 이유가 BFS 구현에서 큐에서 막히기 때문이라고 생각했고, 관련 포스팅을 하게된 것이다! # 큐(Queue) 우선 큐는 쉽게 말해서 다음과 같은 선입선출 구조이다. 먼저 들어온 요소가 먼저 나가는, 그런 것이다. BFS(너비우선탐색) 구현에는 큐를 이용하는 것이 정석인데, 그 이유는 BFS는 인접한 노드부터 차례로 넓게 탐색하는 알고리즘이기 때문이다. (BFS에 대해서는 따로 설명하지 않겠다) Python에는 친절하게도 deque 라이브러리가 존재해서, 큐 자료구조를 이용하고 싶을 때는 관련 라이브러리를 다..

[프로그래머스] 네트워크 (python) - BFS/DFS

# 문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i..