Study hard

www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net [풀이] bfs를 사용하여 풀었다. 말처럼 이동한 횟수가 K번 미만이면 말처럼 이동한 칸을 queue에 넣는다. 그리고 원숭이로 이동하는 경우 또한 queue에 넣어야한다. #include #include using namespace std; struct Monkey { int x, y; int horse;//말 방식으로 이동한 횟수 int dist;//해당 칸까지 이동한 횟수 }; int K,..

www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net [풀이] bfs를 사용하여 풀었다. 각 벽마다 주변에 있는 0의 개수를 세도록 하면 visited[1001][1001]배열을 매번 false로 초기화 해줘야 하기 때문에 시간 초과가 난다. ※방문하지 않은 0마다 bfs를 호출하여 연결된 0의 개수를 센 다음, 탐색하면서 만난 벽들에 그 개수를 더해주도록 하였다. #include #include #include //scanf #include..

www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 문제에 주어진 규칙으로 연산을 진행하는 문제였다. - C연산을 R연산과 같은 방식으로 해주기 위해 배열의 행과 열을 반전시키는 setAcopy함수와 resetAcopy함수를 구현했다. - number_cnt[]에 행에 같은 숫자가 몇 번 나오는지 저장하고, 1번 이상 나온 숫자는 벡터에 나온 횟수와 함께 저장한다. - 나온 횟수를 기준으로 벡터를 정렬하고 배열 A에 정렬된 순서대로 값과 나..

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net [풀이] bfs 최단거리를 구하는 문제였다. 1. 아기 상어의 크기보다 작은 물고기를 벡터에 저장 2. 먹을 수 있는 물고기 없으면 종료 3. 1마리면 그 자리까지 갈 수 있는지 확인 후 갈 수 있으면 먹는다. 갈 수 없으면 종료. (Time += 물고기 먹으러 간 거리) 4. 2마리 이상이면 그 자리까지 갈 수 있는지와 어느 물고기가 가장 가까운지 비교해가며 거리를 구한다. 어떤 물고기로도 갈 수 ..

www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net [풀이] dfs 조합으로 활성화시킬 바이러스 M개를 뽑고, 그에 따라 bfs를 이용하여 확산시켜야 하는 문제였다. bfs level(깊이)갱신을 잘못 이해해서 애먹었다. 각 칸마다 점수가 있는게 아니므로 처음방문 했을 때 시간이 최단 시간임을 명심하자! 한 번 방문했으면 다시 방문하지 않아도 됨!! 빈칸을 미리 세어두고 바이러스를 확산시켰을 때 방문하는 빈칸들의 개수와 비교하여 같으면 최솟값을 갱신하였다. 각 경우마다 ..

www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [풀이] dfs 조합으로 모든 경우의 수를 탐색하는 문제였다. 매 경우의 수마다 스타트 팀과 링크 팀의 능력치 차를 계산하여 최소값을 갱신한다. #include #include //min #include //abs using namespace std; int N; int S[21][21]; bool Select[21];//스타트 팀에 속한 사람 int totalS = 0; int Min = 987654321; void getDiff..