Algorithms/DFS & BFS 검색 결과

해당 글 23건

[BOJ 2206] (DFS/BFS) 벽 부수고 이동하기 (C++)

벽 부수고 이동하기(Gold 4) 문제 전체 문제 보기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 접근법 이번 문제는 출발 지점에서 목표지점까지의 최단거리를 구하는 문제이다. 최단 거리 문제는 DFS보다는 BFS로 풀어야 하는 문제이다. 그리고 이 문제는 벽을 한번 부수고 지나갈 수 있다는 점에서 조금 더 까다로운 문제가 된다. visited 전역 배열을 보통 2차원 배열로 많이 사용하는데 이 문제에서는 기존의 2차원 배열에 벽을 한번 부수었을 때 방문하는 경우와 벽을 한 번도 ..
Algorithms/DFS & BFS 2021. 8. 23. 16:35

[BOJ 1697] (DFS/BFS)숨바꼭질 (C++)

숨바꼭질 (Silver 1) 문제 전체 문제 보기 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 접근법 문제에서 수빈이와 동생의 위치는 1차원 수평선 위의 좌표로 주어진다. 그리고 수빈이의 위치가 x 일 때 다음으로 수빈이가 이동할 수 있는 위치는 x+1, x-1, x*2 이다. 이동할 수 있는 위치를 인접 노드라고 본다면 BFS로 풀이 가능한 문제이다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간도 BFS 탐색을 통해서 최단거리 찾는 방법과 동일하다. 자료구조 선택 본 문제를 ..
Algorithms/DFS & BFS 2021. 8. 20. 11:21

[BOJ 7576] (DFS/BFS) 토마토 (C++) - (최적화)

토마토(Silver 1) 문제 전체 문제 보기 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 접근법 이 문제는 7569번 토마토 문제와 동일하다. 7569번 토마토 문제는 3차원 공간에서 BFS로 풀이하는 문제이고 이번 문제는 오히려 조금 더 쉬운 2차원 공간에서 BFS로 풀이하는 문제이다. 그래서 접근법에 대한 설명은 7569번 토마토 풀이글을 참고하자 최적화 7569번 토마토 문제 풀고 조금 더 쉬운 이번 문제를 다시 풀게되어 이번에는 조금 더 시간을 줄일 수 있도록 최적화 부분에 조금 ..
Algorithms/DFS & BFS 2021. 8. 19. 12:08

[BOJ 2178] (DFS/BFS) 미로 탐색 (C++)

미로 탐색 (Silver 1) 문제 전체 문제 보기 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근법 이 문제에서 구해야 하는 값은 미로를 탈출하기 위해 필요한 최단경로의 길이이다. 최단 경로의 길이를 구하기 위해서는 DFS보다 BFS를 활용해야 한다. 너비 우선으로 탐색하는 BFS에서 탐색 깊이는 항상 최단거리를 보장하기 때문이다. 하지만 DFS는 최단 경로를 보장하기보단 하나의 경로를 끝까지 탐색하기 때문에 최단경로를 두고 다른 경로로 탐색을 완료할 위험이 있다. 아래와 같은 상황을 살펴보자. 이 미로에서는 위에 초록색 경로가 최단..
Algorithms/DFS & BFS 2021. 8. 18. 14:06