목록알고리즘 문제 풀이/BOJ (77)

영벨롭 개발 일지

[백준 BOJ][C++]7576번 토마토 풀이: BFS/DFS

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이 문제는 BFS를 사용하여 해결할 수 있습니다. M*N 크기의 토마토 농장에서 모든 토마토가 익을 때까지 걸리는 최소일은 익은 토마토로부터 시작해 그래프 탐색이 완료 되었을 때의 리프 노드 중, 최대 부모 노드의 수가 됩니다. 예시로 다음과 같은 3*3 토마토 농장을 들겠습니다. 0 0 0 0 0 0 0 0 1 index: x(col), y(row) 0 1 2 0 0 0 0 1 ..
알고리즘 문제 풀이/BOJ 2022. 2. 28. 15:25
[백준 BOJ][C++]4963번 섬의 개수 풀이: DFS/BFS

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이 문제는 DFS로 해결할 수 있습니다. 먼저 각 테스트 케이스마다 너비와 높이 w, h를 입력한 뒤 크기에 맞는 지도 정보를 map에 입력합니다. 지도 정보가 모두 저장되었다면 아직 방문하지 않은 땅(1)을 찾아 dfs()를 호출합니다. 이때 dfs()는 해당 땅 위치에서 연결된 모든 땅들을 탐색합니다. dfs()가 종료되면 섬이 하나 완성되었다는 것을 나타내므로 섬의 개수 cnt를 증가시..
알고리즘 문제 풀이/BOJ 2022. 2. 27. 20:39
[백준 BOJ][C++]2583번 영역 구하기 풀이: DFS/BFS

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이 문제는 재귀호출을 통한 DFS로 해결할 수 있습니다. 먼저 N*M 크기의 지도의 모든 위치에 해당하는 값을 0으로 set 해줍니다. K개의 직사각형에 대한 위치 정보가 주어지면 직사각형에 해당하는 위치를 지도에서 1로 set 해줍니다. 이제 아직 방문하지 않은 영역에서 dfs()를 호출합니다. 이때 영역의 넓이도 구해야하므로 dfs()를 호출하기 전 ret을 0으로 set한..
알고리즘 문제 풀이/BOJ 2022. 2. 27. 20:12
[백준 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
이전 Prev 1 ··· 7 8 9 10 11 12 13 Next 다음