본문 바로가기

BFS

 (7)
[C++] 백준 2667번 - 단지번호붙이기 문제 2667번https://www.acmicpc.net/problem/2667 map에 넣을 입력값을 받을 때 공백이 없기 때문에 문자열로 한줄씩 받아줘야하는데 그냥 int로 받아버렸다. 그래서 한참 고민했다... 게다가 문자 하나하나를 비교하여 '1'이면 정수 1을 map에 넣어주고 '0'이면 0을 넣어줘야한다. 그런데 '1'인지 확인할 때 문자 표시인 작은따옴표를 쓰지 않아 숫자로 인식했다... #include #include #include #include #include using namespace std;int map[26][26];bool visited[26][26];vector result;int n;int x[4] = { 0,0,-1,1 };int y[4] = { 1,-1,0,0 };vo..
[C++] 백준 24445번 - 알고리즘 수업(너비 우선 탐색 2) 문제 24445번https://www.acmicpc.net/problem/24445 어제 문제에서 오름차순이 내림차순으로 바뀌었다. 그래서 정렬을 해줄 때 greater()를 추가해주면 내림차순으로 정렬할 수 있다. #include #include #include #include using namespace std;vector graph[100001];bool visited[100001];int result[100001];int cnt = 0;void bfs(int r) { queue q; q.push(r); visited[r] = true; cnt++; result[r] = cnt; while (!q.empty()) { int first = q.front(); q.pop(); for (int i ..
[C++] 백준 24444번 - 알고리즘 수업(너비 우선 탐색 1) 문제 24444번https://www.acmicpc.net/problem/24444  이번에는 너비 우선 탐색이다. 깊이 우선 탐색과는 bfs() 함수가 있는 부분만 다르다. 먼저 큐를 만들어 해당 정점을 넣어주고 방문처리를 한다. cnt를 하나 증가시킨 후 결과 배열에 넣어준다.  큐의 맨 앞 요소를 변수에 저장한 후 pop으로 빼준다. 그리고 해당 요소를 인덱스로 하여 그것과 이어져있는 점들의 크기만큼 반복해준다. 만약 방문한 점이라면 cnt를 1증가시키고 result 배열에 넣어준다. 그리고 넣어준 인덱스를 큐에 삽입하고 방문처리를 한다. 이 과정을 큐가 빌때까지 계속 반복해준다. #include #include #include #include using namespace std;vector gra..
[C++] 백준 1697번 - 숨바꼭질 으... 너무 졸리다... 문제 1697번 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #include #include #include using namespace std; int n, k; bool visited[100001]; void bfs(int n) { queue q; q.push({ n,0 }); while (!q.empty()) { int x = q.front().first; int cnt = q.fr..
[C++] 백준 2178번 - 미로 탐색 문제 2178번 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 흑흑... 또 까먹었다... 이것도 예전에 풀었던 건데... 다시 그걸로 공부하고 작성해 보았다. #include #include #include using namespace std; int map[100][100]; int n, m, k; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int bfs(int f, int s) { queue q; q.push({ f,s });..
[C++] 백준 2606번 - 바이러스 오늘도 dfs/bfs 문제~~ 문제 2606번 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 이 문제는 dfs나 bfs로 풀면 되는 문제인데, 나는 그냥 bfs로 접근해 count를 1씩 증가시켜가며 문제를 해결하였다. 어제 공부해놔서 그런지 쉽게 풀렸다. #include #include #include #include using namespace std; bool visited[1001]; vector node[1001]; void bfs(int..
[C++] 백준 1260번 - DFS와 BFS 예전에 공부했지만 까먹은 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 문제를 풀어보려고 한다. DFS와 BFS는 그래프를 탐색하는 방법이다. 여기서 그래프는 정점과 그 정점을 연결하는 간선으로 이루어진 자료구조를 말한다. DFS는 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동한다. BFS는 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동한다. 문제 1260번 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다...

티스토리툴바