문제https://www.acmicpc.net/problem/16234 풀이이 문제는 BFS를 학습하기 위해 풀어본 문제이며 이 문제를 통해 BFS를 조금 알기 시작했다.... 문제에서는 각 칸마다 연합을 연결할 수 있는 나라인지 확인한 뒤 계속 인접 칸으로 이동해야 한다. 이러한 풀이 방식에서 인접 노드 탐색을 진행하는 BFS를 적용해야한다. bfs 함수를 실행하는 이중 for문은 각 칸마다 연합을 만들 수 있는지 검증하는 경우를 구현하기위해 사용했고, 해당 노드가 방문했던 노드임을 나타내는 visited 배열을 생성했으며 이 배열을 bfs 함수에 전달해 함수 내부에서 방문 여부를 확인해 방문 하지 않고, 함수에서는 상하좌우 방향의 노드와 현 위치의 노드 간의 차이가 문제에서 주어진 범위 안에 있다면 ..
그래프 탐색
1. 정의 우선 DFS와 BFS의 정의부터 간략하게 다시 알고 가도록 하자. DFS 깊이 우선 탐색이라는 이름에 맞게 탐색할 노드를 깊이를 우선으로 탐색하는 알고리즘이다. DFS의 구현은 Stack 또는 재귀적인 특징을 이용해 구현한다. BFS 너비 우선 탐색은 넓게 바로 아래 하위 노드를 모두 넓게 탐색한 뒤 그 아래의 노드들을 탐색하는 알고리즘이다. 큐를 이용해 탐색을 관리한다. 2. 구분 방법 그렇다면, 실제 코테나 문제를 해결할 때 무엇을 언제 사용해야하나? 우선 그 문제를 분석해봐야한다. 그래프 탐색에서 모든 정점을 방문하는가? DFS와 BFS 둘 다 가능하다. 경로의 특징을 저장 혹은 조합, 순열을 구해야 하는 문제인가? 고로타면 DFS를 이용하는게 유리하다. 최단 경로, 최단 거리를 구해야 ..
