728x90 SMALL 백준 BFS4 [백준] 14502번 : 연구소 (파이썬) BFS + 백트래킹 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 0 - 빈 칸 1 - 벽 2 - 바이러스 처음에 생각한 방식 이것도 처음에 패턴 찾아서 쌩자 구현하려 했는데, 불가능이다. 그 이유는 바이러스(2)가 벽(1)을 만날때까지 상하좌우로 이동하며 벽(0)을 바이러스(2)로 감염시키기 때문이다. 즉, 패턴을 찾을 수 없다. 접근 방식 바이러스들(2)의 위치에서 동시에 퍼져야 하므로 BFS 벽을 무조건 3개 세워야 하는데, 바이러스가 최대한 .. 2024. 2. 15. [백준] 2206번 : 벽 부수고 이동하기 (파이썬) BFS 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net (1) 처음에 생각한 방식 - V1 (실패) # 벽 부수고 이동하기 (골드 3) / BFS import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(n)] visited = [[False] * m for _ in r.. 2024. 2. 10. [백준] 16236번 : 아기 상어 (파이썬) BFS 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 조건 처음에 아기 상어의 크기는 2, 아기 상어는 상하좌우로 인접한 한 칸씩 이동 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지날 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 더 이상 먹을 수 있는 물고기가 공간에 .. 2024. 1. 29. [백준] 7576번 : 토마토 (파이썬) BFS 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net (1) 메모리 초과난 코드 (실패) import sys from collections import deque c, r = map(int, sys.stdin.readline().split()) graph = [] visited = [[False] * c for _ in range(r)] start = deque() for i in range(r): l = list(map.. 2024. 1. 17. 이전 1 다음 320x100 LIST
