가취공부하자

BFS란? BFS (Breadth-First Search) : 너비 우선 탐색 출처 https://developer-mac.tistory.com/64 출발노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이며 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법으로 큐로 구현됨. 다시 말하면 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하여, 먼저 들어온 노드가 먼저 나가게 되어 가까운 노드 부터 탐색하게 됨. - 동작 과정 1) 시작 노드를 큐에 삽입하고 방문 처리 2) 큐에서 노드를 꺼내 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 3) 2번의과정을 더이상 수행할 수 없을 때까지 반복 주로 두 노드의 최단 경로를 찾고 싶을 때 사용된다. 구현 코드 from co..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net bfs 사용 #include #include #include using namespace std; typedef pair Info; int x, y, z; bool visit[101][101][101] = { false, }; int tomato[101][101][101] = { 0, }; int dx[6] = { 1,-1,0,0,0,0 }; int dy[6] = { 0,0..

문제 www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제풀이 1. 섬끼리 분류하기 위해서 각 섬에게 id를 할당한다. 2. A섬에서 B섬까지의 거리를 구한다. void bfs_ground(int a, int b, int id) { queueq; int x, y, next_x, next_y; x = a, y = b; q.push({ a,b }); visit[x][y] = true; while (!q.empty()) { x = q.front().first; y = ..

문제 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 문제 풀이 bfs사용 내가 푼 풀이... 찾아보니까 너무 복잡하게 생각한 것 같다. 더보기 하나의 노드를 확인할 때마다 visit을 확인해주어야 한다고 생각했다. #include #include #include using namespace std; vector relation(101); bool visit[101] = { false, }; int bfs(int x, int y) { queue..