BFS
-
[Graph] 그래프의 탐색 - 너비 우선 탐색 (BFS, Breadth-First Search)알고리즘, 코딩테스트/알고리즘 개념 2023. 12. 18. 01:21
다양한 그래프 탐색 알고리즘이 있지만 가장 기본이 되면서 대표적인 알고리즘은 바로 DFS와 BFS다. 특히 DFS와 BFS는 탐색 방법이 상반되는 만큼 특징과 용도가 확실히 구분되는 편이기 때문에 두 탐색 방법 모두 확실히 이해하고 자유자재로 활용할 수 있어야 한다. 나아가 문제를 만났을 때 어떤 탐색 방식을 사용하는 것이 좋을지 결정할 수 있도록 그 특징을 이해하고 다양한 유형의 문제를 접해보는 것이 좋다. 너비 우선 탐색 (BFS, Breadth-First Search) DFS와 함께 대표적인 그래프 탐색 알고리즘 중 하나다. 깊이 우선 탐색인 DFS와 대조적인 탐색 방법으로 한가지 경로씩 끝까지 탐색하는 DFS와 달리 각 노드의 인접한 노드들부터 탐색해가는 특징을 가진다. 따라서 시작지점에 가까운 ..
-
[백준 BOJ/C++] 1240 노드사이의 거리알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 30. 02:07
1240번: 노드사이의 거리 간선정보를 입력받아 그래프의 최단거리를 구하는 문제다. 아주 기본에 가까운 문제라 최단거리 알고리즘의 기본기를 연습하기 좋은 문제라고 할 수 있다. 시작점과 끝점 여러개를 입력받아 거리를 구해야한다는 점과 문제 설명이 자세하지 않다는 점 정도가 고민해봐야할 부분이다. 문제 설명이 아주 간단한데 말 그대로 주어진 그래프에서 특정 두 노드의 거리를 구해주면 된다. 두 노드 사이의 간선에 방향성이 있는지, 여러개의 간선이 같은 두 노드 사이에 존재할 수 있는지 등 일반적인 그래프 탐색 문제에서 주어지는 설명은 한마디로 압축하고있다. 트리는 두 노드 사이에 간선이 하나만 존재하며 간선에 방향이 존재하지 않는다. 또한 트리는 사이클이 없는 그래프일 뿐이므로 BFS나 DFS와 같은 그래..
-
[백준 BOJ/C++] 10026 적록색약알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 25. 00:39
10026번: 적록색약 BFS, DFS 등을 이용해 2차원 맵을 탐색하는 그래프 탐색 문제다. 기본적이고 전형적인 유형에 아주 약간의 아이디어로 살짝 난이도를 올려놓아서 아주 까다롭지 않게 그래프 탐색 기본기를 익히기 좋은 문제라고 할 수 있다. RGB로 표현한 2차원 맵을 탐색하는 문제다. 보통 주어진 2차원 맵을 탐색하는 문제에서 요구하는 목표는 길을 찾거나 맵 상 구분되는 영역의 크기를 구하거나 영역의 수를 세는 형태로 자주 등장한다. 여기에 추가적으로는 맵을 변화시키는 등의 요소를 더하는 것이 대부분이다. 이 문제도 색상 지도와 적록색약을 가져와 결국 맵에 변화 요소를 주고 변화 전, 후의 영역의 수를 구하도록 하는 문제다. R과, G, B를 모두 구분하도록 그래프를 탐색시켜 적록색약이 아닌 사람..
-
[백준 BOJ/C++] 5214 환승알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 2. 02:00
5214번: 환승 단순한 최단거리 탐색 문제로 보이지만 의외로 정답비율이 낮은편이고 헷갈릴 수 있는 부분이 있는 문제다. 하이퍼튜브라는 컨셉을 문제에서 의도한대로 머릿속에 그리는데 어려움이 있었다. 문제 설명은 아주 짧고 간단하다. K개의 역이 주어지고 이 중 1번역에서 N번역까지 도달하는 최단경로를 찾아주면 된다. 간선에는 가중치도 없기 때문에 그냥 보기에는 상당히 간단해 보였다. 하지만 금방 하이퍼튜브라는 컨셉을 정확히 이해하지 못했음을 깨달았다. 주어지는 경로상 존재하는 역들을 모두 각각 연결하고 하이퍼튜브로 연결된 경로에 대한 비용은 1로 계산 하는 형태로 이해하고 풀었었는데 메모리 제한에 걸리는 상황이 발생했다. 문제의 설명도 너무 짧아 더욱 이해하기 어려웠다. 문제의 포인트 하이퍼튜브 컨셉 이..
-
[백준 BOJ/C++] 1707 이분 그래프알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 28. 01:04
1707번: 이분 그래프 이분 그래프 (Bipartite Graph) 의 개념을 알고있거나 문제에서 빠르게 이해했다면 그리 어렵지 않은 탐색 문제다. 하지만 문제의 설명이 짧고 친절하지도 않은 편이라 혼란스러울 수 있는 부분들이 있었다. 노골적으로 그래프 문제임을 보여주고있지만 자세한 설명이나 예시 없이 이분 그래프인지 아닌지를 판별하도록 하고있다. 이분 그래프라는 개념을 어느정도 알고 있었다면 그나마 접근이 용이하겠지만 그렇지 않은 경우 예시도 없는 한줄 설명 만으로 빠르고 정확히 이해하기에는 쉽지 않은 편이었다. 문제 자체에서 여러번 탐색이 필요하다거나 특정 알고리즘을 사용한다거나 구현 양이 많아지는 문제는 아니지만 생소할 수 있는 문제라 한번쯤 풀어보면 좋을 문제다. 문제의 포인트 이분 그래프의 개..