📗 CS/Algorithm

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net (0,0)에서 시작해서 (W-1,H-1)에 도달하기까지 상하좌우 무빙(횟수 제한 없음) , 그리고 말의 무빙 K번을 사용해서 최소한의 무빙횟수를 구하는 문제이다. 단, 1값으로는 이동할 수 없다. 일반적인 BFS와 크게 다르지 않다. 솔루션의 핵심은 3차원 bool 벡터를 사용해서 check[ y 좌표 ] [ x 좌표 ] [ 말의 움직임 사용 횟수 (=hcnt] 을 만들어 주었다는..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net Point 1. 옥상은 F층, 출발 층은 S층, S층에서 S+U층, S-D층으로 이동가능하다. 2. 이동할 때 마다 현재층 + 1을 저장해 준다. G층에 도달하면 BFS를 멈추면 된다. 소스코드 #include #include #include #include #include #define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(N..

https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 요점 1. 울타리는 #, 양은 k, 늑대는 v 2. 울타리 내부에 양의 수가 늑대의 수보다 많으면 늑대가 모두 잡아먹힌다. 3. 울타리 내부에 늑대의 수가 양의 수보다 많으면 양이 모두 잡아먹힌다. Solution 1. 영역별로 살펴보기 위해 배열값이 #이 아닌경우 bfs를 해서 양의 수와 늑대 수를 계산한다. 2. 영역 내부값만 BFS로 살펴보고, 내부값이 v면 wolf를 더해주고 ..

https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net 처음 문제를 읽고 문제가 이해가 안갔다. 문제를 쉽게 정리하자면, 1. 세 사람을 골라야 된다. 2. 세 사람은 서로 친구 관계여여함 ( 친구 관계는 입력을 통해 주어짐 ) 3. 세 사람이 친구관계이면서 각각의 사람이 가진 친구 수의 합의 최소값을 구해야 함. 예를들어, A, B, C가 서로 친구관계일때, A의 친구수 + B의 친구수 + C의 친구수의 최..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net Point 모든 치킨집(2)중에 n개를 고른 다음, 각각의 집과의 거리를 계산한다. 각각 집의 치킨 거리는 각 집과 치킨집과의 (x좌표차의 절댓값 + y좌표차의 절댓값)의 최솟값. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 도시의 치킨거리의 최솟값을 출력 Solution #include #include #include #include #define FASTio ios..