📗 CS

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net Solution 현재 상태에 대한 정보를 추가적으로 저장한다는 점에서 이전 포스팅에서 다룬 문제와 정확히 같은 유형의 문제입니다. 이전 포스팅과 매우 유사한 문제이기 때문에 소스코드를 짧게 설명하고 끝내도록 하겠습니다. 소스 코드 #include #include #include #include #include #define FASTio ios_base :: sy..

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의 친구수의 최..