반응형 BFS32 백준 1726번 로봇 - C++ 풀이 1. 로봇의 상태를 나타내기 위해서는 {행, 열, 방향} 세 가지 값이 필요하다. 2. 출발 상태 노드에서 도착 상태 노드까지 가는 최단 거리를 BFS를 사용하여 구한다. 1. 로봇의 상태를 나타내기 위해서는 {행, 열, 방향} 세 가지 값이 필요하다. 로봇의 상태를 나타내기 위해서는 {행, 열, 방향} 이 세 가지 값이 필요하다. 이것을 세 정보를 가지고 상태 노드를 구성할 수 있다. 2. 출발 상태 노드에서 도착 상태 노드까지 가는 최단 거리를 BFS를 사용하여 구한다. go k, turn left/right 연산을 통해 도달할 수 있는 상태 노드를 간선으로 이어 인접 노드로 만든다. 완성된 그래프에서 출발 상태에서 도착 상태로 가는 최단 거리를 구해준다. 모든 간선의 가중치가 1이므로 BFS를 사용.. 2022. 9. 23. 백준 2583번 영역 구하기 - C++ 풀이 1. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 잇는다. 2. 완성된 그래프에서 각 연결 요소의 크기와 연결 요소의 개수를 센다. 1. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 잇는다. 유의미한 칸은 직사각형이 없는 칸이다. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 이어 그래프로 만들어준다. 2. 완성된 그래프에서 각 연결 요소의 크기와 연결 요소의 개수를 센다. 이제 각 영역은 연결 요소와 같다. DFS/BFS로 연결 요소의 개수를 세는 동시에 각 연결 요소의 크기도 구해준다. 연결 요소의 개수는 총 DFS/BFS의 호출 횟수이고, 각 연결 요소의 크기는 한 DFS/BFS에서 방문한 노드의 개수와 .. 2022. 9. 19. 백준 14867번 물통 - C++ 풀이 1. 항상 두 물통 중 한 물통은 꽉 차있거나 비어있다. 2. BFS를 사용해서 {0, 0}에서 {C, D}로 가는 최단 거리를 구한다. 1. 항상 두 물통 중 한 물통은 꽉 차있거나 비어있다. 주어진 연산을 사용하면 항상 두 물통 중 한 물통은 꽉 차있거나 비어있어야 한다. 따라서 상태를 나타낼 때, 아래와 같은 3가지 정보만 있으면 된다. 한 물통에 들어있는 양 x 그 물통이 A물통인지 B물통인지 여부 반대 물통이 비어있는지 꽉 차있는지 여부 두 물병에 들어있는 물의 양 정보 대신 위의 정보를 사용하여 상태를 나타내면 상태 개수를 N^2개에서 4N개로 줄일 수 있다. 2. BFS를 사용해서 {0, 0}에서 {C, D}로 가는 최단 거리를 구한다. 위의 사실을 이용해서 상태 노드를 나타내고 BFS를 사.. 2022. 9. 1. 백준 1963번 소수 경로 - C++ 풀이 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 네 자리 수가 소수인지 아닌지 판별할 일이 잦으므로 미리 4자리 소수를 모두 구해두어 O(1)에 소수 판별을 할 수 있도록 하자. N 미만의 소수는 에라토스테네스의 체를 사용하면 O(NloglogN)에 구할 수 있다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 각 소수를 그래프의 노드라고 생각하면, BFS를 통해 두 소수(노드) 사이의 최단 거리를 구할 수 있다. #include #include using namespace std; const int INF = 987654.. 2022. 8. 20. 백준 17142번 연구소 3 - C++ 풀이 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 바이러스를 놓을 수 있는 위치가 최대 10군데이고, M이 최대 10이므로 최악의 경우에도 10C5가지 경우 밖에 발생하지 않는다. 또한 각 경우를 시뮬레이션하는 데는 O(N^2)의 시간 복잡도가 들기 때문에 브루트 포스를 사용해도 충분하다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 바이러스가 퍼지는 시뮬레이션은 BFS를 사용하면 쉽게 구현할 수 있다. #include #include #include using namespace std; typedef pair pii; const int EMP.. 2022. 8. 19. 이전 1 2 3 4 5 ··· 7 다음 반응형
