탐색
-
[백준 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를 모두 구분하도록 그래프를 탐색시켜 적록색약이 아닌 사람..