김미썸코딩

BFS와 Brute force를 섞어야하는 문제였다. Brute force를 공부하기 전이라 관련 포스팅을 참고 하였다. 연구소에 세개의 벽을 세운후 퍼진 바이러스의 영향을 받지 않은 영역의 수의 최댓값을 구하는 문제다. 내 기준 굉장히 까다로운 문제였다.. 벽과 바이러스가 없는 0인 자리에 벽 3개를 세웠을 때의 모든 경우의 수를 따져야한다. ---> brute force 연구소 상태를 복사하여 테스트 할 이차원배열이 따로 필요하다 바이러스가 퍼진 후의 연구실 상태를 구하고 그 후, 그때의 0인 자리 수를 세야한다. ---> bfs 처음에 예시를 제대로 보지 않아 헷갈렸던 것 ---> 2의 바로 옆에만 벽을 세우는 게 아니다!!! (그래서 brute force) 벽을 3개 세워 볼 때마다 나오는 0인 ..

BFS와 DFS 두가지를 모두 이용하여 풀수 있는 문제다. 1. DFS #include #include #include //memset #include using namespace std; const int MAX = 1000 + 1; int N, M; vector connect[MAX];// 이차가됨 bool visited[MAX]; void DFS(int node) { visited[node] = true; // node에 연결된 다른 정점을 모두 방문 for (int i = 0; i >..

BFS를 활용하면 풀수 있는 문제다. 관련 포스팅을 참고한 후 풀었다. 중요한 건 한번 방문한 곳은 다시 방문하지 않게 해야한다는 것. pair를 사용해서 (위치, 시간) 쌍으로 queue에 넣었다. while문이 한바퀴를 돌 때 같은 초에 갈수 있는 같은 레벨의 위치들이 queue에 push되는데 queue에 일단 push 되면 같은 초(같은레벨) 인지 알 수 없기 때문이다. #include #include #include //memset using namespace std; const int MAX = 1000000 + 1; int N, K; bool visited[MAX]; int minSecond(int N, int K) { queue q; q.push(make_pair(N, 0)); visite..

BFS를 사용한 문제다 고려해야할 부분이 많아서 다소 까다로운 문제였다. 1. 1은 익은 토마토, 0은 안익은 토마토, -1은 토마토가 없음 ( 대각선은 영향을 받지 않는다.) 2. 트리를 생각햇을 때 익을 수 있는것이 다 익어서 트리가 완성 되었을 때의 트리의 레벨 수가 익기까지 걸린 일 수. 3. 익은상태로 시작하는 토마토가 여러개일 수도 있음 (토마토상태 입력받으면서 deque에 1인 토마토 push 필요) 4. 토마토가 비어있는 곳(-1)이 있을 때, 다 익을수도 있고 아닐수도 있음 --> 다익었는지 확인하는 함수 따로 필요 #include #include //#include //memset using namespace std; const int MAX = 1000; typedef struct {..

BFS와 DFS 두가지로 다 가능한 방법이다. 처음에 관련 포스팅을 참고하여 DFS로 푼후, BFS로도 풀어보았다. 1. 입력받은 N*N을 돌면서 1이고 방문하지 않은 곳일 경우 DFS or BFS함수를 호출한다. 2. 호출된 DFS함수는 '재귀'로 연결된 모든 곳을 찾으면서 cnt++하고 더이상 연결된 곳이 없어서 함수실행을 마친후엔 vector에 그 cnt(연결된 마을수)를 push_back 한다. 2-1. 호출된 BFS 함수는 '큐'로 연결된 모든 곳을 찾는다. while문 안에서 현재위치와 연결된 모든 곳을 큐에 넣고 현재위 치를 pop 한후의 front가 현재위치가 되어 연결된 곳이 더이상 없어 큐가 빌때 까지 반복한다. 1. DFS #include #include #include #includ..

DFS, BFS, Union-Find를 사용하여 풀수 있는 문제다. 1. DFS(재귀) #include #include #include //memset using namespace std; const int MAX = 100 + 1; int N, M; int adjacent[MAX][MAX];// 1이면 연결됨을 의미 bool visited[MAX]; int cnt; // DFS 재귀 void DFS(int v) { cnt++; for (int i = 1; i > N >> M; for (int i = 0; i > from >> to; adjacent[from][to] = 1; adjacent[to][from] = 1; } visited[1] = 1;..