목록전체 글 (246)

영벨롭 개발 일지

[백준 BOJ][C++]2468번 안전 영역 풀이: DFS/BFS

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 각 지역의 높이 정보 map를 입력받을 때 최소, 최댓값을 minh와 maxh에 기록해둡니다. 그렇다면 검사해야할 높이는 minh > map[i][j]; maxh = max(maxh, map[i][j]); minh = min(minh, map[i][j]); } } for (int h = minh; h < maxh; h++) { cnt = 0; init_visit(); for (int i = 0; i < ..
알고리즘 문제 풀이/BOJ 2022. 2. 27. 19:39
[백준 BOJ][C++]1987번 알파벳 풀이: DFS/BFS

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 DFS를 사용하여 해결할 수 있습니다. 이 문제의 답은 DFS를 했을 때 리프 노드의 부모 노드의 개수 + 1의 최댓값이 됩니다. 문제에 주어진 예시를 한 번 보겠습니다. 2 4 C A A B A D C B index: x(col), y(row) 0 1 2 3 0 C A A B 1 A D C B 이 정보를 가지고 DFS를 진행하게 되면 다음과 같이 됩니다. DFS의 특성 상 한 ..
알고리즘 문제 풀이/BOJ 2022. 2. 27. 18:34
[백준 BOJ][C++]11724번 연결 요소의 길이 풀이: BFS/DFS

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 이 문제는 BFS 또는 DFS 로 해결할 수 있습니다. 저는 재귀 호출을 이용한 DFS 로 해결하였는데요! 입력된 값으로 그래프의 정보만 잘 저장하면 쉽게 풀립니다. 먼저 정점의 개수 n과 간선의 개수 m을 입력으로 받은 뒤, 간선의 개수 만큼 두 정점이 연결된 간선의 정보를 받습니다. 이때 입력된 두 정점 u와 v가 연결되었음을 표시..
알고리즘 문제 풀이/BOJ 2022. 2. 27. 15:43
[백준 BOJ][C++]10026번 적록색약 풀이: BFS/DFS

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 이 문제는 BFS 알고리즘을 사용하여 해결할 수 있습니다. 먼저 init_visit() 함수와 all_visit() 함수는 각각 visit 배열을 0으로 초기화하는 함수와 모든 구역을 방문했는지를 체크하기 위한 함수입니다. 먼저 적록색약이 아닌 사람을 기준으로 탐색을 시작합니다. 모든 구역을 탐색해야지만 구역의 수를 알아낼 수 있겠죠? 그렇기 때문에 all_visit() 함수를 사용하여 모..
알고리즘 문제 풀이/BOJ 2022. 2. 27. 00:09
[백준 BOJ][C++]1012번 유기농 배추: BFS/DFS

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 BFS 또는 DFS로 해결할 수 있습니다. 먼저 배추밭을 나타낼 2차원 배열 map[][]과 각 배추의 방문 표시할 2차원 배열 visit[][]을 n*m 사이즈로 0으로 초기화 합니다. 각 테스트 케이스마다 배추밭의 모양이 달라지기 때문입니다. 이 과정을 init()이라는 함수를 따로 정의하여 테스트 케이스마다 호출하겠습니다. k개의 배추의 위치를 입력 받으면 map에서 해당 위치에 해당하는 원소..
알고리즘 문제 풀이/BOJ 2022. 2. 26. 23:05
[백준 BOJ][C++]2606번 바이러스 풀이: BFS/DFS

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 첫 번째 입력은 그래프의 노드 수, 두 번째 입력은 그래프의 엣지 수를 의미합니다. 그 다음 입력으로 엣지 수 만큼의 연결된 두 노드가 주어집니다. 처음 문제를 접했을 때, 엣지 정보를 저장하는 2차원 배열을 선언하고 이를 바탕으로 인접리스트로 전체 그래프를 만들었으나 틀렸습니다 ㅠㅠ 아마 시간이 너무 걸린듯 합니다. 때문에 두 노드 u, v 입력이 주어지면 그래프 g[u][v]와 g[v][u]를 1로..
알고리즘 문제 풀이/BOJ 2022. 2. 26. 17:53
이전 Prev 1 ··· 34 35 36 37 38 39 40 41 Next 다음