본문 바로가기

알고리즘/BFS13

[BFS] 백준 1600번 : 말이 되고픈 원숭이 - 파이썬 Python https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 생각하기 처음에는 말의 움직임과 원숭이 본래 움직임을 통합하여 BFS로 풀고자 하였다. 하지만 간과한 사안이 있었다. 말의 움직임과 원숭이 본래 움직임이 전혀 다른 패턴이기 때문에 원숭이의 본래 움직임으로 방문한 칸을 나중에 말의 움직임으로 더 짧은 시간에 방문할 수 있다는 점이었다. 만약 움직임의 패턴이 다른 경우, 칸까지 움직인 최소 거리를 하나의 visited 배열에 넣는 방.. 2022. 3. 10.
[BFS] 백준 2234 : 성곽 - 파이썬 Python https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 생각하기 각 칸의 테두리를 기준으로 구역을 나누는 것이므로 각 칸을 돌면서 해당 칸이 구역에 속하는지, 속하지 않는지를 판단하면 되는 방법이라고 생각했다 BFS를 사용하여 칸들을 돌아보기로 했다 세가지 문제에 대한 답을 풀어야 하는데 1. 성에 있는 방의 개수 각 칸에 대한 BFS를 돌면서 더이상 갈 곳이 없으면 방의 개수를 증가시킨다 2. 가장 넓은 방의 넓이 1번의 방법을 수행하면서 BF.. 2022. 2. 23.
[BFS] 백준 17141 : 연구소2 - 파이썬 Python https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 생각하기 연구소 전체를 점령할 수 있는 최소시간을 구하는 문제이므로 BFS를 통해 점령하다가 점령이 완료되면 그 때의 time을 min_time과 비교하면 되는 문제로 생각했다 바이러스를 놓을 수 있는 후보 여러 개중에서 M개를 선택하여 바이러스를 놓는다 -> 조합을 사용 처음에 모든 빈칸 + 바이러스 놓을 수 있는 후보지를 counting한 후 BFS 큐를 돌면서 counting을 차감해주는 방식으로 점.. 2022. 2. 17.
[BFS] 백준 5014번 : 스타트링크 - 파이썬 Python https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 생각하기 버튼을 누르는 최소 횟수를 구하는 것이기 때문에 전형적인 BFS 문제라고 생각하였다 시간 복잡도 S, G, F가 모두 1000000 이하의 수이므로 충분히 BFS로 풀어도 시간 안에 들어올 수 있는 문제 구현하기 q = deque() (현재 강호가 있는 층, 현재까지 누른 버튼의 횟수) 를 q에 append / popleft 한다 올라가는 버튼 현재 강호가 있는 층 + U 가 건물을 넘지 않아야 함 .. 2022. 2. 7.

티스토리툴바