Algorithm/BFS DFS17 [백준] 2468 안전영역 c++ 문제 링크 https://www.acmicpc.net/problem/2468 Key 0부터 제일 높은 지역의 높이까지 1씩 침수높이를 올려가면서 답을 찾으면 된다. 침수된 지역을 0으로 만들어 침수가 되지 않은 곳과 차별을 두었고, 이를 기반으로 0이 아닌 지역에 대해서 DFS탐색 하도록 하였다. 문제 조건에서 아무 지역도 물에 잠기지 않을 수도 있다고 했으므로 높이가 0일 때부터 탐색해야 한다. Code 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 48 49 50 51 52 53 54 55 56 57 58 59 6.. 2023. 3. 2. [백준] 4963 섬의 개수 c++ 문제 링크 https://www.acmicpc.net/problem/4963 Key 대각선까지 총 8방향을 탐색해야 하는 문제이다. 그것 외에는 다른 DFS,BFS유형의 문제들과 유사하게 순회 시 카운트를 증가하는 유형이기 때문에 쉽게 접근할 수 있었다. height이 열, width이 행을 뜻하기 때문에 입력을 height, width순으로 받아야 한다. 1. DFS풀이 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 48 49 50 51 52 53 54 55 #include #include #include #incl.. 2023. 3. 1. [백준] 10026 적록색약 c++ 문제 링크 https://www.acmicpc.net/problem/10026 다른 문제와 비슷하게 DFS순회할 때마다 카운트를 증가하는 문제이다. 다만, 적록색약의 경우 R과 G를 같은 것으로 보기 때문에, 정상인의 경우 -> R-R, G-G, B-B와 같이 같은 것을 만났을 때만 DFS순회를 하도록 하고, 적록색약의 경우 -> 정상인의 경우에 R-G, G-R 이 두가지 경우를 추가해주면 된다. Code 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 48 49 50 51 52 53 54 55 56 57 58 59 6.. 2023. 2. 28. [백준] 11724 연결 요소의 개수 c++ 문제 링크 https://www.acmicpc.net/problem/11724 평범한 dfs 문제였다. 1~6번까지의 노드가 있고, 1-2-3 4-5-6 이렇게 두개의 연결그래프가 있다고 예를 들어보면, 1부터 6까지 모든 노드를 탐색하면서 탐색을 할 때마다 카운트를 세주면 된다. 그렇게 되면 1번, 4번노드에서 각각 dfs를 하여 총 두번 탐색이 이루어진다. Code 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 #include #include #include #include #include const int MAX = 1001; using .. 2023. 2. 28. [백준] 1012 유기농 배추 c++ 문제 링크 https://www.acmicpc.net/problem/1012 백준 2667번 [단지번호 붙이기]와 거의 같은 문제이다. 문제 풀이 링크 >> https://everydayyy.tistory.com/101 DFS로 배열을 한번 순회할 때마다 카운트를 해주면 되는 문제이다. 주의할 점은, 테스트케이스마다 방문배열, 입력배열을 0으로 초기화해야 된다는 점. 아마 이부분 때문에 정답률이 낮았던 것 같다. Code 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 48 49 50 51 52 #include #inc.. 2023. 2. 27. [백준] 2667 단지번호붙이기 c++ 문제링크 https://www.acmicpc.net/problem/2667 DFS와 BFS 둘다 이용해서 풀이했다. DFS 주의사항 dfs재귀 함수를 호출할 때마다 count를 증가해선 안된다.--> dfs(nx,ny,count+1)이런식으로 매개변수로 넣으면 안된다는 뜻. 그 이유는, 일직선 상으로 생기지 않고 (ㅓ,ㅗ,ㅏ,ㅗ) DFS풀이 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 48 49 50 51 52 53 54 55 56 57 #define _CRT_SECURE_NO_WARNINGS #include #in.. 2023. 2. 27. 이전 1 2 3 다음
