문제 출처 : https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제 설명 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼..
그래프 탐색 그래프 탐색은 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선을 타고 이동할 수 있는 모든 정점을 한 번씩 탐색하는 것을 의미합니다. 그래프 탐색 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)이 있습니다. 시간 복잡도 : 인접 행렬(O(V^2)), 인접 리스트(O(V+E)) V : 접점, E : 간선 DFS DFS는 시작점에서 시작하여 해당 분기를 모두 탐색 후 다음 분기로 넘어가는 탐색 방법입니다. 모든 경로를 탐색할 때 DFS를 사용한다. 검색 속도는 BFS에 비해 느리다. 메모리 효율은 인접리스트가 인접 행렬에 비해 좋지만 속도는 인접 행렬이 빠르다. 스택 또는 재귀를 이용하여 구현한다. BFS BFS는 시작점에서 가까운 점들을 우선적으로 탐색하는 방법입니다. 두 노드..
문제 출처 : https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제 설명 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다...
