본문 바로가기

그래프 이론15

[백준/C,C++] 1012번: 유기농 배추 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 모든 방문하지 않은 좌표를 돌며 DFS가 몇번 실행되는지 탐색하면 되는 문제입니다. #include #include #include using namespace std; const int MAX = 50; int m, n, k; int map[MAX][MAX]; bool visited[MAX][MAX]; pair direction[4] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; int re.. 2021. 5. 5.
[백준/C,C++] 2606번: 바이러스 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 1번을 기준으로 DFS나 BFS를 돌려주기만 하면 되는 문제입니다. #include #include using namespace std; const int MAX = 101; vector v[MAX]; bool visited[MAX]; int res = -1; void DFS(int node) { res++; visited[node] = true; size_t sz = v[node].size(); for (si.. 2021. 5. 5.
[백준/C,C++] 9019번: DSLR www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 최단 거리 찾기 종류의 문제인데, 살짝 변형된 문제입니다. 이 문제에서 중요한 것은 실행된 명령어를 어떻게 유지할 것인가인데, 문자열로 유지를 했더니 시간 초과가 났습니다. 그래서 다른 분들의 코드를 참고해 pair에 현재 사용된 명령어와 이전 노드의 번호를 저장해 마지막에 역순으로 출력해주는 방식을 사용했습니다. #include #include #include #include using na.. 2021. 4. 21.
[백준/C,C++] 1707번: 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 풀이 이분 그래프라 함은 모든 꼭짓점을 빨강과 파랑으로 칠하되, 모든 변이 빨강과 파랑을 포함하도록 색칠할 수 있는 그래프를 말합니다(출처 : 위키백과). 즉 같은 레벨(깊이)의 정점은 모두 같은 색으로 칠할 수 있어야 합니다. 너비 우선 탐색을 하며 방문하지 않은 정점이라면 이전 레벨의 노드와 반대의 색을 칠하고 방문한 정점이라면 이전 레벨의 노드와 색이 반대인지 체크한 후에 반대가 아니라면 이분.. 2021. 4. 21.

티스토리툴바