오늘은 너비우선 탐색을 알아보겠습니다. DFS는 BFS와 같이 배우는 경우가 많은데요. BFS는 지난 포스팅에서 다루었기 때문에 필요하다면 참고해보셔도 좋을 것 같아요 〰️ DFS❓ DFS는 Depth First Search의 약자입니다. 너비 우선 탐색으로, 연결되어 있는 모든 노드를 전부 확인하고 그 다음 노드의 모든 노드를 살펴보는 방식으로 모든 노드를 탐색하는 방식이죠. DFS와 BFS의 비교는 지난 포스팅에서 이미 다뤘기 때문에 생략하겠습니다. DFS 구현 노드들이 연결되어 있다고 가정하겠습니다. 아래의 그림에서 왼쪽은 보기 편하게 도식화한 모습이고, 오른 쪽의 위는 linked List로 구현되어 있는 모습을 표시했습니다, Visited는 Boolean 타입의 Array입니다. 위의 그림에서 ..

프로그래머스 문제인 '단어 변환'을 해결해 봅시다. 문제를 먼저 살펴보도록 할게요. 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과..

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

안녕하세요 ❗️ 오늘은 굉장히 유명한 알고리즘인 BFS/DFS 중 BFS를 집중적으로 살펴보려고 합니다. 살펴보기 전, BFS/DFS를 적용하는데 있어서 '그래프 Graph'라는 자료구조를 사용하는데요. 지난 포스팅으로 '그래프 graph' 자료구조를 소개해드렸습니다. 만약, 그래프 자료구조가 무엇인지 모르시는 분들은 한 번쯤 읽고 가시는 게 좋을 듯 싶습니다 〰️ 이제부터 BFS가 무엇인지 알아가보도록 하겠습니다 ❗️ BFS ❓ 그래프의 모든 노드를 순회하고자 할때, 인접한 노드들을 우선으로 방문하도록 구현합니다. BFS와 비슷한 개념이 DFS는 Depth First Search이 있는데요. DFS는 시작 노드를 기준으로 다음 노드를 선택할 때, 선택한 분기를 끝까지 순회하고 나서 다른 분기를 확인합니..