BFS

[C++] 백준 11403번 경로 찾기

그래프 이론 문제. i에서 j로 가는 경로가 있다면 인접 행렬(AdjacentMatrixGraph)로 1을 나타내고 없다면 0을 나타내면 된다. DFS나 BFS를 이용해서 인접 행렬을 업데이트 하면 된다. 처음에는 자기 자신은 무조건 방문하므로 1인줄 알았는데, 두번째 테스트 케이스를 보고서 자기 자신을 돌아올 수 있는 경우에만 1이고 시작에만 자기 자신이 있다면 0이였다. DFS, BFS는 구현만 할 줄 알면 쉽게 풀 수 있다. 문제풀이 그래프 이론 문제는 개념만 알고 있으면 문제를 이해하는 것은 쉬우므로 바로 코드해석을 하겠다. 먼저 정점의 개수 vertex변수. 인접한 정점들의 번호를 담을 벡터 adjList, 각 정점마다 어떤 정점들을 갈 수 있는지 정보를 담을 인접행렬 check 2차원 배열을 ..

[C++] 백준 1697번 숨바꼭질

그래프 탐색 문제인 줄 몰랐던 그래프 탐색 문제. 알고보니 모든 정점들이 서로 연결돼 있던 그래프였다는 것을 문제에서 설명해 주고 있었다. 이 사실을 질문 검색 게시판을 보다가 알게되었다. 처음 이문제를 보았을 때 수학 문제인 줄 알았다. 그래서 경우의 수를 나눠서 구현해야 하는 줄 알고 그렇게 시도했다. 결과는 틀렸습니다가 나왔다. 그래서 어떻게 풀어야 할까 고민하면서 질문 검색 게시판을 보았다. 두번째 시도 게시판에서 보니 사람들이 그래프 탐색으로 많이 풀었다는 사실을 알게되었다. "이 문제를 어떻게 그래프 탐색으로 풀까..?" 고민하던 찰나에 머리에 다익스트라와 비슷한 알고리즘이 스쳐지나갔다. 게시판 검색 안했다면 아마 생각 못하지 않았을까 생각한다. 정말 많은 문제를 풀어봐야 겠다고 생각했다. D..

[C++] 백준 2606번 바이러스

그래프 문제. 그래프 이론을 알고있다면 쉽게 풀 수 있는 문제였다. 문제풀이 그래프 구현을 위해 vector와 bfs구현을 위해 queue STL을 사용했다. 정점의 개수와 간선의 개수를 받는 변수를 만들었다. adj_list 벡터를 사용해서 그래프를 구현했고 visit 배열로 방문한 정점인지 체크했다. result 변수로 결과값을 출력했다. 시작점은 어차피 1부터 시작하므로 따로 매개변수로 받아서 시작하진 않았다. 그리고 1번을 큐에 넣고 방문했다고 기록하고 반복문을 큐가 비어있지 않다면 계속 반복하게 했다. 현재 방문중인 정점과 연결된 정점들 중 방문하지 않은(혹은 큐에 들어가있지 않은) 정점들은 큐에 삽입하고 방문했다는 기록을 남긴다. 그리고 결과값에 1을 더해준다. 그래프 이론은 실버 정도의 난이..

[C++] 백준 1260번 DFS와 BFS

오랜만에 풀어보는 DFS와 BFS 문제였다. 그래프 이론을 알고 있다면 어려운 문제는 아니다. DFS란? 깊이 우선 탐색(Depth First Search)라는 그래프 탐색 방법 중 하나로, 방문해 나갈 수 있는 정점이 있다면 계속해서 탐색하는 것. 시작점이 루트가 되어서 깊이를 1씩 더해가는 방식이다. 보통은 재귀함수를 이용해서 구현한다. BFS의 시간복잡도는 n개의 정점과 m개의 간선이 있을 때, O(n + m)이다. 백트래킹(backtracking) 알고리즘이 DFS에서 파생됐다. BFS란? 너비 우선 탐색(Breadth First Search)라는 그래프 탐색 방법 중 하나로, 이번에 방문한 정점에서 방문해 나갈 수 있는 모든 정점을 모두 탐색하는 것을 의미한다. 보통은 자료구조 queue를 이용..