BFS2 [BOJ 5247] 불 https://www.acmicpc.net/problem/5427 5427번: 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩 www.acmicpc.net 위 문제는 여러 테스트 케이스가 주어지고, 맵의 크기도 1000이 되기 때문에 상근이가 이동할 때마다 불을 옮기면 시간초과가 날 수 있다. 그.. 2020. 4. 8. [BOJ 2606] 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. www.acmicpc.net 위 문제는 간단하게 BFS로 풀 수 있다. 1번 컴퓨터에서 갈 수 있는 모든 컴퓨터를 구하면, 몇 개의 컴퓨터가 바이러스에 걸리는지 알 수 있다. 이를 위해서 큐에 1번을 넣음 큐에서 값을 하나 꺼냄 꺼낸 값과 연결된 모든 값 중 방문하지 않은 곳을 큐에 넣음 큐에 넣을 때마다 바이러스가 걸린 컴.. 2020. 4. 7. 이전 1 다음