문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 방법 1초동안 미세먼지 확산, 공기청정기 작동이 일어나며 T초 후 미세먼지의 양을 구하는 구현, 시뮬레이션 문제다. 주의할 점은 미세먼지가 확산 될 때는 그 시간의 미세먼지 양에 대해서만 처리를 해야한다. 다시말해, 확산될 때 제 자리와 확산된 방향의 A(r,c)이 변하게 되는데, 변한 값으로 확산을 처리하면 안된다. 문제에서 확산의 예시 세번째를 보면 이해가 될 것이다. 아래 코드에..
프로그래밍/Algorithm
문제 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 풀이 방법 사이클이 없는 무방향 그래프에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당겼을 때, 가장 길게 늘어나는 경우가 있을 것이다. 이때 트리의 모든 노드들은 이 두 노드를 끝점으로 하는 원 안에 들어가게 되는데, 이런 두 노드 사이의 경로를 트리의 지름이라고 한다. (정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이) 이러한 트리의 지름을 구하는..
