문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 방법 백준 17141 연구소 2와 비슷한 문제다. (풀이) 차이점은 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다는 것이다. 따라서 탐색할 때 비활성 바이러스를 만나면 퍼뜨린 시간을 계산하지 않아도 된다는 것만 주의하면 된다. 코드 #include #include #include #include using namespace std; int dy[] = {-..
프로그래밍
문제 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 풀이 방법 주어진 연구소 정사각형의 '2'의 위치에 바이러스를 M개 놓아본 후, 그것을 퍼뜨렸을 때 모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제다. 바이러스를 퍼뜨리는 것이나 최소 시간을 구하는 건 다른 문제에서도 많이 해봤기 때문에 어려움은 없을 것이다. (만약에 어렵다면 미로 탐색이나 불 등 다른 문제를 더 풀어보자.) 하지만 전체 바이러스 개수 중 M개를 선택해 놓는 것이 좀 어렵다..
문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 방법 사이클이 없는 무방향 그래프에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당겼을 때, 가장 길게 늘어나는 경우가 있을 것이다. 이때 트리의 모든 노드들은 이 두 노드를 끝점으로 하는 원 안에 들어가게 되는데, 이런 두 노드 사이의 경로를 트리의 지름이라고 한다. (정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이) 이러한 트리의 지름을 구하는..
문제 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 방법 예전에 유명했던 테트리스 비슷한 게임인 뿌요뿌요 관련된 문제이다. 뿌요뿌요는 같은 색깔이 4개 이상 연결되어 있으면 터지며, 터진 후에 위에 있던 뿌요들이 아래로 내려오면서 연결되면 또 터진다. 이를 연쇄라고 한다. 필드의 정보가 주어졌을때 연쇄가 얼마나 일어나는지 계산하는 문제이다. 4개 이상 연결되어 있는 뿌요를 찾는다. 터뜨린다. (빈 칸으로 만든다)..
