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를 활용하는 것이 정배라고는 하지만 이 문제는 단순히 BFS를 통해서 문제를 풀 수 있었다. 1번 Node는 고려하지 않으므로, 1번 Node에서 출반하여 BFS 탐색을 수행하면 문제가 풀린다. 문제는 항상 root node가 1이 아니기 때문에 입력에서 양방향 인접리스트로 받았는데, 이제 visited한 것을 잘 처리해주면 된다. #include #define endl '\n' #define pii pair using namespace std; int n; vector tree[100001]; bool visited[100001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)..

코로나 확진 후 집에서 공부가 되지 않는 스타일이라 주구장창 놀기만 한 것 같다. 슬슬 블로그 운영 다시 해야겠다. 간단한 BFS문제였지만 오타때문에 맞왜틀을 1시간동안 하고 있던 문제다. 3차원 배열을 활용해서 벽을 부쉈으면 [][][1]쪽으로 이동해서 그쪽에서 부터 BFS를 돌리면 된다. 코딩 스타일이 cur.first.first 이렇게 전부 다 쓰는 스타일이라 여기서 까딱 실수해버리면 항상 맞왜틀 하고 있는 것 같다... #include #define endl '\n' #define pii pair using namespace std; int graph[1001][1001]; int visited[1001][1001][2]; int n, m; const int dx[] = { 1, -1, 0, 0 ..

인접행렬로 문제를 푸는 것을 선호하는데, 이렇게 인접 리스트로 푸는게 오랜만이라 시간이 좀 걸렸다. 항상 느끼는 거지만 인접행렬이 더 편한 것 같다. #include #define endl '\n' #define MAX 100005 using namespace std; int n, m, init; vector v[MAX]; bool visited[MAX]; int solve() { int cnt = 0; queue q; q.push(init); visited[init] = true; while (!q.empty()) { auto current = q.front(); q.pop(); if (!v[current].size()) { return cnt; } if (visited[v[current][0]]) b..

입력받는것을 계속 int로 받다가 실패했다. 띄어쓰기가 없는 것은 char이나 string으로 받아야 하는 것에 유의하자. n-1일때 return true 해야하는데 m-1로 계속 써서 실패했다. 항상 조건을 잘 보도록 하자. #include #define endl '\n' using namespace std; int n, m; int board[1005][1005]; bool visited[1005][1005]; const int dx[4] = { 1, -1, 0, 0 }; const int dy[4] = { 0, 0, 1, -1 }; bool bfs(int y, int x) { visited[y][x] = true; queue q; q.push({ y, x }); while (!q.empty()) {..

BFS로 구현했다. (DFS 싫어) #include #define endl '\n' using namespace std; bool arr[51][51]; bool visited[51][51]; const int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }; const int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 }; int w, h; int bfs(int x, int y) { if (arr[x][y] == 0) return 0; if (visited[x][y]) return 0; queue q; q.push({ x, y }); visited[x][y] = 1; while (!q.empty()) { auto current = q.front(); q.pop();..

문제 조건에 아무 지역도 물에 잠기지 않을 수도 있다. 이 말을 듣고 음 그런군..... 이라고 생각을 했었는데 이것때문에 계속 틀렸다;;; 이 말은 즉슨 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++)..

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 {..

dfs로 간단하게 풀 수 있는 문제이다. 1번 컴퓨터를 통해 감염되는 컴퓨터의 개수를 출력하면 되기 때문에, 탐색을 할 노드를 1번 노드로 고정을 해놓고, 1번 노드를 통해 다시 재귀로 탐색을 할 때마다 감염된 컴퓨터의 수를 하나씩 증가시켜주면 된다. #include #include #include #include #include using namespace std; vector a[1001]; bool check[1001]; int infected = 0; void dfs(int node) { check[node] = true; for (int i = 0; i < a[node].size(); i++) { int next = a[node][i]; if (check[next] == false) { infe..