케이스윔의 개발 블로그

DFS는 vector로 구현도 해보고 문제도 몇개풀어봤으니 이제는 queue로 BFS를 구현해보려한다 DFS는 한 우물만 계속해서 파니까 쭉쭉 들어가기위해서 스택이 필요했고, BFS는 짧게짧게 갈 수 있는 모든 곳을 들러야하니까 FIFO(선입선출)인 큐가 필요하다 1. queue의 사용 #include을 해줘야한다queue Q; : int형으로 Q라는 이름의 큐 선언Q.push(값) : 해당값을 큐 Q에 넣는다Q.pop() : 큐 Q의 front를 삭제한다Q.front() : 큐의 제일 앞 값을 리턴한다(삭제되지않음)Q.back() : 큐의 제일 마지막 값을 리턴한다(삭제되지않음)Q.size() : 큐 Q의 원소 개수를 리턴한다 Q.empty() : 큐가 비어있는지를 확인한다. 비어있으면 1 비어있지않으..

문제남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다.재혁: 동우가 안 가면 나도 안 간다. 동우: 세종이가 안 가면 난 안 갈래.버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 많은 인원을 데려가지 않으면 안 되는 상황이었다.각 사람이 원하는 같이 갈 사람이 주어질 때, 버스에 태울 수 있는 사람은 최대 몇 명인지 알아내시오. 입력과 출력첫 번째 줄에 사람 수 n과 버스에 태울 수 있는 사람 수 k가 주어진다. (1 ≤ k ≤ n ≤..

문제재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이 때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시..

문제가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력과 출력첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력하고, 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력 풀이이전에 들어왔던 input 이랑 다르게 인접행렬 자체가 들어오므로 i, j를 입력받으면서 인접리스트를 만들고 n번 f..

문제과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력과 출력첫 번째 줄에는 지도의 크기 N(5

문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자. 입력첫째줄에 통로의 세로 길이(N

문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력과 출력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.출력은 연결 요소의 개수이다 풀이예제입력을 통해 그래프를 그려보면왼쪽과 같은 그래프가 그려지므로 연결 요소는 2가 된다 어제 만들었던 DFS를 이용할 수 있게 응용해보면 그 코드에서는 무조건 0에서 그래프가 만들어지고 DFS 탐색을 시작하는 걸로 되어있으니 for문을 통해서 visited에 방문한적없는 vertex부터 항..

오늘은 c++의 STL(Standard Templete Liberary) 중 하나인 vector를 공부하고 이걸로 DFS를 구현해서 계속해서 알고리즘 문제를 풀 때 응용을 하려고 한다 알고리즘 문제를 풀다보면 더 반복되는 부분이 많이 나올텐데 계속 구현하며 더 효율적으로 짤..수도 있겠지만 하나의 틀을 만들어서 응용해서 계속 사용하려고 한다 일단 벡터는 거의 c의 배열이랑 비슷한거 같긴하다 하지만 배열에서 확장된 기능을 가지고 있다나는 완전히 벡터 공부를 정복할려는게 아니니까 간단히 내가 사용할? 부분만 찾아서 정리해야겠따 vector에 가장 큰 특징 중 하나는 원소가 하나의 메모리 블록에 연속하게 저장된다는 것이라는데(무조건 데이터를 선형적으로 만들려고) 그래서 원소가 추가되거나 삽입될 때 메모리를 재..