DFS

문제 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 어떤 문제인가? 빈칸, 벽, 바이러스 총 세 종류로 맵을 채울 수 있다. 이때, 임의의 벽을 추가로 3개 세운다. 추가로 세운 벽의 위치에 따라 안전한 공간의 개수가 바뀐다. 임의의 벽을 세웠을 때 안전한 공간의 최대 개수를 출력하면 된다. 접근 방법 코드를 먼저 보면 복잡하고 이해하기 어려울 것 같으니 대략적인 문제풀이의 방향을 보고 코드를 보자! 1. map에 입력받기 이때, 바이러스의 위치와 빈..

문제 : https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 어떤 문제인가? 입력을 받으면 땅인 부분과 바다인 부분이 생긴다. 한 땅 덩어리가 하나의 연결 요소라고 생각하면 된다. 이때 연결 요소 내에서 한 정점에서 다른 정점으로 가는 최대 거리를 출력하면 되는 것이다. 접근 방법 int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; 한 정점에서 상, 하, 좌, 우로 움직이기 위한 배열이다. char map[..

문제 : https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 어떤 문제인가? 아주 간단한 문제이다. 기존의 상, 하, 좌, 우로 그래프를 탐색하던 방법에서 나이트의 이동 방식처럼만 움직이며 탐색하면 되는 문제이다. 나이트의 시작 위치와 도착 위치가 주어졌을 때 도착하는 최소 횟수를 출력하면 된다. 접근 방법 int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[8] = {1, -1, 2, -2, 2, -2, 1, -..

문제 : https://www.acmicpc.net/problem/1325 > n >> m; 문제에서 주어진 변수를 선언하고 입력받는다. while (m--) { int a, b; cin >> a >> b; graph[b].push_back(a); } 간선의 개수인 m번만큼 한 간선이 연결하는 두 정점을 입력받는다. 이때, 단방향 그래프임에 유의하여 b정점에 연결된 정점으로 a를 추가해준다. int maxNum = 0; vectorans; for (int i = 1; i maxNum){ maxNum=cnt; ans.clear(); ans.push_back(i); } else if(cnt ==maxNum){ ans.push_back(i); } for (int j = 0; j

문제 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 어떤 문제인가? 각 위치의 높이가 존재한다. 따라서, 0부터 최대 높이까지 모든 경우를 살펴봐야 한다. 잠기는 높이마다 생기는 연결 요소들의 개수가 바뀌게 된다. 이때, 어떤 높이에서 생기는 연결 요소의 최대 개수를 출력하면 된다. int map[101][101]; bool visited[101][101]; int n; 위치들의 높이를 저장할 이차원 배열과 방문 여부를 저장할 이차원 배열, n을..

문제 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 어떤 문제인가? 그래프를 입력받고 연결 요소의 개수를 출력하면 된다. 이 문제를 풀기위해선 먼저 연결 요소가 무엇인지 알아야 한다. 간단하게 말하면 나누어진 각각의 그래프들을 연결 요소라고 한다. 문제의 첫 번째 예시대로 입력을 받으면 1-2-5, 3-4-6이 연결된 두 개의 연결 요소가 존재하는 것이다. 접근 방법 한 정점을..

문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 어떤 문제인가? 그래프 탐색 방법인 dfs와 bfs를 통해 그래프를 탐색하는 순서를 출력하면 되는 간단한 문제이다. 접근 방법 bool visited[1001]; vectorgraph[10001]; 먼저 그래프를 저장할 벡터와 정점의 방문 여부를 저장할 배열이 필요하다. int n,m,v; cin >> n >> m >> v; 문제에서 주어진 변수들을 ..

문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 어떠한 그래프에 대한 깊이 우선 탐색과 너비 우선 탐색 결과를 각각 출력하면 되는 문제이다. 주의해야 할 점은 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다는 것이다. 따라서 그래프를 sort함수를 통해 오름차순으로 정렬해줘야 한다. 입력받은 v부터 dfs를 실행한 결과를 출력하고 그래프를 다시 초기 상태로 돌려놔 bfs..

문제 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 깊이 우선 탐색 알고리즘을 사용하면 아주 쉽게 풀 수 있는 문제다. 1번 컴퓨터와 연결된 컴퓨터에 대해서만 탐색을 하면 된다. #include #include using namespace std; bool visited[101]; vector graph[101]; int cnt=0; void dfs(int x){ cnt++; visited[x]=true; for(int i : graph[x])..