풀이 참고 https://yabmoons.tistory.com/319 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #define endl "\n" #define MAX_N 10001 using namespace std; typedef struct st { int num; int parent; int child[2]; int index;//몇 번째 자식인지 판별 }Node; int v, e, a,b, ancestor, subsize; int dist[MAX_N][2]; Node tree[MAX_N]; void init() { memset(dist, 0, sizeof(dist)); for (int i = 0; i < MAX_N; i..
1인곳을 만나서 visit상태가 아니면 bfs를 돌린다. bfs돌리게 되는 횟수 = 지렁이 개수 #define _CRT_SECURE_NO_DEPRECATE #include #include #include using namespace std; #define MAX 51 int n,t,m,k; int map[MAX][MAX]; bool vis[MAX][MAX]; int ypos[] = { 0,0,1,-1 }; int xpos[] = { 1,-1,0,0 }; int cnt = 0; void bfs(int i,int j) { queue q; q.push({ i,j }); vis[i][j] = true; while (q.size() > 0) { int y, x; tie(y, x) = q.front(); q.pop..
www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 활성 바이러스를 조합으로 구한 후 돌린다. 활성 바이러스는 비활성 바이러스가 있는 칸을 지나갈 수 있다. package algo0424; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super..
변을 기준으로 하는 bfs문제는 처음 풀었다. 방문 기준을 어떻게 해야할지 고민했는데 시작점과 끝점이 연결된 변을 방문 표시하기 위해서 (y,x,yy,xx)를 하나의 쌍으로 방문 배열에 넣고 같은 것이 있는지 찾았다. 만약 vis배열에 있다면 방문했던 곳이므로 answer를 증가시켜주지 않는다. function solution(dirs) { var answer = 0; let xpos=[0,0,1,-1];//DURL let ypos=[1,-1,0,0]; const dict={ 'D':0, 'U':1, 'R':2, 'L':3 }; let vis=[]; let y=5 let x=5; for(let i=0;i
1. 먼저 numbering함수에서 폭탄이 아닌 곳의 숫자를 쓴다. (for문으로 사방돌며 폭탄 몇개인지 체크, bfs필요없음) 2. 0인 곳의 처리 (bfs) 0인 곳은 연속으로 터지므로 큐에 0을 넣고 돌려 폭탄이 아닌 곳을 모두 폭탄(-1)로 바꿔준다. -1로 바꿔주는 것은 방문표시임과 동시에 더이상 터트릴 필요가 없어지는 숫자라고 생각하면 된다. 0의 개수만큼 cnt를 1증가시켜준다. 3. 1이상 숫자인 곳의 처리 마지막 배열 이중 포문을 돌면서 1이상의 숫자들은 일일히 눌러줘야하므로 만날때마다 cnt를 1증가시켜준다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Sc..
연결리스트를 만들어준 다음 bfs를 돌면서 각 단계의 큐의 개수로 answer를 업데이트해줬다. (각 단계의 노드 개수) function solution(n, edge) { const list={}; for(let i=0;i
www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 처음에 네트워크를 구하는 줄알고 dfs인 줄 알았으나 depth (친구의 친구)가 2인 곳까지만 탐색하므로 bfs로 풀었다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n,m; static ArrayList[]..
www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 추가 설명에 비에 모두 잠기지 않을 가능성이 있다고 했다. (비가 안오는 경우가 있다. 높이 모두 1인 곳의 기준) 최대 지역의 높이 = 비의 최대 강수량으로 놓고 모든 비의 높이에 따라서 bfs를 돌려준다. 비의 높이보다 낮은 곳은 모두 0으로 만든 후 여전히 양수인 (물에 잠기지 않은 곳)의 영역을 구해준다. import java.util.LinkedList; import java.util.Queue; import..
www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 중간 중간에 조건들을 처리해줘야 할 것이 많다. 디버깅이 안되서 아예 다시 풀었다. 도착지, 출발지 정보를 다 저장하고 taxi클래스를 또 따로 만들어줬다. 한 사람의 도착지 = 다음 승객의 출발지이거나 초기 택시 출발지 = 이미 승객이 거기 서있음 의 경우로 택시 위치의 승객은 또 따로 처리해줘야 된다. 각 승객은 (출발지 != 도착지) 정보를 가졌지만 모든 승객이 같은..
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net subset으로 집합을 나눈다. vis[번호]=true => a집합, false면 b집합 만약 리스트 두 개를 만들어서 각각 집어넣는다. 리스트 하나라도 길이가 0이다 => 나머지 몰빵 => 집합 2개가 안됨 => return 리스트 두 개의 길이를 합쳤는데 n이 안됨 => 집합이 3개 이상이라는 뜻 => return 그 다음에는 한 집합 내에서 bfs로 인접리스트를 돌리며 한 집합의 모든 원소가 연결되는 지 확인한 후 두 집합 합..