[C++/16234] 인구 이동 - using BFS
문제 아이디어: BFS 연합 정보를 기록하는 vector를 만들어서 인구 수 차이가 연합을 생성할 수 있다면 vector에 좌표를 추가하고 마지막에 인구 수를 나눠서 저장한다. // 동 서 남 북 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int L, R; void process(vector &v, vector &unions, int x, int y, int index) { // 연결된 연합 도시 정보 vector united; united.push_back({x, y}); // BFS queue queue q; q.push({x, y}); unions[x][y] = index; int sum = v[x][y]; // 인구 수 총합 int count ..
[C++/3190] 뱀 - Implementation
문제 아이디어: 좌표를 저장하는 vector를 만들고, 사과가 없는 경우 꼬리를 자르기 위한 vector를 따로 만들어서 관리한다. #include #include #include using namespace std; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int main() { // N(보드 크기), K(사과 수), L(뱀 회전 수) int N, K, L; int result = 0; cin>>N; vector v(N, vector(N, 0)); cin>>K; for(int i = 0;i >a>>b; v[a - 1][b - 1] = 1; } vector snake; cin>>L; for(int i = ..
[C++/18405] 경쟁적 전염 - using BFS
문제 아이디어: BFS 바이러스의 위치 좌표를 queue에 넣어서 이를 확인하며 바이러스가 진행할 수 있는 칸의 값을 바꾸며 탐색을 진행한다. #include #include #include using namespace std; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int main() { // N(시험관 크기), K(바이러스 종류) int N, K; cin>>N>>K; vector v(200, vector(200, 0)); vector virus[1001]; for(int i = 0;i >temp; v[i][j] = temp; if (temp != 0) ..
[C++/1012] 유기농 배추 - using DFS
문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 아이디어: DFS DFS로 1이 붙어있는 곳은 다 방문하고 결과를 + 1한다. 그 다음 방문하지 않았고, 1인 공간에 대해서 DFS를 반복하면 총 몇개의 분리된 공간이 나오는지 확인할 수 있다. 완성 #include #include using namespace std; int M, N; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; void DFS(vector &v, vector &visited, int i, int j..
[C++/2178] 미로 탐색 - using BFS
BOJ 2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #include #include #include using namespace std; int N, M; // 동 서 남 북 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; void BFS(vector &v, vector &visited, int i, int j) { queue q; q.push({i, j}); visited[i][j] = true; while(q.empty() == false) { auto temp = q.fron..
