본문 바로가기
반응형

BFS32

백준 4991번 로봇청소기 - C++ 풀이 1. 총 이동 횟수가 최소가 되는 순서로 더러운 칸들을 방문해야 한다. 2. A칸에서 B칸으로 가기 위한 최소 이동 횟수는 BFS로 구한다. 1. 총 이동 횟수가 최소가 되는 순서로 더러운 칸들을 방문해야 한다. 더러운 칸이 최대 10개이므로, 더러운 칸을 방문하는 순서를 정하는 경우의 수는 10! 이 중 총 이동 횟수가 최소가 되는 경우를 찾으면 된다. N이 작기 때문에 DFS를 이용한 브루트 포스로도 시간 내에 통과가 가능한데, 아래 코드에서는 DP를 사용하였다. 2. A칸에서 B칸으로 가기 위한 최소 이동 횟수는 BFS로 구한다. 중간에 장애물이 있을 수 있으므로 A칸에서 B칸으로 가기 위한 최소 이동 횟수는 BFS를 이용해서 구해야 한다. #include #include #include #incl.. 2022. 7. 14.
백준 1600번 말이 되고픈 원숭이 - C++ 풀이 1. 원숭이의 위치 {r, c}와 말처럼 이동한 횟수 k로 원숭이의 상태를 나타낼 수 있다. 2. 원숭이의 상태를 그래프의 노드로 생각하고, 한 번의 이동으로 도달 가능한 상태를 모두 간선으로 잇는다. 3. 출발 상태 노드에서 도착 상태 노드로 가는 최단 거리를 BFS를 사용하여 구한다. 1. 원숭이의 위치 {r, c}와 말처럼 이동한 횟수 k로 원숭이의 상태를 나타낼 수 있다. 원숭이의 상태를 나타내기 위해서 필요한 값은, 원숭이의 위치와 현재 위치까지 오면서 말(knight)처럼 이동한 횟수 k이다. 2. 원숭이의 상태를 그래프의 노드로 생각하고, 한 번의 이동으로 도달 가능한 상태를 모두 간선으로 잇는다. 원숭이의 {r, c, k} 값을 가지고 원숭이 상태 노드를 나타낸다. 그리고 한 번의 이동으로.. 2022. 7. 13.
백준 2933번 미네랄 - C++ 풀이 1. 바닥에서 시작하는 DFS/BFS로 떠있는 미네랄인지 체크할 수 있다. 2. 떠있는 미네랄들에 대해서 아랫부분이 어딘가에 닿을 때까지 떨어뜨린다. 1. 바닥에서 시작하는 DFS/BFS로 떠있는 미네랄인지 체크할 수 있다. 인접한 미네랄은 하나의 클러스터이므로, 바닥에서 DFS/BFS를 시작하여 방문하지 못한 미네랄은 떠있는 미네랄로 판단하면 된다. 2. 떠있는 미네랄들에 대해서 아랫부분이 어딘가에 닿을 때까지 떨어뜨린다. 1에서 검증한 떠있는 미네랄들에 대해서 각각 아랫부분이 어딘가에 닿으려면 몇 칸이나 떨어져야 하는지 구한다. 떠있는 클러스터는 그중 가장 작은 값만큼 떨어지게 될 것이다. #include #include using namespace std; const int LEFT = 0, RIG.. 2022. 7. 8.
백준 1938번 통나무 옮기기 - C++ 풀이 1. 통나무의 위치와 방향 값으로 평지의 상태를 나타낼 수 있다. 2. 평지의 상태를 그래프의 노드로 생각하고, 한 번의 연산으로 도달 가능한 상태들을 모두 간선으로 잇는다. 3. 초기 상태 노드에서 도착 상태 노드로 가는 최단거리를 BFS를 사용하여 구한다. 1. 통나무의 위치와 방향 값으로 평지의 상태를 나타낼 수 있다. 평지에서 움직이는 것은 통나무뿐이다. 따라서 평지의 상태를 나타내기 위해 필요한 값은 통나무의 위치와 놓인 방향뿐이다. 2. 평지의 상태를 그래프의 노드로 생각하고, 한번의 연산으로 도달 가능한 상태들을 모두 간선으로 잇는다. 통나무의 위치와 방향을 가지고 평지의 상태를 나타낸다. 그리고 하나의 상태를 그래프 상의 하나의 노드로 생각해준다. 그리고 한 번의 연산으로 도달 가능한 상태.. 2022. 7. 6.
백준 16933번 벽 부수고 이동하기 3 - C++ 풀이 1. 어떤 상황을 나타내기 위해 필요한 값은 {행, 열, 벽 부순 횟수, 낮밤여부}이다. 2. BFS로 {1, 1, 0, 낮}인 상황 노드에서 {N, M, ?, ?}인 상황으로 가는 최단 거리를 구한다. 1. 어떤 상황을 나타내기 위해 필요한 값은 {행, 열, 벽 부순 횟수, 낮밤여부}이다. 어떤 상황을 나타내기 위해 필요한 값은 {행, 열, 벽 부순 횟수, 낮밤여부}이다. 2. BFS로 {1, 1, 0, 낮}인 상황 노드에서 {N, M, ?, ?}인 상황으로 가는 최단 거리를 구한다. BFS를 사용해서 시작 상황에서 종료 상황까지 가는 최단 거리를 구할 수 있다. 각 노드에서 인접 노드는 상, 하, 좌, 우로 이동하는 경우 + 해당 칸에서 가만히 머무는 경우 총 5가지가 된다. 이때 인접 노드가 벽이라.. 2022. 6. 16.
반응형

티스토리툴바