문제https://www.acmicpc.net/problem/1707풀이과정주어진 그래프가 이분 그래프인지 아닌지 출력하는 문제이다. 먼저 이분 그래프란 무엇인지 찾아보니 모든 노드를 빨강색 혹은 파랑색으로 칠하는데 같은 색을 가진 노드는 서로 인접하지 않는 위치에 존재하는 그래프이다.이분 그래프인지 아닌지 판별하는 방법은 dfs나 bfs로 그래프를 탐색하며 노드를 색칠하고 색칠되어 있는 노드를 방문할 경우 인접한 노드와 같은 색깔이면 이분 그래프가 아니라고 판별할 수 있다.소스코드#include #include #include using namespace std; vector a[20001]; int color[20001]; void dfs(int node, int c) { color[node] = c..
문제https://www.acmicpc.net/problem/9935풀이과정처음에는 문자열을 처음부터 ans라는 문자열 변수에 하나씩 넣어가며 문자열 끝부터 폭발문자열의 길이만큼의 chk_str을 만들어 폭발문자열과 비교하고 같으면 substr을 통해 ans 문자열에서 폭발문자열을 제거하는 식으로 해결하고자 했다. 하지만 제출결과는 시간 초과가 났다. 그 이유를 살펴보니 입력되는 문자열의 최대길이는 백만이고 시간제한이 1초이므로 시간복잡도 O(N) 정도로 해결해야하는 문제였다.그래서 다시 생각해서 새로운 알고리즘을 생각했다. 입력 문자열을 순차적으로 ans 문자열 변수에 넣는다.만약 넣는 문자가 폭발문자열의 끝 문자와 같다면폭발문자열의 길이만큼 ans 문자열을 검사한다ans의 끝 쪽이 폭발문자열이면 폭발..
문제https://www.acmicpc.net/problem/1260풀이과정DFS와 BFS 구현에 대한 기본적인 문제이다. DFS는 벡터를 이용해 구현했고, BFS는 큐를 이용해 구현하였다. 문제에서 방문할 수 있는 정점이 여러개일 경우에는 정점 번호가 작은 것을 먼저 방문한다는 조건을 주었기 때문에 DFS와 BFS를 실행하기 전에 인접 리스트를 정렬 시켜줬다.소스코드#include #include #include #include using namespace std; int N, M, V; vector a[1001]; bool chk[1001]; void DFS(int node) { chk[node] = true; cout > V; for (int i = 0; i < M; i++) { int x, y; ..