BOJ/BFS
-
[Python 3] 백준 14502-연구소BOJ/BFS 2020. 2. 10. 23:55
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 벽을 세우는 경우의 수는 4만 가지를 넘지 않는다. 따라서 모든 경우에 대해 다 계산해 봐도 OK. 따라서, 벽 3개를 세운 이후, 바이러..
-
[Python 3] 백준 11403-경로 찾기BOJ/BFS 2020. 2. 10. 23:47
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 우선적으로, 방문했음을 체크하는 2차원 배열 하나를 만든다. 그 이후, 모든 노드로부터 BFS를 실행하면서, 노드 하나를 방문할 때마다 배열에서 그 노드의 위치를 의미하는 위치의 값을 1로 수정한다. 모든 노드에 대해 BFS를 실행하면 결국 모든 노드를 다 방문하게 된다. (deque 쓰면 속도 절감이 가능하다) import sys from collections import deque INF=10**9 N=int(sys.stdin.read..