본문 바로가기

전체 글132

1743번, 2606번 - DFS, BFS 오늘은 실버 고티어 문제 두 문제를 풀었다.최근 DFS, BFS를 많이 풀다 보니, 푸는 시간도 줄었고, 큰 고민도 하지 않았다. 1745번 - 음식물 피하기문제:N x M 사이즈의 지도에 음식물이 있는 위치가 K 번 주어진다.이때 가장 큰 음식물의 크기를 구하여라. 풀이:힌트를 보면 그동안 푼 문제들과 크게 다르지 않다는 것을 알 수 있을 것이다. 특히 아래 문제와 매우 비슷하다.1303번 - 4방향 탐색(dfs) (tistory.com) 과정은 아래와 같다.1. 저장 시 queue 형태에 저장해준다.2. 모두 저장이 끝난 후, poll() 한 좌표에 이전에 방문한 적이 없다면,     해당 좌표와 연결된 음식물의 크기를 끝까지 추적하는 함수를 호출한다.3. queue가 빌 동안 2번 과정을 반복해준다.. 2024. 7. 23.
2178 - 미로 탐색(bfs) 실버1 문제이다. 문제:N, M 크기의 미로가 주어진다. 미로에서 1은 지나갈 수 있는 곳이고, 0은 막힌 곳이다.(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하시오  풀이:미로를 이동하는 방법은 무었일까? 당연하게도 지나갈 수 있는 길로 계속해서 이동하는 것이다.그렇다면 최소 거리를 구하는 방법은 무엇일까? 다음 과정을 살펴보자. 1. 시작 위치는 (1,1)이다.2. 시작위치에서 갈 수 있는 위치는 (2, 1) (1, 2)이다. 둘다 한칸만 이동하면 된다.3. 이후 (1, 2)에서 이동 할 수 있는 위치는 (2, 2)이다.4. (2, 1)에서 이동 가능한 위치는 (2, 2), (3,1) 이며, 이중 (2, 2)는 이동할 필요가 없다.     이미 (1,1)에서.. 2024. 7. 22.
1303번 - 4방향 탐색(dfs) 문제:위의 입력과 같이 주어진다.가로, 세로가 N, M으로 주어진다.다음 M개 줄에 B와 W가 적혀져 있으며, N개가 뭉쳐있을 때는 N^2의 위력을 낼 수 있다.W와 B의 위력을 알아내라. 풀이:어떤 문자가 모여있는 것은 해당 문자 주변을 탐색해서 찾아내야 할 것이다.고로 아래와 같은 과정으로 생각해보았다. 현재 위치에서 4방향(상, 하, 좌, 우)으로 이동하면서 같은 문자(B 또는 W)를 찾는다.이동할 수 있는 방향으로 이동해 다시 4방향(상, 하, 좌, 우)를 둘러본다. 다시 돌아가지 않기 위해 들렸던 위치에는 흔적을 남긴다.더이상 이동 할 수 없다면, (해당 구역의 합)^2을 저장한다.이렇게 생각해보니까 dfs()를 사용하고 있다는 것을 눈치챘다.가능한 한 깊이 있는 노드를 먼저 탐색하고, 더 이상.. 2024. 7. 20.
1260번 - BFS와 DFS BFS와 DFS라는 실버 1 문제이다.문제는 아래와 같다. 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.dfs() 메서드와 bfs() 메서드를 작성하여 문제를 풀 것이다. DFS(깊이 우선 탐색) 위와 같은 그래프가 있다. dfs는 말 그대로 깊은 곳부터 먼저 탐색하는 방법이다.이렇게 1 -> 2 -> 5 -> 11로 그래프의.. 2024. 7. 19.

티스토리툴바