본문 바로가기

알고리즘74

[BFS] 백준 2206번 : 벽 부수고 이동하기 - 파이썬 Python https://www.acmicpc.net/problem/2206 생각하기 미로 찾기와 비슷한 게임이라고 판단하여 BFS를 사용하여 마지막 정점까지 가는 최소를 구하기로 생각했다 미로 찾기 문제와 달리 까다로운 해결해야할 조건 하나는 "벽을 한개 깰 수 있다는 점" 각 정점에서 다른 정점으로 이동하는 경우는 다음과 같다 빈칸 -> 빈칸 : 벽 깨기 유무와 상관 없이 모두 이동 가능 빈칸 -> 벽 : 벽 깨지 않은 경우 만 이동 가능 / 벽을 깬 경우 이동 불가 벽 -> 벽 : 이동 불가 벽 -> 빈칸 : 벽 깨기 유무와 상관 없이 모두 이동 가능 백준 강의에서 정점이란 정점은 앞에 어떤 상황이건 간선에 대하여 항상 같은 일을 해야 함 이 정의가 지켜져야 정점이라는 것이 성립한다 따라서 큐에 넣어주는 정점.. 2021. 11. 21.
[BFS] 백준 12886번 : 돌 그룹 - 파이썬 Python (보충예정) 생각하기 돌 그룹이 모두 같은 개수가 있는지를 찾는 문제이기 때문에 DFS 와 BFS 중 고민했다. 최소를 구하는 문제는 아니지만 그룹의 개수가 같아지면 바로 프로그램을 종료하면 된다고 생각했다 만약 DFS를 사용한다면 그게 그룹의 개수가 절대 같아지지 않는 경로를 탄다면 굉장히 오버헤드가 커질 것이라 생각했다 BFS로 A, B, C 조합의 주변부터 검사를 했을 때, 그룹의 개수가 같아지는 상황이 걸리면 바로 종료하기로 했다 구현하기 큐를 만들어서 해당 조합이 같지 않고 개수가 달라서 로직이 실행되고 검사시, 문제가 없다면 큐에 넣어주어서 BFS를 구현한다 visited 배열 만약 조합이 이전에 했던 조합이 또 나오면 결국 그 안에서 반복되어 무한루프가 생기기 때문에 visited 여부를 체크해가며 BF.. 2021. 11. 18.
[BFS] 백준 14502번 : 연구소 - 파이썬 Python 생각하기 처음에는 어떻게 벽 3개를 놓으면 하면 바이러스의(2번의) 확산을 적게할 수 있을까에 대해서 생각했다 하지만 고려해야할 변수가 너무 많았다. 벽이 놓였을 때, 어떤 기준으로 해당 자리에 있을 때, 확산이 최소가 되는지 벽이 한개도 아니다 세개인데 한개가 맞으면 다른 두개는 어떻게 판단할건지 코드가 복잡해지면 다시 생각하자.. 다시 생각하는게 좋았다 만약 벽 3개를 N x M 개의 좌표의 각 칸을 대상으로 3개를 뽑는 조합을 구성한다면 M이 최대가 8이므로 64 x 63 x 62가 되겠다 해당 조합을 기준으로 각각의 바이러스들을 BFS로 하여서 모든 조합 벽배치 조합을 검사하는 방식으로 진행을 하여도 64 x 63 x 62 x 64 < 1억 이므로 충분히 시간안에 해결이 가능하다 구현하기 iter.. 2021. 11. 17.
[BFS] 백준 16928번 : 뱀과 사다리 게임 - 파이썬 Python 생각하기 최소의 횟수로 주사위를 던지기 위해서는 BFS 알고리즘이 딱이었다. 가장 근처에 있는 아이들을 먼저 검사하면서 100에 딱 갔을때 바로 종료시켜버리면 그 때가 최소 주사위 던진 횟수일 것이다 잠시 BFS에 대해 정리하기 큐를 이용하여 한 정점에서 시작해서 모든 정점을 방문하는 알고리즘 단계별로 주변 노드들을 넣어가며 진행하기 때문에 최단거리 알고리즘에 적합 어떤 문제가 그래프로 변환이 가능하고 모든 가중치가 1인 경우에는 BFS로 간주 큐에 넣을 때 해당 노드 방문 표시하는 것이 중요!! 시작 정점 큐에 넣어주기 큐에 요소가 존재하는 한 무한반복하는 while문 안에서 큐의 요소를 하나 뺀다 큐에 연결된 요소들중 방문하지 않은 항목들을 다시 큐에 넣음 구현하기 뱀과 사다리가 규칙상으로는 다르지만.. 2021. 11. 13.

티스토리툴바