문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 방법 항상 낮은 칸으로 이동하며 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 갈 수 있는 경로의 개수를 구하는 문제다. 처음엔 단순한 탐색문제인 줄 알고 모든 케이스를 다 탐색해서 개수를 구하려고 했다. 하지만 최악의 경우를 생각해본다면 한 정점에서 4방향으로 모든 정점을 계속해서 탐색할 수도 있기 때문에 다른 방법이 필요하다. 좀 더 생각해보면, 어떤 점(y, x)에서 제일 오른쪽..
그래프 탐색
문제 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 풀이 방법 사이클이 없는 무방향 그래프에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당겼을 때, 가장 길게 늘어나는 경우가 있을 것이다. 이때 트리의 모든 노드들은 이 두 노드를 끝점으로 하는 원 안에 들어가게 되는데, 이런 두 노드 사이의 경로를 트리의 지름이라고 한다. (정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이) 이러한 트리의 지름을 구하는..
