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) 그래프를 다시 공부하면서 풀었던 문제 (..

https://www.acmicpc.net/problem/2548 2548번: 대표 자연수 첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다. www.acmicpc.net 문제 요약 주어진 자연수에 대해 그 차이를 계산하여 차이의 전체 합을 최소로 하는 자연수 = 대표 자연수를 구하라 (대표 자연수가 두 개 이상이면 가장 작은 것 출력) 범위 N은 1 이상 20,000 이하 입력되는 자연수는 1 이상 10,000 이하 자연수 k의 범위를 정하고 완전 탐색으로 돌면서 각 원소들과의 차이를 더해 최소 값을 구하면 된다. k의 범위는 1부터(0은 자연수가 아님) 입력된 원소의..

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 문제 요약 문자열 X, Y의 차이는 X[i] != Y[i]인 i의 개수 A는 B의 길이보다 작거나 같고, A의 길이와 B의 길이가 동일해질 때까지 A 앞에 알파벳 추가 혹은 A 뒤에 알파벳 추가한다. A 길이 == B 길이 이면서 A와 B 차이를 최소화한 값을 구하라. 범위 A와 B의 최대 길이 50 앞뒤로 원하는 알파벳을 채울 수 있기 때문에 B와 동일한 ..