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 기존 벽 부수고 이동하기 문제에선 오직 한 번만 벽을 부술 수 있었지만 2번 문제에선 총 10번까지 벽을 부술 수 있다. 따라서 기존 vis[MAX][MAX][2] 였던 배열을 vis[MAX][MAX][11]로 바꿔서 BFS 할 때 조금만 수정해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2..

www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 처음 문제를 봤을 때 맵의 크기가 1500*1500 이길래 BFS두 개를 배열 초기화를 해가면서 사용해도 1초 안에 돌아갈까? 생각해서 구현해봤지만 TLE가 났다. 정 모르겠어서 찾아봤는데 물에 대해서 큐에 집어 넣어주고, nextQ에 넣어준 뒤에 Q = nextQ 를 통해서 복사가 가능했다..! 그리고 백조에 대해서 BFS를 해줘야 하는데 중간에 다른 백조가 있다면 BFS의 반환 값을 참으로 반환해준..

begin에서 target이 될 때까지 DFS탐색을 하면서 총 몇 번에 변환이 완료되는지 구하면 된다. 단어는 오직 한 글자씩만 변할 수 있으니 반복문을 통해서 각각 단어들을 비교해주고 차이가 1이라면 DFS를 재귀 호출해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include using namespace std; bool vis[51]; int ans = 100000; void DFS(string cur, string target, vector ar, int cnt, int n, int sum) { if (cur == target) { an..

www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 버블 소트를 하면서 스왑하는 개수가 총 몇 번 나오는지 확인하면 되는데 N이 50만이라 버블 소트를 사용해서 해결하면 TLE가 난다. \(O(NlogN)\)으로 해결해야 하는데 퀵 소트나 머지 소트를 사용해서 약간 응용시켜주면 된다. 우선 기존 병합 정렬에서 원소를 각 하나씩 남을 때까지 쪼개주고, 1 2 3 4 5 6 7 void mergeSort(int* ar, int s, int e) { if (s

www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상 정렬 + DP 문제였다. 1번 노드에서 걸리는 작업을 모두 완료하고 2번과 3번 노드에서 작업을 시작할 수 있다. 2번 노드에서 걸리는 시간은 1초이지만, 3번 노드에서 걸리는 시간이 100 초기 때문에 4번 노드에서 작업을 시작하려면 1번 10초 + 3번 100초 가 걸리고 4번노드까지 마치면 120초가 정답이 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ..

www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 탐색 + 구현 문제였다. 고슴도치는 물이 들어올 곳에 갈 수 없다는 말에 처음에는 bfs 한 번에서 고슴도치와 물을 전부 pop 해가면서 했는데 그러한 접근은 while문이 한번 돌 때마다 하나씩 pop 되기 때문에 실패했다. 다시 생각해봤는데 물의 위치에서 BFS한 것과 고슴도치 위치에서 BFS 한 것을 통해서 고슴도치가 갈 위치 + 1 < 물이 들어올 위치값 을 만족한다면 고슴도치가 갈 수 있겠다는 생각이 들어서..