Deff_Dev

문제https://www.acmicpc.net/problem/1012풀이BFS를 이용하여 그래프를 탐색하고 간선으로 이어져 있는 정점 갯수를 구했다.#include #include #include using namespace std;int m, n, k;int dx[4] = { 1,-1,0,0 };int dy[4] = { 0,0,1,-1 };vector answer;void BFS(int map [50][50], bool visited [50][50], vector > vec) { int count = 0; for (int i = 0; i > q; q.push({ vec[i].first ,vec[i].second }); visited[vec[i].first][vec[i].second] = tru..

문제https://www.acmicpc.net/problem/7576풀이BFS를 통해 익은 토마토(1) 주변 덜 익은 토마토(0)를 탐색하고 익은 토마토(1)로 바꿔준다. BFS가 끝난 후, 전체 맵을 탐색하고 덜 익은 토마토(0)가 있다면 -1 출력하고,덜 익은 토마토(0)가 없다면 맵에서 가장 큰 값을 출력한다. #include #include #include // https://www.acmicpc.net/problem/7576using namespace std;int m, n;int dx[4] = { 1,-1,0,0 };int dy[4] = { 0,0,1,-1 };vector> map;queue > q;void BFS(){ while (!q.empty()) { pair front = q.fron..

https://www.acmicpc.net/problem/2667  이 문제는 1로 이어진 아파트 단지 수와 각 단지내 집의 수를 오름차순으로 출력하는 문제이다.  풀이n의 갯수 만큼 이중 for문을 돌려 아직 방문하지 않은 1을 찾고, 해당 위치에서 bfs를 이용해 이어져있는 1을 탐색한다. 탐색이 완료되면 1의 갯수를 answer 벡터에 Push 한 뒤, 모든 탐색이 완료되면 answer 벡터를 오름차순으로 정렬하고 벡터의 size와 0부터 순서대로 출력한다.#include #include #include #include #include // https://www.acmicpc.net/problem/2667using namespace std;int n;int dx[4] = { 1,-1,0,0 };in..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 이 문제는 0과 1로 이루어진 미로에서 0은 벽을 나타내고, 1은 길을 나타낸다. 출발점은 (1, 1)이고 도착점은 (N, M)일 때, 출발점부터 도착점까지의 최소 칸 수를 출력하는 문제이다. DFS로 이 문제를 풀려고 시도했지만 해결하지 못하여 블로그의 풀이를 참고하여 BFS로 문제를 해결했습니다. DFS로 이 문제를 풀 경우, 연산이 많아져 시간초과가 나온다고 한다. 풀이 BFS를 이용하여 상하좌우로 탐색하고 목적지에 도달했을 경우 이동 거리를 출력하는 방법으로 풀이했다. #inclu..

9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 이 문제는 입력한 문자열에서 모든 괄호가 완성되면 "YES"를, 완성되지 못한다면 "NO"를 출력하는 문제이다. 스택의 top에 "("가 있고 푸시할 문자가 ")"일 때 pop을 하고, 그 이외의 경우에는 push한 뒤, 스택이 비어 있다면 "YES", 스택이 채워져 있다면 "NO"를 출력하는 방법으로 문제를 풀이했다. 풀이 #include #include #include using namespace std; int main(..

11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 이 문제는 여러 사람이 ATM에서 돈을 인출하는 데 걸리는 시간의 최솟값을 출력하는 문제이다. 최솟값이 될려면 오름차순으로 정렬한 뒤 처음부터 끝까지 더하면 된다. 풀이 #include #include #include // https://www.acmicpc.net/problem/11399 11399번 ATM using namespace std; int n; vector line; void ATM() { sort(line.begin(), line.end()); // 정렬 int resul..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 이 문제는 BFS를 사용하여 각 위치별 이동 시간을 계산한 후, 동생이 있는 위치에 도달할 때까지의 이동 시간을 출력하는 방법으로 풀이하면 된다. 풀이 #include #include // https://www.acmicpc.net/problem/1697 1697번 숨바꼭질 using namespace std; bool visited[100001] = { false , }; int result[100001] = { 0 , }; /..

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 이 문제는 DFS와 BFS를 처음 공부하기에 가장 좋은 문제 중 하나다. 입력한 간선을 토대로 양방향 그래프를 만들고 시작 지점부터 DFS, BFS를 이용해 탐색하면 된다. 풀이 #include #include // https://www.acmicpc.net/problem/1260 DFS와 BFS using namespace std; int map[1001][1001] = {0, }; // 맵 bool visited[1..