문제 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다. 배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자. 입력 첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다. 출력 첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다. 제한 2 ≤ N, M ≤ 1,000 0과 1의 개수는 하나 이상이다. 풀이 그래프 탐색을 이용한 완전탐색 문제였다. NM 배열을 탐색하며, 값이 0..

문제 2007년 1월 9일(화)는 원장선생님의 말씀대로 어제와 같이 하루 일과를 팀플레이를 통해 하려고 한다. 이 날은 특별히 청팀과 백팀으로 두 팀을 나누어 팀전을 하려 한다. 하지만 어제 하루 팀플레이를 하면서, 서로 같은 팀을 하기 싫어하는 사람들이 생겼다. 이제 우리가 할 일은 다음과 같다. 사람들이 각각 싫어하는 사람들의 정보가 주어져 있을 때, 그 사람들의 요구를 수용하여 서로 싫어하는 사람은 같은 팀에 넣지 않으려 한다. 이 조건을 만족하여 n명의 사람들 두 팀으로 나누는 프로그램을 작성하여라. 입력 첫 줄에는 학생들의 수 n (1 ≤ n ≤ 100)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 서로가 싫어하는 사람들의 정보가 주어진다. i+1번째 줄에는 i번째 사람이 싫어하는 사람의 ..

풀이 문제의 핵심만 파악하면 쉽게 풀 수 있는 문제였다. 여기서 핵심은 첫 로봇에서 다른 로봇에까지 가는 데 발생하는 cost를 모두 더하여 구한 후 이동하였던 경로 중 가장 큰 cost가 발생하였던 것을 빼주면 답이 나오는 문제였다. 이때 그래프 탐색은 dfs를 활용하여 구현하였으며, 목표한 다른 로봇에 도달하였을 때 flag를 설정하여, dfs 이동 경로 중 발생한 cost를 계산하였다. #include #include using namespace std; int N,t1,t2; vector g[100001]; bool visited[100001],flag; int tmp,ans; void dfs(int v,int u){ if(v==u){ flag = true; visited[u] = true; re..

문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이..

풀이 A,B 각각의 단계에서 저장될 수 있는 최솟값을 dp로 구성하여 문제풀이를 하였다. 다른 라인으로 이동하지 않고 같은 라인의 다음 단계 시간과 이전 단계에서 다른 라인의 최솟값과 이동시간을 더한 값을 비교하여 점화식을 구성하였다. #include #include #include using namespace std; int main(int argc, char** argv) { int N; cin >> N; vector A(N), B(N), tA(N-1), tB(N-1); for (int i = 0; i > A[i] >> B[i] >> tA[i] >> tB[i]; } cin >> A[N - 1] >> B[N - 1]; vector dpA(N), dpB(N); dpA..

풀이 처음에는 dfs문제인줄 알았지만 풀다보니 일반 구현문제였다. 먼저 연관성을 입력 받고 반복문을 돌려 각 사람들에 연결된 사람들의 무게를 비교하며, 현재 단계 사람의 무게보다 연결된 사람의 무게가 더 무거우면 flag를 설정하여 카운트하지 않았다. #include #include using namespace std; int N,M; int W[100001]; vector vec[100001]; bool flag; int main(int argc, char** argv) { int u,v,ans=0; cin>>N>>M; for(int i=1;i>W[i]; } for(int i=0;i>u>>v; vec[u].push_back(v); vec[v].push_back(u); } for(int i=1;i