짱아의 개발 기록장

비교적? 간단한 bfs문제이다. 지뢰가 없는 곳을 방문하고 그와 인접한 8곳 중에서도 지뢰가 없다면 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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 // 1868. 파핑..

아이디어가 생각나지 않아 다른 분의 아이디어를 참고하여 유니온파인드로 구현했다. 핵심 아이디어는 3번 게이트로 들어오게 되면, 3->2를 가리키도록 union해주어야 한다. 따라서, 다시 한 번 3번 게이트로 다른 비행기가 들어오면 바로 3의 Parent인 2에 넣어줄 수 있게 된다. 만약 Parent값이 게이트 범위 안에 있지 않다면, 바로 공항은 폐쇄된다. 코드 첨부 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 34 35 36 37 38 39 40 41 42 43 // 공항 #include #include using namespace std; int g, p, n; vector airp..

각 정점마다의 최단 경로를 저장하기 위한 heap벡터(내림차순), 다익스트라 알고리즘 사용을 위한 pq벡터(오름차순)를 사용하여 전체적인 로직을 구현했다. 핵심은 heap벡터에 k개의 원소가 있지 않으면 계속 원소를 넣어주고 k개의 원소가 이미 차있는 상태라면, heap[i].top()과 cost값을 비교해주어 top의 값이 더 크다면 pop해주고 cost값을 새롭게 넣어주면 된다. 설명의 이해를 위해 간단히 필기해둔 것을 아래에 첨부했다. *이때, 빼먹기 쉬운 부분* 1->1로 가는 첫 번째 최단 경로는 무조건 0이다! 따라서, dijkstra()함수 초반에 heap[1].push(0);을 해주었다. 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..

모든 점을 연결하는 최소 비용을 구하는 문제이다. 따라서 MST알고리즘을 사용해야한다. 글쓴이는 그 중 kruskal 알고리즘을 사용하여 문제를 풀었다. 벡터에 {두 점을 연결하는 비용, {점1, 점2}}의 형태로 정보를 저장해주었다. 그리고 벡터를 비용순으로 sort한다. 모든 점을 하나씩 union하면서 최소 비용을 찾는다. 코드 첨부 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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 // 별자리 만들기(MST-..

bfs와 kruskal 알고리즘을 사용해야 하는 매우 괜찮은 문제이다. 총 3단계로 생각해볼 수 있다. 1) bfs로 이동할 수 있는 영역을 숫자로 check이차원 배열에 표시해두었다. 2) 그 후, 각 영역간에 필요한 사다리의 비용을 {사다리 비용, {영역1, 영역2}}의 형태로 vector에 저장했다. 3) MST를 구현하기 위해 kruskal을 사용하여 각 영역을 최소 비용으로 연결해주었다. MST로 구현해야 한다는 것을 쉽게 생각해내지 못해서 좀 헤맸던 것 같다. (어떻게 최소 비용으로 연결해주지..? 이 생각만 30분 넘게 했던 것 같...다....ㅎ) 코드 첨부 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..

약간 생각의 전환이 필요한 이분탐색 문제였다. mid값을 '돌사이의 최솟값'이라고 잠정적으로 잡아놓은 후에, mid값보다 (현재 돌 위치-이전 돌 위치)값이 더 작으면, 돌을 없애고 더 크면, 돌을 살려둔다. 그 후, 없앤 돌의 수가 n보다 작거나 같다면 mid(돌 사이의 최솟값)이 충분히 작다는 의미니 low = mid+1을 해주고 n보다 크다면 mid값이 너무 크다는 의미니 high = mid-1로 해준다. .....이런식으로 이분탐색을 진행하면 된다. 이 문제도 그림으로 설명하면 좋을 것 같아서 추후 첨부해보겠다. 코드 첨부 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 34 35 36..

오랜만에 이분탐색을 풀려고 하니까 머리가 돌아가지 않는다....ㅎ 하지만, 쉬운 이분탐색 문제여서 가볍게 풀 수 있었다. 첫 번째 숫자카드를 한 줄 받고 배열에 저장한다. 그리고 정렬한다. 두 번째 숫자카드를 한 개씩 첫 번째 숫자카드의 배열의 값과 이분탐색으로 대조한다. That's all..^^ 코드 첨부 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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 // 숫자 카드 #include #include using namespace std; int arr1[500001] = {0, }; int arr2[..

문자열 처리와 유니온파인드를 모두 활용해야 하는 아주 괜찮은 문제이다. 글쓴이는 총 2가지 경우로 나누어서 처리해주었다. 1) 속국이 종주국을 공격하는 경우 2) 왕국이 다른 왕국이나 다른 왕국의 속국을 공격하는 경우 문제를 풀면서 생각했던 풀이방법을 아래 사진으로 첨부했다. (유니온파인드) 문제를 풀면서 또 헤맸던 부분이 문자열 처리 부분이다. 글쓴이는 getline()을 사용하여 문자열 한 줄을 전체 받았는데, 이상하게 앞에서 cin으로 n, m을 받고 나서 한 줄의 여백이 자꾸 생기는 바람에 마지막 입력 한 줄을 못받는 이상한 상황?이 벌어졌다. 아마 getline이 '\n'을 인식해서 벌어진 일 같은데,,,, 정확한 이유는 모르겠다,,, 그래서 해결 방법을 모색하다 cin.ignore()라는 것을..