'dfs' 태그의 글 목록

[백준] 1260번 DFS와 BFS (C++)

문제 주소 백준 1260번 DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 알고리즘 DFS, BFS 풀이 간단한 DFS와 BFS 구현 문제이다. DFS는 재귀함수와 스택으로 구현할 수 있고, BFS는 q로 구현해야 한다. DFS를 하고 check배열을 초기화 해주어 BFS를 한다. #include #include using namespace std; int graph[1001][1001]; int check[1001]; int n, m; void dfs(i..

Problem Solve/DFS & BFS 2020. 3. 21. 15:37

[백준] 1023번 유기농 배추 (C)

문제 주소 백준 1012번: 유기농 배추 알고리즘 DFS, Flood Fill 힌트 Flood Fill 알고리즘을 사용하여 구역의 개수를 구한다. 풀이 배추들의 위치를 입력받기 전에 in배열과 check배열을 초기화 해주어야 한다. check가 되어 있지 않으면서 배추가 있는 곳을 탐색하여 주변 배추들이 있는 곳을 check한다. #include using namespace std; int n,m; int in[50][50]; int check[50][50]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; void fill(int a, int b){ check[a][b]=1; for(int i=0;i=n || nb>=m||nax; for(int q=0;q>m>>n>>c; f..

Problem Solve/DFS & BFS 2020. 3. 20. 23:50

[백준] 2485번 키 순서 (C)

출처 한국정보올림피아드 지역본선 2011 초등부 4번 문제 번호 백준 2458번 키 순서 코드업 4714 : 키 순서 알고리즘 DFS 힌트 나보다 큰 아이보다 작은 아이와의 관계는 알 수 없음 나보다 큰 아이보다 큰 아이는 나보다 큼 나보다 작은 아이보다 작은 아이는 나보다 작음 나보다 작은 아이보다 큰 아이와의 관계는 알 수 없음 풀이 들어오는 입력들을 그래프에 저장해 줄 때 1과 2로 구분하여 저장해줌으로써 누가 더 큰 아이인지 구분이 가능하게 해준다. 나보다 큰 아이들과 나보다 작은 아이들의 합이 전체 아이의 수 - 1 (n-1) 이라면 모든 나의 등 수를 알고있다고 할 수 있다. 따라서 dfs함수를 구현 할 때 몇 번째 아이에 대해 탐색할건지 n와 어느 방향에 대해(큰 아이들, 작은 아이들) 탐색..

Problem Solve/DFS & BFS 2020. 3. 20. 01:07

[백준] 2468번 안전영역 (C)

출처 한국정보올림피아드 KOI 2010 초등부 2번 문제 번호 백준 : 4697 안전 영역 코드업 : 2468번 안전 영역 알고리즘 DFS, Flood Fill 풀이 수면의 높이를 0부터 100까지 올려가면서 구역의 개수를 세어준다.(cnt) 각 수면의 높이마다 ans를 최대 값으로 갱신해준다. 매 높이 마다 구역을 새로 세어야 하기 때문에 check배열을 매번 초기화 해주어야 한다. #include using namespace std; int in[100][100]; int check[100][100]; int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; int n; void fill(int a, int b){ check[a][b]=1; for(int i=0;i=n||nb>=n..

Problem Solve/DFS & BFS 2020. 3. 15. 23:52

[코드업] 3500 : 지뢰 찾기 2 (C)

알고리즘 : DFS, Flood Fill 풀이 단순한 탐색 알고리즘 문제지만 다른 문제들과 다른점은 4방향이 아닌 8방향을 탐색해야 한다는 것이다. 방향배열을 8*2로 잡아주고 탐색을 해주면 된다. 문제를 풀기에 앞서 이해를 해보면 다음과 같다. 특정 칸의 숫자는 그 칸 주위의 8개의 칸 중에 지뢰의 개수를 나타낸다. 클릭한 칸에서 시작하여 (1)의 숫자가 0이 아닐때 까지 탐색한다. (이때 탐색도 8방향이다) 탐 탐색한 칸은 (1)의 숫자, 탐색하지 않은 칸은 _로 출력한다. 내가 선택한 칸이 지뢰일 경우 그 칸을 -1 나머지는 _를 출력한다. in배열은 입력 데이터 이고 map배열은 지뢰의 갯수를 세어 놓는 배열이다. ( 탐색이 끝나는 지점이 될 것이다. ) 처음에 in 배열을 모두 돌아 map 배열..

Problem Solve/DFS & BFS 2020. 3. 13. 01:50

[백준] 2667번 단지 번호 붙이기 (C)

출처 : KOI 1996 초등부 1번 알고리즘 : Flood Fill 풀이 Flood Fill 알고리즘을 그 이상 그 이하도 아니다. 알고리즘만 알면 간단히 풀 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include #include #include using namespace std; vector ans; int in[27][27]; int check[26][26]; int dir[4][2]={{0,1}, {0,-1}, {1,0}, {-1,0}}; int fill(int a, int b){ int c..

Problem Solve/DFS & BFS 2020. 3. 10. 15:13

[백준] 2606번 바이러스 (C)

출처 2004 전국 본선 초등3 힌트 단순 탐색 풀이 양방향 그래프를 만들어 준 뒤, 연결 되어 있는 컴퓨터들을 찾아가면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include using namespace std; int com[101][101]; int check[101]; int ans=-1; int v,e; void dfs(int n){ check[n]=1; ans++; for(int i=1;i>v>>e; for(int i=0;i>a>>b; com[a][b]=1; com[b][a]=1; } int n; dfs(1); cout

Problem Solve/DFS & BFS 2020. 3. 10. 07:32

[코드업] 2605 : 캔디팡 (C)

알고리즘 Flood Fill 풀이 문제 그대로 같은 색으로 이어진 칸들의 갯수를 세면 된다. 배열 범위를 벗어나는지 좀 더 편리하게 체크하기위해서 배열의 크기를 9*9로 잡아 주었다. 입력값에 0이 없기 때문에 in[i][j]가 0이라면 배열의 범위를 벗어난 것으로 확인할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142#includeusing namespace std; int in[9][9];int check[8][8]; // 한번 방문했던 곳 체크 int dir[4][2]={{1,0}, {0,1}, {-1,0}, {0,-1}}; // 방향배열 int ans; int search(int a,int b){ /..

Problem Solve/DFS & BFS 2020. 3. 9. 09:23

낭만 IT

dfs → (8)건