목록DFS (40)

1일1알

백준 13023번 ABCDE C++

서로 다른 5명이 이어져 있으면 된다. dfs로 문제를 해결하였는데, 처음에 방문 표시를 엉뚱한 곳에다 해서 시간이 좀 걸렸다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; bool isAns = false; vector v(2001, vector()); vector visited(2001, false); void Dfs(int n, int cnt) { if (cnt == 4) { isAns = true; return; } visited[n] = tr..
알고리즘 2022. 3. 14. 13:20
백준 21736번 헌내기는 친구가 필요해 C++

간단한 그래프 탐색 문제이다. bfs를 이용해서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; pair start; vector board(n, vect..
알고리즘 2022. 3. 4. 12:28
백준 2617번 구슬 찾기 C++

자기보다 가벼운 것과 무거운 것 두 경우의 그래프를 만들고, 둘 중 하나라도 자기의 자식의 수가 n/2보다 크다면 중간이 될 수 없다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int hs = 0; int ls = 0; vector light(100, vector()); vector heavy(100, vector()); vector visited1(100, false); vector visited2(100, false); void dfs1(int..
알고리즘 2022. 3. 1. 11:02
백준 1987번 알파벳 C++

백트래킹을 이용해서 해결할 수 있는 문제이다. 처음에 방문한 알파벳을 set에 저장해서 이미 방문한 곳인지 확인해서 풀었더니 시간초과가 났다. 그래서 알파벳 개수의 크기의 visited 배열을 만들어서 방문 체크를 O(1)에 할 수 있도록 수정했더니 통과되었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int r, c; int ans = 0; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; vec..
알고리즘 2022. 2. 27. 12:36
백준 2210번 숫자판 점프 C++

1. 백트래킹으로 5번 이동하는 경우를 모두 구한다. 2. 모든 칸에 대하여 1에서 구한 이동하는 경우를 적용한다. 3. 2의 과정에서 6자리수를 만들 수 있으면 그 수를 set에 넣는다. 4. set의 size를 출력한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; vector board(5, vector(5)); vector dirV; set s; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; void Sol..
알고리즘 2022. 1. 16. 12:56
백준 1068번 트리 C++

1. root부터 탐색하면서 삭제할 노드의 부모 노드를 알아낸다. 2. 삭제할 노드를 dfs를 이용하여 제일 밑에있는 자식 노드부터 차례로 삭제한다. 3. 2번이 끝났으면 삭제할 노드의 자식들은 모두 삭제가 된 상태이기 때문에 1번에서 파악한 부모 노드를 이용하여 삭제할 노드를 삭제한다. 4. root부터 탐색하면서 리프 노드의 갯수를 알아낸다. 예외) 삭제할 노드가 root노드라면 부모 노드가 없기때문에 0을 출력하고 프로그램을 종료한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef lon..
알고리즘 2022. 1. 15. 14:54
이전 Prev 1 2 3 4 5 6 7 Next 다음