Study hard

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..

www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net [풀이] dfs 조합 구하는 방법을 이용하여 풀어야하는 문제였다. 먼저 사다리는 Ladder[11][11][31]로 표현하였다. Ladder[b][b+1][a] = true는 b번 세로선과 b+1번 세로선이 a번째줄의 가로선에 의해 연결되었다는 뜻이다. dfs로 추가할 가로선을 선정하고 0번 이상 추가했으면(3번 이하로) i번 세로선의 결과가 i번이 나오는지 확인하고 최솟값을 갱신한다. ※착각해서 조합을 구하..

www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net [풀이] dfs 중복순열을 구하는 방법을 이용하여 5번 이동시키는 모든 경우에 대해 얻을 수 있는 가장 큰 블록을 구하였다. #include #include using namespace std; int N; int Board[20][20]; int c_Board[20][20]; int Order[5]; const int dx[] = { -1,1,0,0 };//위,아래 const in..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [풀이] dfs를 사용하여 각각 방향마다 어떤 상태가 되는지 확인하는 방법으로 풀었다. dfs를 10번 호출했으면 return해주었다. 빨간 구슬을 먼저 움직여주고, 파란 구슬을 움직여서 파란 구슬이 구멍에 빠졌으면 return, 빨간 구슬만 구멍에 빠졌으면 최소값을 갱신해주었다. #include #include //min #include using namesp..