본문 바로가기

BOJ206

[BOJ]16964번: DFS 스페셜 저지 (c++) https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루� www.acmicpc.net 방법 1: 입력순서대로 인접리스트를 정렬 후 dfs 재귀함수 호출 #include #include #include using namespace std; const int MAX = 100000; bool visited[MAX + 1]; int test_idx; // 입력으로 주어진 DFS 방문순서가 올바른지 검사 bool dfs(vector& graph, ve.. 2020. 5. 29.
[BOJ]16940번: BFS 스페셜 저지 (c++) https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 방법 1: 부모노드를 저장 후 비교 #include #include #include using namespace std; // 입력으로 주어진 BFS 방문순서가 올바른지 검사 bool bfs(vector& graph, queue& test) { // 문제에서 시작 노드는 1로 고정된다. if (test.front() != 1) { return false; } vector visit(graph.size()); vector parent(graph.size()); queue q; q.push(1); test.pop().. 2020. 5. 28.
[BOJ]16947번: 서울 지하철 2호선 (c++) https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호www.acmicpc.net  #include #include #include using namespace std;const int MAX = 3000;int info[MAX + 1];enum flag { NOT_CYCLE = -2, CYCLE_NOT_FOUND = -1, VISITED = 1, CYCLE = 2 };/* 깊이 우선 탐색으로 싸이클 찾기 반환값 0 : 싸이클을 찾았고, 반환값은 해당 .. 2020. 5. 28.
[BOJ]16929번: Two Dots (c++) https://www.acmicpc.net/problem/16929 16929번: Two Dots첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문��www.acmicpc.net 방법 1: 이동 횟수를 저장하며 탐색#include #include using namespace std;int dir_x[4] = {0, 1, 0, -1};int dir_y[4] = {1, 0, -1, 0};int N, M;// 깊이 우선 탐색bool dfs(vector &map, vector> &check, int x, int y){ // 4방향 탐색 for (int i = 0; i =.. 2020. 5. 28.

티스토리툴바