https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 루트 없는 트리. 트리의 루트가 1일 때, 각 노드의 부모를 구하라 범위 노드의 개수 N (2 ≤ N ≤ 100,000) 모든 정점을 탐색해서 모든 노드의 부모 노드를 찾으면 되므로 이는 DFS 혹은 BFS 중 하나를 선택해서 코드를 구현하면 된다. BFS BFS는 한 노드에서부터 시작해서 방문한 노드를 큐에 넣으면서 진행한다. 큐에 들어간 노드의 인접 노드를 반복문을 통해 방문하게 되는데, 이때 x는 현재 방문 노드, y는 인접 노드를 의미하므로 ..

https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 문제 요약 . 빈 필드 / # 울타리 / o 양 / v 늑대 한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면 두 칸은 같은 영역 안에 속해있다고 한다. 마당에서 탈출할 수 있는 칸(마당 밖으로 나갈 수 있는 칸)은 어떤 영역에도 속하지 않는다. IF 영역 안의 양의 수 > 늑대의 수 → 늑대를 내쫓는다. ELSE 늑대가 모든 양을 먹는다. 아침..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 요약 가로, 세로, 대각선으로 연결된 사각형 = 섬 섬의 개수를 세는 프로그램을 작성해라. 범위 지도의 너비 w와 높이 h (50보다 작거나 같은 양의 정수) 상하좌우, 대각선까지 포함해야 하므로 방향을 담은 배열dir을 확장시켰다. 배열의 x, y 좌표를 나타내는 것이 반대이므로 처음에 입력받을 때부터 반대로 입력해서 헷갈리지 않도록 해줬다. #include using namespac..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 요약 방향없는 그래프, 연결 요소의 개수를 구하는 프로그램 → 연결 요소란? 연결 그룹의 개수 범위 정점의 개수 N (1 ≤ N ≤ 1,000) 간선의 개수 M (0 ≤ M ≤ N×(N-1)/2) 간선의 양 끝점 u, v (1 ≤ u, v ≤ N, u ≠ v) DFS 를 이용해서 연결된 노드들을 방문했고, 방문한 적도 없고 연결되..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 요약 지렁이는 인접한 다른 배추로 이동할 수 있다. (한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접한 것) 배추가 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리가 필요한지 알 수 있다. 범위 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50), 세로길이 N(1 ≤ N ≤ 50) 배추가 심어져 있는 위치의..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 요약 연결된 집 = 단지. 단지의 번호를 붙이자. 1: 집이 있음 0: 집이 없음 범위 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25) 시작 집을 찾기 위해 반복문을 통해 방문하지 않은 집(1)을 찾고 찾았다면 dfs를 통해 연결된 집들을 탐색(방문)한다. 연결된 집들을 모두 방문하고 만약 방문하지 않은 집이 없다면 dfs 함수가 끝난다. 다른 단지를 보러가기 위해 반..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 요약 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하라. 범위 컴퓨터의 수 100 이하 어떤 그래프 탐색을 선택해야 더 효율적인 방법인지 생각해봤다. DFS는 깊이 우선 탐색으로 원하는 값을 찾을 때까지 깊게 들어간다. 현 경로상의 데이터만 기억하면 되므로 저장 공간을 적게 사용한다. 얻은 해가 최단 경로를 보장하지 않는다. (→ 최단 경로를 찾는 방법은 BFS에 더 적절하다)..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 요약 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램 작성하기 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문하고 더이상 방문할 수 있는 점이 없으면 종료한다. 정점 번호는 1~N 범위 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000) 그래프를 다시 공부하면서 풀었던 문제 (..