Little Jay

전형적인 DFS문제이다. 그런데 이제 Sorting을 곁들인..... 순서대로 DFS를 수행해주면 되지만 인접리스트로 구현한 그래프를 정렬을 하고 DFS를 수행해줘야 한다. 문제해결기법 13주차 A번 문제와 매우 유사한 문제였던 것 같다. #include #define endl '\n' #define pii pair using namespace std; int t; vector v[100001]; bool visited[100001]; int order[100001]; vector dfs_order; bool cmp(int& a, int& b) { return order[a] < order[b]; } void dfs(int start) { if (visited[start]) return; visited[..

강연결요소는 DFS를 두번 실행해서 연결된 요소를 찾을 수 있다. stack에 방문한 순서가 아닌 finished 되는 순서로 넣어야하기 때문에 이 점을 주의해서 풀면 될 것이다. 정렬을 빡세게 수행했는데 이렇게까지는 안해도 될 것 같다. #include #include #include #include using namespace std; #define endl '\n' #define vvi vector #define vi vector #define vb vector int n, m; int follower[50001]; void first_dfs(int start, vb& visited, vvi& adj, stack& st) { visited[start] = true; for (auto next : a..

문제 조건에 아무 지역도 물에 잠기지 않을 수도 있다. 이 말을 듣고 음 그런군..... 이라고 생각을 했었는데 이것때문에 계속 틀렸다;;; 이 말은 즉슨 level이 0부터 시작될 수도 있다는거다 #include #include #include #include #include using namespace std; int n, safe, level; int map[101][101]; bool visited[101][101]; int map_copy[101][101]; vector v; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; void copy(int flood_level) { for (int i = 0; i < n; i++)..

아래의 문제 15650번과 유사한 문제이다 #include #include #define MAX 9 using namespace std; int n, m; int arr[MAX] = { 0, }; bool visited[MAX] = { 0, }; void dfs(int num, int cnt) { if (cnt == m) { for (int i = 0; i < m; i++) cout m; dfs(1, 0); return 0; }

이번에는 중복순열 문제이다 이전에는 중복을 체크하면서 DFS를 했는데, 이번에는 중복을 허용하기때문에 그 부분만 주석처리 해주어 쉽게 풀 수 있었다. #include #include #define MAX 9 using namespace std; int n, m; int arr[MAX] = { 0, }; bool visited[MAX] = { 0, }; void dfs(int cnt) { if (cnt == m) { for (int i = 0; i < m; i++) cout m; dfs(0); return 0; }

백트래킹에 들어가있지만, DFS로 풀 수 있는것 같다. 둘이 조금은 비슷한 성향을 가진 문제인 것 같다. #include #include #define MAX 9 using namespace std; int n, m; int arr[MAX] = { 0, }; bool visited[MAX] = { 0, }; void dfs(int num, int cnt) { if (cnt == m) { for (int i = 0; i < m; i++) cout m; dfs(1, 0); return 0; }

Mooyo Mooyo == 뿌요뿌요....? 문제가 영어라 해석이 들어가야 한다. 문제를 잠시 분석을 한다면, n X 10의 줄을 입력을 받아서 뿌요뿌요 게임을 실행시켜주면 된다. 먼저 같은 숫자가 k개 이상 연결 되어 있다면 0으로 만들어준다. 이 과정을 dfs로 탐색하고 바꿔준다. 그 후에 중력의 영향을 받아 아래로 블럭들을 아래로 당겨주어야 한다. 아래로 다 당겨주었다면 계속해서 블럭들을 터뜨리고.... 이 과정을 계속 반복해주면 된다. 범위 잘못 설정해서 여러번 틀렸다..... 그래프 문제는 진짜 한 시간 이상 걸려서 푸는데 코딩좀 잘 하고 싶어요ㅠㅠ #include #include using namespace std; int n, k; char table[100][10]; bool visited..

생각보다 엄청 더러웠던(?) 문제였다. 역시 브루트포스는 항상 그렇고 그렇다...... CCTV 구조체를 하나 만들어서 CCTV 종류(몇번인지), 몇열, 몇행에 저장되어있는지에 대한 정보를 저장하고 rotation이라는 정수 배열에서 회전 가능한 범위를 넣어주었다. 디버깅을 하면 이제 input 하고 dfs로 탐색이 들어가는데, 이제 중요한점은 백트랙킹을 해야한다는 것이다. 이 문제의 핵심인 부분이다. 예를 들어서 01000 00000 00000 00000 00000 이런 cctv가 있으면, 얘는 아래쪽으로 탐색을 해야 하는 것이다 그래서 이 부분에 대해서 각각의 경우에 대해서 백트랙킹을 해주면 된다. #include #define MAX 8 using namespace std; struct CCTV {..

기본적인 그래프문제 #include #include #include #include #include #include using namespace std; vector a[1001]; bool check[1001]; void dfs(int node) { check[node] = true; printf("%d ", node); for (int i = 0; i < a[node].size(); i++) { int next = a[node][i]; if (check[next] == false) { dfs(next); } } } void bfs(int start) { queue q; memset(check, false, sizeof(check)); check[start] = true; q.push(start); w..